Abstract
To be considered fast, algorithms for operations on large data structures should operate in polylog time, i.e., with the number of steps bounded by a polynomial in log(N) where N is the size of the data structure. Example: an ordered list of reasonably short strings can be searched in log2 (N) time via binary search. To measure the time and space complexity of such operations, the usual Turing machine with its serial-access input tape is replaced by a random access model. To compare such problems and define completeness, the appropriate relation is loglog reducibility: the relation generated by random-access transducers whose work tapes have length at most log(log(N)). The surprise is that instead of being a refinement of the standard log space, polynomial time, polynomial space, ... hierarchy, the complexity classes for these random-access Turing machines form a distinct parallel hierarchy, namely, polylog time, polylog space, exppolylog time, ... . Propositional truth evaluation, context-free language recognition and searching a linked list are complete for polylog space. Searching ordered lists and searching unordered lists are complete for polylog time and nondeterministic polylog time respectively. In the serial-access hierarchy, log-space reducibility is not fine enough to classify polylog-time problems and there can be no complete problems for polylog space even with polynomial-time Turing reducibility
References
[1]
AHO, A., HOPCROFT, J., and ULLMAN, J. THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS. Addison-Wesley, Reading Mass. 1974, pp. 97-99.
[2]
BOOK, R. Comparing complexity classes. J. COMPUT. SYS. SCI. 9(1974), 213-229.
[3]
BOOK, R. Translational lemmas, polynomial time, and (logn)@@@@-space. THEOR. COMPUT. SCI. 1 (1976), 215-226.
[4]
BORODIN, A. On relating time and space to size and depth. SIAM J. COMPUT. 6 (1977), 733-744.
[5]
CHANDRA, A., KOZEN, D., and STOCKMEYER, L. Alternation. J. ACM 28 (1981), 114-133.
[6]
COBHAM, A. The intrinsic computational difficulty of functions. PROC. 1964 INTERNAT. CONGR. FOR LOGIC, METH., AND PHILO. OF SCI., North-Holland, Amsterdam, pp. 24-30.
[7]
COOK, S. Path systems and language recognition. 2nd ANN. ACM SYMP. ON THEORY OF COMPUTING, 1970, pp. 70-72.
[8]
COOK, S. The complexity of theorem proving procedures. 3rd ANN. ACM SYMP. ON THEORY OF COMPUTING, New York, 1971a, pp. 151-158.
[9]
COOK, S. Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971b), 4-18.
[10]
COOK, S. A hierarchy for nondeterministic time complexity, J. COMPUT. SYS. SCI. 7 (1973), 343-353.
[11]
COOK, S. An observation on time-storage trade off. J. COMPUT. SYS. SCI. 9 (1974), 308-316.
[12]
COOK, S. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. PROC. 11th ACM SYMP. ON THEORY OF COMPUTING, 1979, pp. 338-345.
[13]
CSANKY, L. Fast parallel matrix inversion algorithms. SIAM J. Comput. 5 (1976), 618-623.
[14]
HARTMANIS, J. On log-tape isomorphisms of complete sets. THEOR. COMPUT. SCI. 7 (1978a), 273-286.
[15]
HARTMANIS, J. FEASIBLE COMPUTATIONS AND PROVABLE COMPLEXITY PROPERTIES. CBMS-NSF Regional Conf. Series in Applied Math. vol. 30, SIAM, Philadelphia, 1978b.
[16]
HARTMANIS, J., IMMERMAN, N., and MAHANEY, S. One-way log-tape reductions. 19th ANN. IEEE SYMP. ON FOUNDATIONS OF COMP. SCI., 1978, pp. 65-72.
[17]
HOPCROFT, J. and ULLMAN, J. FORMAL LANGUAGES AND THEIR RELATION TO AUTOMATA. Addison-Wesley, Reading, MA, 1969, pp. 148-149.
[18]
HOPCROFT, J. and ULLMAN, J. INTRO. TO AUTOMATA THEORY, LANGUAGES AND COMPUTATION. Addison-Wesley, Reading, MA, 1979, pp. 285-306.
[19]
IBARRA, O. Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxillary stack automata. J. COMPUT. SYS. SCI. 5 (1971), 88-117.
[20]
IBARRA, O. A note concerning nondeterministic tape complexities. J. ACM 19 (1972), 608-612.
[21]
IBARRA, O. and CHAN, T. On the space and time complexity of functions computable by simple programs. Technical Report 81-36, 1981, Dept. of Computer Sci., University of Minnesota, Minneapolis, Minnesota.
[22]
JONES, N. Space-bounded reducibility among combinatorial problems, J. COMPUT. SYS. SCI. 11 (1975), 68-85.
[23]
JONES, N., LIEN, Y., and LAASER, W. New problems complete for nondeterministic log space. MATH. SYS. THEORY 10 (1976), 1-17.
[24]
JONES, N., and LAASER, W. Problems complete for deterministic polynomial time. THEOR. COMPUT. SCI. 3 (1977), 105-117.
[25]
KARP, R. Reducibility among combinatorial problems. COMPLEXITY OF COMPUTER COMPUTATIONS (Miller, R.E., and Thatcher, J. eds.), Plenum Press, New York, 1972, pp. 85-104.
[26]
LYNCH, N. Log space recognition and translation of parenthesis languages. J. ACM 24 (1977), 583-590.
[27]
PAUL, W., and REISCHUK, R. On time versus space II. J. COMPUT. SYS. SCI. 22 (1981), 312-327.
[28]
PIPPENGER, N. On simultaneous resource bounds. 20th ANN. SYMP. ON FOUNDATIONS OF COMPUT. SCI., 1979, pp. 307-311.
[29]
PIPPENGER, N., and FISCHER, M. Relations among complexity measures. J ACM 26 (1979), 361-381.
[30]
PREPARATA, F., and VUILLEMIN, J. The cube-connected cycles: A versatile network for parallel computation. COMM. ACM 24 (1981), 300-309.
[31]
RUZZO, W. Tree-size bounded alternation. J. COMPUT. SYS. SCI. 21 (1980), 218-235.
[32]
RUBY, S. and FISCHER, P. Translational methods and computational complexity. CONF. RECORD IEEE 6th ANN. SYMP. ON SWITCHING CIRCUIT THEORY AND LOGICAL DESIGN, 1965, pp. 173-178.
[33]
RUZZO, W. On uniform circut complexity. J. COMPUT. SYS. SCI. 22 (1981), 365-383.
[34]
SAVITCH, W. Relations between nondeterminisitic and deterministic tape complexities. J. COMPUT. SYS. SCI. 4 (1970), 177-192.
[35]
SAVITCH, W. Nondeterministic Log N space. PROC. 8th ANN. PRINCETON CONF. ON INFORMATION SCIENCES AND SYSTEMS, Dept. of Electrical Engineering, Princeton University, Princeton, NJ, 1974, pp. 21-23.
[36]
SCHWARTZ, J. Ultracomputers. ACM TANS. ON PROGRAMMING LANG. AND SYS. 2 (1980), 484-521.
[37]
STOCKMEYER, L., and MEYER, A. Word problems requiring exponential time: preliminary report, PROC. FIFTH ANNUAL ACM SYMP. ON THEORY OF COMPUT. (1973), pp. 1-9.
[38]
STOCKMEYER, L. The polynomial-time hierarchy. THEOR. COMPUT. SCI. 3 (1976), 1-22.
[39]
STONE, H. Parallel processing with the perfect shuffle. IEEE TRANS. COMPUT. C-20, 2 (1971), 153-161.
[40]
SUDBOROUGH, H. Time and tape bounded auxiliary pushdown automata, MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE, Lecture Notes in Computer Science, No. 53, Springer-Verlag, Belin/New York, 1977, pp. 493-503.
Index Terms
- The random access hierarchy
Recommendations
Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer ScienceAbstractThe dynamic trie is a fundamental data structure which finds applications in many areas. This paper proposes a compressed version of the dynamic trie data structure. Our data-structure is not only space efficient, it also allows pattern searching ...
A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence
SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and ArchitecturesThe neighborhood independence number of a graph G, denoted by β = β(G), is the size of the largest independent set in the neighborhood of any vertex. Graphs with bounded neighborhood independence, already for constant β, constitute a wide family of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 1983
487 pages
ISBN:0897910990
DOI:10.1145/800061
Copyright © 1983 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 December 1983
Check for updates
Author Tags
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 95Total Downloads
- Downloads (Last 12 months)58
- Downloads (Last 6 weeks)10
Reflects downloads up to 13 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in