article Share on Separation of complexity classes Author: Juris Hartmanis Cornell University Cornell UniversityView Profile Authors Info & Claims Journal of the ACMVolume 50Issue 1January 2003 pp 58–62https://doi.org/10.1145/602382.602402Published:01 January 2003Publication History 0citation1,645DownloadsMetricsTotal Citations0Total Downloads1,645Last 12 Months15Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We investigate the Kolmogorov complexity of real numbers. Let K be the Kolmogorov complexity function; we determine the Hausdorff dimension and the topological dimension of the graph of K. Since these dimensions are different, the graph of the Kolmogorov complexity function of the real line forms a fractal in the sense of Mandelbrot. We also solve an open problem of Razborov using our exact bound on the topological dimension.

The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the unrelativized case. Although this paper is not the first to provide a counterexample to the Random Oracle Hypothesis, it does provide a most compelling counterexample by showing that for almost all oracles A, IPA ≠ PSPACEA. If the Random Oracle Hypothesis were true, it would contradict Shamir's result that IP = PSPACE. In fact, it is shown that for almost all oracles A, co-NPA ⫋ IPA. These results extend to the multiprover proof systems of Ben-Or, Goldwasser, Killian, and Wigderson. In addition, this paper shows that the Random Oracle Hypothesis is sensitive to small changes in the definition. A class IPP, similar to IP, is defined. Surprisingly, the IPP = PSPACE result holds for all oracle worlds.

The One-way Conjecture states that the existence of nonisomorphic NP-complete sets implies the existence of one-way functions. This paper gives a relativized counterexample to the conjecture by constructing a relativized world that has nonisomorphic NP-complete sets, but lacks one-way functions.

In this paper we review the key results about space bounded complexity classes, discuss the central open problems and outline the prominent proof techniques. We show that, for a slightly modified Turing machine model, low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch's theorem and the Immerman-Szelepcsényi theorem do not hold in the range lg lg n to lg n. We also present other changes in the computation model which bring out and clarify the importance of space constructibility. We conclude by enumerating open problems which arise out of the discussion.

This paper discusses the scope and goals of structural complexity theory, describes some working hypotheses of this field and summarizes (some) recent developments.

A robust machine is a machine that maintains some computational property for every oracle. In this paper we study robustly complementary, robustly categorical, robustly ∑∗-accepting, and robustly ∑∗-spanning machines. We prove that robust machines squander their powerful nondeterministic oracle access in all relativizations—relative to any oracle A, their languages and properties can be computed in PNPA.

The Boolean Hierarchy I: Structural Properties [J. Cai et al., SIAM J. Comput ., 17 (1988), pp. 1232–252] explores the structure of the boolean hierarchy, the closure of NP with respect to boolean operations. This paper uses the boolean hierarchy as a tool with which to extend and explain three important results in structural complexity theory. (1) Hartmanis, Immerman, and Sewelson [ Proc. 15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391] showed that ${\text{E}} = {\text{NE}}$ if and only if ${\text{NP}} - {\text{P}}$ contains no sparse sets. In this paper it is shown that this reflects a behavior of the boolean hierarchy. When ${\text{E}} = {\text{NE}}$, sparse sets fall from alternate levels of the boolean hierarchy (Fig. 2(a)). Furthermore, it is shown that capturable sets (i.e., subsets of sparse NP sets) are banished from the boolean hierarchy when ${\text{E}} = {\text{NE}}:{\text{E}} = {\text{NE}}$ implies that ${\text{BH}} - {\text{P}}$ has no capturable sets. (2) Counting classes are natural candidates as complete languages for the levels of the boolean hierarchy. The authors show that in relativized worlds counting classes are not complete for the levels of the boolean hierarchy. Relatedly, the work of Blass and Gurevich [Inform, and Control, 55 (1982), pp. 80–88] is extended and it is concluded that counting classes are weak in some relativized worlds. (3) Karp and Lipton [Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309] showed that if NP has a sparse oracle (i.e., if there is a sparse set S so ${\text{NP}} \subseteq {\text{P}}^S $; equivalently, if NP has small circuits), then the polynomial hierarchy collapses to ${\text{NP}}^{{\text{NP}}} $. The authors demonstrate that this cannot be much improved. There is a relativized world in which NP has a sparse oracle, yet the boolean hierarchy is infinite. Thus no proof that relativizes can show: NP has .a sparse oracle implies that the polynomial hierarchy equals the boolean hierarchy. The results of this paper present new ideas and techniques, and put previous results about NP and ${\text{D}}^{\text{P}} $ in a richer perspective. Throughout, the emphasis is on the structure of the boolean hierarchy and its relations with more common classes.

