Randomness and completeness in computational complexity (Q1591868)

The text is a revised version of the author's Ph.D. thesis, which was written at the University of Chicago with Lance Fortnow as the thesis advisor and has been honored by the 1999 ACM Doctoral Dissertation Award. Most of the results obtained have also been published elsewhere, partially with co-authors, see the introduction and the Zentralblatt-reviews cited below. The thesis is about complexity theory, with a focus on the role of randomness and on techniques for separating complexity classes. The main tools used are the concepts of sparseness and autoreducibility, as well as techniques from resource-bounded measure theory. In Chapter 2, the author reviews models of computation, reducibilities, and resource-bounded measure and discusses the role of randomness in computational complexity. For further use, recall that the complexity classes E and EXP contain exactly the sets that can be decided in linear and polynomial exponential time, respectively, and that a class of sets has E-measure 0 (has EXP-measure 0) if there is a betting strategy that succeeds on every set in the class and is computable in linear (in polynomial) exponential time. Unless explicitly stated otherwise, all reducibilities mentioned in the sequel are restricted to polynomial time. Chapter 3 is about the derandomization of Arthur-Merlin games and other randomized computation models [see also \textit{Klivans} and \textit{D. van Melkebeek}, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. ACM Symposium on the Theory of Computing, 659-667 (1999)]. The derandomization results are obtained by extending known hardness versus randomness results to a setting of relativized computations. The main results assert that certain hardness assumptions are sufficient for derandomizing Arthur-Merlin games and for obtaining subexponential size proofs for graph nonisomorphism. Furthermore, the author discusses the derandomization of the Valiant-Vazirani hashing procedure and of other randomized processes. Chapter 4 deals with the question of whether languages that are hard for certain complexity classes under appropriate reducibilities can be sparse, i.e., may contain at most a polynomial number of the exponentially many words of each length [see also \textit{D. van Melkebeek}, Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets. J. Comput. Syst. Sci. 57, 213-232 (1998; Zbl 0921.68030)]. Among other results, the author shows that with respect to bounded truth-table reductions computable in logarithmic space, sparse sets cannot be hard for the class P of sets computable in polynomial time unless P coincides with L, the class of sets computable in logarithmic space. Chapter 5 features the concept of an autoreducible set and its application for separating complexity classes [see also \textit{H. Buhrman, L. Fortnow, D. van Melkebeek} and \textit{L. Torenvliet}, Separating complexity classes using autoreducibility. SIAM J. Comput. 29, 1497-1520 (2000; Zbl 0949.68068)]. A set is autoreducible if it can be reduced to itself while never querying the oracle at the current input. Among others, the following results on autoreducibility are shown. For reducibilities of Turing type, any set that is complete for EXP or for a level \(\Delta_{k}^{\text{ exp}}\), \(k > 0\), of the exponential time hierarchy is always autoreducible, while there is a set that is complete for doubly exponential space and is not autoreducible. Similarly, with respect to reducibilities of truth-table type, any set that is complete for a level \(\Delta_{k}\), \(k > 0\), of the polynomial time hierarchy is autoreducible, while there is a complete set for exponential space that is not. From these results known separations of the complexity classes involved are immediate. The author argues that for several other pairs of a complexity class and a reducibility it appears to be hard to answer the question of whether the corresponding complete languages are all autoreducible because both a positive or a negative answer would yield major new results about the separation of complexity classes. Chapter 6 investigates into the resource-bounded measure of BPP, the class of sets decidable in probabilistic polynomial time with bounded-error [see also \textit{D. van Melkebeek}, The zero-one law holds for BPP. Theor. Comput. Sci. 244, 283-288 (2000; Zbl 0945.68057)]. The author uses a result by Impagliazzo and Wigderson in order to show that if the class BPP differs from EXP at all, then it has E-measure 0. Furthermore, this assertion remains valid with BPP replaced by any subclass of BPP (and not superclass of BPP, as stated erroneously in the abstract of the corresponding journal article Zbl 0945.68057) that is closed under reductions of truth-table type. The main result of Chapter 7 is a Small Span Theorem for reducibilities of truth-table type that are restricted to \(n^{o(1)}\) queries on inputs of length \(n\) [see also \textit{H. Buhrman} and \textit{D. van Melkebeek}, Hard sets are hard to find. J.~Comput. Syst. Sci. 59, 327-345 (1999; Zbl 0947.68067)]. The Small Span Theorem asserts that for any set A, at least one of the following classes has EXP-measure 0: the class of sets in EXP that are reducible to A or the class of sets to which A can be reduced. The Small Span Theorem is shown by first proving that for reductions of truth-table type that are restricted to~\(n^{\alpha}\) queries for some \(\alpha < 1\), the sets in EXP that can be reduced to a class of EXP-measure different from 0 form a class of E-measure 0. Another consequence of the latter result is that for such reducibilities the degree of a set in EXP always has EXP-measure 0. Furthermore it is shown that for any fixed constant \(c\), the class of sets that are complete for EXP under reductions restricted to \(n^c\) queries has EXP-measure \(0\), and likewise the class of sets that are complete for E with respect to reductions restricted to \(cn\) queries has E-measure 0. Chapter 8 introduces the concept of betting game and its relation to the question whether EXP coincides with its subclass BPP [see also \textit{H. Buhrman, D. van Melkebeek, K. W. Regan, D. Sivakumar} and \textit{M. Strauss},, A generalization of resource-bounded measure, with application to the BPP vs. EXP problem. SIAM J. Comput. 30, 576-601 (2000; Zbl 0963.68230)]. While with betting strategies the bets have to be placed in the natural order, this is not required for betting games. In a setting of reductions of Turing type, the following results are obtained. The class of autoreducible sets has measure 0 with respect to E-betting games and, by results in Chapter 5, contains all sets that are complete for EXP. On the other hand, by a result of Allender and Strauss, the class of sets that are complete for BPP can not have measure 0 with respect to E-betting strategies. Thus a separation of EXP and BPP would follow if E-betting strategies and E-betting games were equivalent, and a couple of other conditions implying this separation are obtained by similar arguments. Analogous results are shown for reductions of truth-table type and betting games that are nonadaptive, i.e., where the place on which the next bet is put does not depend on the outcomes of the bets already made. Furthermore, it is argued that E-betting games and E-betting strategies are equivalent in case in case certain pseudo-random generators exist and the equivalence of EXP-betting games and EXP-betting strategies follows from similar but apparently slightly weaker assumptions. Finally it is shown that the class of sets that are autoreducible by truth-table reductions has E-measure 0 in case EXP differs from MA, the class of sets that can be recognized by interactive proof systems of Merlin-Arthur type.