Abstract
We analyze the fine structure of time complexity classes for RAM's, in particular the equivalence relation A= C B (“A and B have the same time complexity”) ⇔ (for all time constructible f : A∈DTIME RAM (f) ⇔ B∈DTIME RAM (f)). The =C-equivalence class of A is called its complexity type. We prove that every set X can be partitioned into two sets A and B such that X=t C A= C B, and that the partial order of sets in an arbitrary complexity type under \( \subseteq *\) (inclusion modulo finite sets) is dense. The proofs employ a new strategy for finite injury priority arguments.
We consider the following set of time bounds:
T:={f : N→N|f(n)≥n and f is time constructible on a RAM}, where f is called time constructible on a RAM if some RAM can compute the function 1n↦1f(n) in O(f(n)) steps. We do not allow arbitrary recursive functions as time bounds in our approach in order to avoid pathological phenomena (e.g. gap theorems [HU], [HH]). In this way we can focus on those aspects of complexity classes that are relevant for concrete complexity (note that all functions that are actually used as time bounds in the analysis of algorithms are time constructible). We use the random access machine (RAM) with uniform cost criterion as machine model (e.g. as defined in [CR]; see also [AHU], [MY]) because this is the most frequently considered model in algorithm design, and because a RAM allows more sophisticated diagonalization — constructions than a Turing machine. One defines DTIME RAM (f):={A\( \subseteq \) {0, 1}*| there is a RAM of time complexity O(f) that computes A∼. We write DTIME(f) for DTIME RAM (f) in the following.
For sets A, B \( \subseteq \){0, 1}* we define
A= C B(“A has the same det. time complexity as B”)
A complexity type is an equivalence class of this equivalence relation = C .
We write 0 for DTIME(n), which is the “minimal” complexity type. Note that for every complexity type C and every f∈T one has either C \( \subseteq \) DTIME(f) or C∩DTIME(f)=0.
In this paper we investigate some basic properties of the partial order
where C is an arbitrary complexity type and \( \subseteq *\) denotes inclusion modulo finite sets (i.e. X\( \subseteq *\)Y : ↦ X−Y is finite).
This work is part of the long range project to study the relationship between extensional properties of a set and its computational complexity. Among other work in this direction we would like to mention in particular the study of the complexity of sparse sets (see e.g. [Ma]), and the investigation of the relationship between properties of recursively enumerable sets under \( \subseteq *\) and their degree of computability (see e.g. Chapter XI in [So]). Our approach differs from this preceding work insofar as it also applies to “actually computable” sets (i.e. sets in P). Therefore it provides an opportunity to develop finer construction tools that can be used to examine also the structure of sets of small complexity. In this paper we introduce a new strategy for a finite injury priority argument that allows us to prove splitting and density theorems for sets of arbitrarily given complexity type C (for example sets of time complexity Θ(n 2)). Further results about the structure of complexity types can be found in [MS].
Written under partial support by NSF-Grant CCR 8703889.
Written under partial support by Presidential Young Investigator Award DMS-8451748 and NSF-Grant DMS-8601856.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley (Reading, 1974).
M. Blum, A machine-independent theory of the complexity of recursive functions, J. ACM, 14(1967), 322–336.
S.A. Cook, R.A. Reckhow, Time-bounded random access machines, J. Comp. Syst. Sc., 7(1973), 354–375.
J. Hartmanis, J.E. Hopcroft, An overview of the theory of computational complexity, J. ACM, 18(1971), 444–475.
L.A. Levin, On storage capacity for algorithms, Soviet Math. Dokl., 14(1973), 1464–1466.
N. Lynch, Helping: several formalizations, J. of Symbolic Logic, 40(1975), 555–566.
M. Machtey, P. Young, An Introduction to the General Theory of Algorithms, North-Holland (Amsterdam, 1978).
S. Mahaney, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, J. Comp. Syst. Sc., 25(1982), 130–143.
A.R. Meyer, P.C. Fischer, Computational speed-up by effective operators, J. of Symbolic Logic, 37(1972), 55–68.
A.R. Meyer, K. Winklmann, The fundamental theorem of complexity theory, Math. Centre Tracts, 108(1979), 97–112.
W. Maass, T.A. Slaman, On the complexity types of computable sets (extended abstract), to appear in: Proc. of the Structure in Complexity Theory Conference 1989.
C.P. Schnorr, G. Stumpf, A characterization of complexity sequences, Zeitschr. f. math. Logik u. Grundlagen d. Math., 21(1975), 47–56.
R.I. Soare Recursively Enumerable Sets and Degrees, Springer (Berlin, 1987).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maass, W., Slaman, T.A. (1989). Extensional properties of sets of time bounded complexity (extended abstract). In: Csirik, J., Demetrovics, J., Gécseg, F. (eds) Fundamentals of Computation Theory. FCT 1989. Lecture Notes in Computer Science, vol 380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51498-8_31
Download citation
DOI: https://doi.org/10.1007/3-540-51498-8_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51498-5
Online ISBN: 978-3-540-48180-5
eBook Packages: Springer Book Archive