In this paper, we study the complexity of sets formed by boolean operations (union, intersection, and complement) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together these form the boolean hierarchy. We present many results about the structure of the boolean hierarchy: separation and immunity results, natural complete languages, and structural asymmetries between complementary classes. We show that in some relativized worlds the boolean hierarchy is infinite, and that for every k there is a relativized world in which the boolean hierarchy extends exactly k levels. We prove natural languages, variations of VERTEX COVER, complete for the various levels of the boolean hierarchy. We show the following structural asymmetry: though no set in the boolean hierarchy is ${\text{D}}^{\text{P}} $-immune, there is a relativized world in which the boolean hierarchy contains ${\text{coD}}^{\text{P}} $-immune sets. Thus, this paper explores the structural properties of the boolean hierarchy. A companion paper [J. Cai et al., SIAM J. Comput. 18 (1989), to appear] uses the boolean hierarchy to extend known results on small circuits [R. Karp and R. Lipton, Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309], sparse sets in NP-P [J. Hartmanis, N. Immerman, and V. Sewelson, Proc.15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391], and counting classes [A. Blass and Y. Gurevich, Inform. and Control, 55 (1982), pp. 80–88].

This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of their machines. Counting classes, probabilistic classes, and intersection classes often lack such enumerations. Concentrating on the counting class UP, we show that there are relativizations for which UPA has no complete languages and other relativizations for which PB≠UPB≠NPB and UPB has complete languages. Among other results we show that (1) UP has complete languages if and only if there exists a set R in P of Boolean formulas, each having at most one satisfying assignment so that SAT∩R is complete for UP. (2) P ≠ UP if and only if there exists a set S in P of Boolean formulas, each having at most one satisfying assignment, such that S ∩ SAT is not in P. (3) P ≠ UP ∩ coUP if and only if there exists a set S in P of uniquely satisfiable Boolean formulas such that no polynomial-time machine can compute the solutions for the formulas in S. We suggest the wide applicability of our techniques to counting and probabilistic classes by using them to examine the probabilistic class BPP. There is a relativized word where BPPA has no complete languages. If BPP has complete languages, then it has a complete language of the form B ∩ Majority, where B ϵ P and Majority = {f¦f is true for at least half of all assignments} is the canonical PP-complete set.

In this paper we define a generalized, two-parameter, Kolmogorov complexity of finite strings which measures how much and how fast a string can be compressed and we show that this string complexity measure is an efficient tool for the study of computational complexity. The advantage of this approach is that it not only classifies strings as random or not random, but measures the amount of randomness detectable in a given time. This permits the study how computations change the amount of randomness of finite strings and thus establish a direct link between computational complexity and generalized Kolmogorov complexity of strings. This approach gives a new viewpoint for computational complexity theory, yields natural formulations of new problems and yields new results about the structure of feasible computations.

The main result of this note shows that there exist sparse sets in $NP$ that are not in $P$ if and only if NEXPTIME differs from EXPTIME. Several other results are derived about the complexity of very sparse sets in $NP-P$ and an interpretation of the meaning of these results is given in terms of the complexity of solving "individual instances" of problems in $NP-P$.

In this paper we study languages accepted by nondeterministic $\log n$-tape automata that scan their input only once and relate their computational power to two-way $\log n$-tape automata. We show that for the one-way $\log n$-tape automata the nondeterministic model (1-NL) is computationally much more powerful than the deterministic model (1-L), that under one-way $\log n$-tape reductions there exist natural complete languages for these automata and that the complete languages cannot be sparse. Furthermore, we show that any language complete for nondeterministic one-way $\log n$-tape automata (under 1-L reductions) is also complete for the computationally more powerful nondeterministic two-way $\log n$-tape automata (NL) under two-way $\log n$-tape reductions. Therefore, for all bounds $T(n)$, $T(n) \geqq \log n$, the deterministic and nondeterministic $T(n)$-tape bounded computations collapse iff the nondeterministic one-way $\log n$-tape computations can be carried out by two-way deterministic log n-tape automata.

The purposes of this paper is to give simple new proofs of some interesting recent results about the relative succinctness of different representations of regular, deterministic and unambiguous context-free languages and to derive some new results about how the relative succinctness of representations change when the representations contain a formal proof that the languages generated are in the desired subclass of languages.

Several representations of P, the class of deterministic polynomial time acceptable languages, are compared with respect to succinctness. It is shown that requirements such as polynomial running time, verifiability of running time, and verifiability of accepting a set in P can be causes for differences in succinctness that are not recursively bounded. Relating succinctness to nondeterminism, it is shown that P ≠ NP if and only if the relative succinctness of representing languages in P by deterministic and nondeterministic clocked polynomial time machines is not recursively bounded. questions are posed, concerning the implications of P = NP, with respect to translatability and succinctness between other pairs of deterministic and nondeterministic representations for P.

This paper gives a personal account of some developments in automata theory and computational complexity theory. Though the account is subjective and deals primarily with the research areas of direct interest to the author, it discusses the underlying beliefs and philosophy which guided this research as well as the intellectual environment and the ideas and contacts which influenced it. An attempt is also made to draw some general conclusions about computer science research and to discuss the nature of theoretical computer science.

One-way log-tape (1-L) reductions are mappings defined by log-tape Turing machines whose read head on the input can only move to the right. The 1-L reductions provide a more refined tool for studying the feasible complexity classes than the P-time [2,7] or log-tape [4] reductions. Although the 1-L computations are provably weaker than the feasible classes L, NL, P and NP, the known complete sets for those classes are complete under 1-L reductions. However, using known techniques of counting arguments and recursion theory we show that certain log-tape reductions cannot be 1-L and we construct sets that are complete under log-tape reductions but not under 1-L reductions.

In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional “clock” in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. Furthermore, these diagonalization methods show that the Gap Theorem for resource bounded computations does not hold for complexity classes consisting only of languages accepted by Turing machines for which it can be formally proven that they run in the required time bound.

If all $NP$ complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then $P \ne NP$ and if all PTAPE complete sets are P-isomorphic then $P \ne {\text{PTAPE}}$. We show that all $NP$ complete sets known (in the literature) are indeed p-isomorphic and so are the known PTAPE complete sets. This shows that, in spite of the radically different origins and attempted simplification of these sets, all the known $NP$ complete sets are identical but for simple isomorphic codings computable in deterministic polynomial time. Furthermore, if all $NP$ complete sets are p-isomorphic then they all must have similar densities and, for example, no language over a single letter alphabet can be $NP$ complete, nor can any sparse language over an arbitrary alphabet be $NP$ complete. We show that complete sets in EXPTIME and EXPTAPE cannot be sparse and therefore they cannot be over a single letter alphabet. Similarly, we show that the hardest context-sensitive languages cannot be sparse. We also relate the existence of sparse complete sets to the existence of simple combinatorial circuits for the corresponding truncated recognition problem of these languages.

If all NP complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then P @@@@ NP and if all PTAPE complete sets are p-isomorphic then P @@@@ PTAPE. We show that all NP complete sets known (in the literature) are indeed p-isomorphic and so are the known PTAPE complete sets. Thus showing that, inspite of the radically different origins and attempted simplification of these sets, all the known NP complete sets are identical but for polynomially time bounded permutations.

In this note we show that the tape bounded complexity classes of languages over single letter alphabets are closed under complementation. We then use this result to show that there exists an infinite hierarchy of tape bounded complexity classes of sla languages between log n and log log n tape bounds. We also show that every infinite sla language recognizable on less than log n tape has infinitely many different regular subsets, and, therefore, the set of primes in unary notation, P, requires exactly log n tape for its recognition and every infinite subset of P requires at least log n tape.

In this paper we consider classes of Goedel numberings, viewed as simple models for programming languages, into which all other Goedel numberings can be translated by computationally simple mappings. Several such classes of Goedel numberings are defined and their properties are investigated. For example, one such class studied is the class of Goedel numberings into which all other Goedel numberings can be translated by finite automata mappings. We also compare these classes of Goedel numberings to the class of optimal Goedel numberings and show that translation into optimal Goedel numberings can be computationally arbitrarily complex, thus indicating that from a computer science point of view, optimal Goedel numberings have undesirable properties.

The purpose of this paper is to give a model for the study of quantitative problems about formal translations from one programming language into another, as well as derive some initial results about the speed of programs produced by translations. The paper also contains a new speed-up result which shows that in any computational complexity measure there exist functions which have arbitrarily large speed-ups but that the size of the speed-up programs must grow non-computably fast.

The purpose of this paper is to outline the theory of computational complexity which has emerged as a comprehensive theory during the last decade.This theory is concerned with the quantitative aspects of computations and its central theme is the measuring of the difficulty of computing functions.The paper concentrates on the study of computational complexity measures defined for all computable functions and makes no attempt to survey the whole field exhaustively nor to present the material in historical order.Rather it presents the basic concepts, results, and techniques of computational complexity from a new point of view from which the ideas are more easily understood and fit together as a coherent whole.

Although considerable progress has been made in the understanding of the more "algebraic" properties of context-free languages, the quantitative aspects of the recognition and parsing of context- free languages are still far from well understood. It was shown by Kasami and Younger that for every context-free language there exists a multitape Turing machine which recognizes this language and uses no more than n3operations to process input words of length n. For one-tape Turing machines Hartmanis showed, using the Younger algorithm, that every context-free language can be recognized in n5operations. This result has now been improved in the paper under review. It is shown, by a careful implementation of the Torii–Kasami–Ozaki algorithm on a one-tape Turing machine, that every context-free language can be recognized in n4operations. Again, just like for the n3operation multitape result, it is not known how good this time bound is. On the other hand, the authors have been able to show in this paper that for linear context-free languages n2is the least-upper time bound for their recognition on one-tape Turing machines. This is done by showing that every linear language is n2-recognizable, and by recalling that there are linear languages whose recognition requires n2 operations on a one-tape machine.

Some general results about hierarchies of undecidable problems in automata theory are given, and studies are described which show how properties of sets accepted by automata (i.e. languages) change from decidable to undecidable problems as the computational power of the automata is increased. This work also yields unified techniques which characterize for different languages large classes of undecidable problems.

The quantitative aspects of one-tape Turing machine computations are considered. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of nonregular sets of sequences. It is shown that the computation time can be used to characterize the complexity of recursive sets of sequences, and several results are obtained about this classification. These results are then applied to the recognition speed of context-free languages and it is shown, among other things, that it is recursively undecidable how much time is required to recognize a nonregular context-free language on a one-tape Turing machine. Several unsolved problems are discussed.

A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of the set of primes can be accepted by a pushdown or finite automaton. In view of this result an interesting open problem is to determine the “weakest” automaton which can accept the set of primes. It is shown that the linearly bounded automaton can accept the set of primes, and it is conjectured that no automaton whose memory grows less rapidly can recognize the set of primes. One of the results shows that if this conjecture is true, it cannot be proved by the use of arguments about the distribution of primes, as described by the Prime Number Theorem. Some relations are established between two classical conjectures in number theory and the minimal rate of memory growth of automata which can recognize the set of primes.

The purpose of this note is to show that it is recursively undecidable how much tape is required by a Turing machine to recognize nonregular context-free languages.

In this note we define the amount of feedback in a realization of a sequential machine M, give a simple algorithm to compute the minimal amount of feedback which has to be present in any realization of M, and give a canonical realization of M which uses the minimal amount of feedback.

This paper describes two tests for the existence of a linear state assignment for binary input sequential machines. The first test is based on ``transfer sequences'' which map one stationary state of a machine onto another stationary state. It is shown that from a minimal transfer sequence of a machine one can read off directly a linear assignment of this machine if one exists. The second test uses ``ignorance'' computations by means of partitions and previously developed results about sequential machine structure.

Results on the Structure of Sequential Machines* J. t[AItTMANIS (;e~zera~' EZec~ric Research Laboratory, Schenecl(ulf/

The object of this paper is to study feedback in sequential machines, to classify (according to their seriousness) and analyze errors which arise in the state transitions of machines, and to establish some relations between feedback and errors. It is shown that the previously developed algebraic methods1,2 supply the necessary tools and a rigorous basis for this theory, and relate these new results to previously obtained results about the structure of sequential machines. For example, this work yields the necessary methods to detect the existence of a decomposition of machines into component machines so that the most ``serious'' errors of the computation can occur only in an isolated component machine. This leads to the possibility of imposing selectively different reliability conditions on the component machines to achieve high over-all reliability of the realizations.

Some sequential machinies contain input-independent parts and can therefore be input-inependent machine (an autonomous clock) and an input-dependent machine. Necessary and sufficient conditions on the flow table are obtained for the existence of autonomous clocks in sequential machines, and the properties of these machines and their clocks are studied.

In this paper, the problem of determining economical state assignments for finite-state sequential machines is studied. The fundamental idea in this study is to find methods for selection of these assignments in which each binary variable describing the new state depends on as few variables of the old state as possible. In general, these variable assignments in which the dependence is reduced yield more economical implementation for the sequential machine than the assignments in which the dependence is not reduced. The main tool used in this study is the partition with the substitution property on the set of states of a sequential machine. It is shown that for a sequential machine the existence of assignments with reduced dependence is very closely connected with the existence of partitions with the substitution property on the set of states of the machine. It is shown how to determine these partitions for a given sequential machine and how they can be used to obtain assignments with reduced dependence.

The object of this paper is to find state assignments for the internal states of a sequential machine such that the logical equations representing the machine are relatively simple. This is done by finding assignments for which the computation of a particular state variable depends only on the previous values of a small subset of the variables. The chief tool is the concept of a partition pair, which describes (loosely speaking) the information going into and resulting from the evaluation of a state variable. A necessary and sufficient condition for the existence of assignments with reduced dependence is found in terms of these pairs, and their algebraic properties are worked out so that they can be handled and generated. It is shown that the same methods can also be used to find input and output assignments with reduced dependence. The case of ``don't care'' conditions is considered and the theory is seen to apply, except that the failure of an algebraic property makes it weaker.