Grant Proposal: Interactive Models, Proof Models and Exponential Time

Sarah Easton Mocas Portland State University Portland, Oregon 97207

1 Overview

A primary focus of structural complexity theory is showing that a class contains a language which in fact can not be computed with less resources. In this way complexity classes are shown to be distinct or separate. Intuitively, increasing the amount of resources should allow us to recognize more languages. In fact various separation results are known between nondeterministic time classes [Coo73, SFM73, BG70] and between deterministic time classes [HS65]. Although of great practical interest, separations between nondeterministic and deterministic classes of the same time complexity have not been proved. This proposal outlines an approach which we believe will be useful in separating exponential time-bounded classes from lower complexity classes.

Problems for which there is no known solution in polynomial time; i.e., no known efficient solution, are considered to be intractable^{1}. These problems have been broadly categorized as exponential time problems even though this includes problems in subexponential classes such as T IME(n^{log n}) [GJ79]. Our proposed research will focus on the exponential time classes EXP, NEXP and classes in the related exponential time hierarchy, EXP H. It should be noted that there are several different ways to define exponentially time-bounded classes. In this proposal EXP will be used to refer to the set of languages in DT IME(2^{p(n)}), where p is a polynomial, and NEXP will be used to refer to the set of languages in NT IME(2^{p(n)}). Likewise, E, (NE) will be used to refer to the set of languages in DT IME(2^{cn}), (NT IME(2^{cn})) respectively, where c is any constant. The following containments are known:

P ⊆ NP ⊆ P H ⊆ P SP ACE ⊆ EXP ⊆ NEXP

1In different parts of the literature problems in both P, deterministic polynomial time, and BP P, the class of languages recognized by polynomial time probabilistic Turing machines whose error is bounded above by some positive constant ϵ < 1/2 , have been considered tractable.

where P H is the polynomial time hierarchy and P SP ACE refers to the set of languages in SP ACE(p(n)). By time hierarchy theorems, the following proper containments are known [HS65, HLS65, Coo73, Moc96]:

P ⊂ E ⊂ EXP and NP ⊂ NE ⊂ NEXP and P^{NP [n^{c}]} ⊂ NEXP.

The last result improves the separation NP ⊂ NEXP since NP ⊆ P^{NP [n^{c}]} ⊂ NEXP ^{2}. Surprisingly, with the exception of the last statement, proofs of the above separations results date from early work in complexity theory and have not been improved. Many interesting questions, one of which is the proper containment of NP in EXP, are still open and appear to be difficult to prove.

Relativized results are used as a tool to indicates the difficulty of resolving a proposition in the unrelativized case. Intuitively, if a relationship between two sets is known, for example, A ≠ B, then allowing machines which compute the membership of each set to have access to an additional resource should not change the inequality relationship. So if machines for recognizing elements in A and B have access to a resource that decides membership for a set C, then A^{C} ≠ B^{C} should be true. C in this contexts is roughly used as an oracle set. A complexity theoretical statment relativizes if the truth of the statement remains unchanged in the presents of any oracle set. In general, the proof techniques which have traditionally been used in complexity theory relativize. For example, the statement NP ≠ NEXP relativizes since NP^{A} ≠ NEXP^{A} for any set A used as an oracle, but the statement P ≠ NP does not relativize since there is an oracle such that relative to that set P ≠ NP and a different oracle such that relative to it P = NP [BGS75]. Many of the central questions in complexity theory have results which are optimal with respect to relativization. For example, it is known that P^{NP [n^{c}]} ⊂ NEXP, for any fixed constant c, [Moc93, Moc96] and that this result can not be improved using proof techniques which relativize [BT93]. In other words, Buhrman and Torenvliet show that there is an oracle set relative to which P^{NP [poly]} = NEXP. An oracle relative to which these classes are not equal is easily constructed using a NEXP -complete set as an oracle. To make head-way in answering many of the open questions in structural complexity, proof techniques which do not relativize are needed. Please see section 3.1.2 for a brief review of oracle results that relate specifically to exponential time classes and the proposed research.

In the last few years, results using non-relativizing proof techniques have appeared [Sha90, BFL90, ALM^{+}92]. The introduction of non-relativizing proof techniques holds great promise that some of the current fundamental questions, which are known not to have relativizing proofs, can be resolved. Unfortunately this has not happened to date. Never the less, these proof techniques form an important first step in this direction. Our intention is to investigate exponential time classes defined via models which are shown, using nonrelativizing proof techniques, to encompass standard complexity classes. Specifically we propose to characterize classes in the exponential time hierarchy in terms of these models with the intention of showing separations using these characterizations. Note that NEXP has already been characterized via two probabilistic models, since NEXP = MIP [BFL90] and NEXP = P CP (poly, poly) [ALM^{+}92]. Multiple interactive proofs, MIP, characterizes NEXP via two prover interactive proof systems and the probabilisticly checkable proof model, P CP, uses random access to a fixed proof (with no interaction). EXP SP ACE has also been characterized as a probabilistic game [FT95]. We propose using the characterization for EXPSPACE in terms of a probabilistic game (as given in [FT95] ) to characterize classes in the exponential time hierarchy in the same manner in which probabilisticly checkable debate systems, PCD’s, were used to characterize the levels of the polynomial hierarchy [CFS94, KLR^{+}94]. It is our hope that an examination of non-relativizing proof techniques in a different environment; i. e., high time classes, will give some intuition as to their strengths and weaknesses.

2P^{NP [f(n)]} is the set of all languages computed deterministically by a polynomial time-bounded oracle Turing machine which, on input x, makes at most O(f(|x|)) queries to an NP set. For example, optimization versions of many problems in NP are complete for P^{NP [log]} or P^{NP [poly]} [Kre88] .

The P CD model is closely related to the alternating Turing machine model of [CS76]. The proof of the collapse of the polynomial time hierarch, under the assumption that P = NP, is closely tied to Stockmeyer’s definition of the polynomial time hierarchy via alternating universal and existential quantifiers [Sto83]. This particular characterization can not be directly used to show that the exponential time hierarchy collapses under the similar assumption that EXP = NEXP. The exponential time hierarchy is most naturally defined via alternating Turing machines. Although there is a direct relationship between the alternating Turing machine model and the alternating quantifier model they are not interchangeable in the context of some proofs and specifically with regard to exponential time classes. It is for this reason there is interest in finding yet another way in which to define classes in EXP H. It is hoped that defining classes in EXP H via proof models will lead to new results about these classes.

There is strong justification for examining complexity classes that are not computationally feasible since resolving many of the open questions for high time/space classes implies similar results for corresponding lower classes. For example, it is known that if exponential time deterministic and nondeterministic classes are not equal then there are corresponding lower classes that are also not equal (see section 3.1.1 for details). So showing that EXP ≠ NEXP implies P ≠ NP. This particular exponential time problem is probably not structurally different form it’s polynomial counterpart but there are important open questions concerning exponential time classes where the classes involved appear to be structurally different from their polynomial time counterparts and yet answering such questions still implies corresponding results for lower time classes.

The structure of exponential time classes does not always mirror that of related polynomial time classes. Specifically, some of the techniques which are used to demonstrate results in the polynomial time hierarchy do not generalize to exponential time hierarchies. For one, it has not been shown that general downward separating results which apply to the polynomial time hierarchy can be duplicated in natural exponential time hierarchies. The exponential time hierarchy is not know to collapse under the assumption that EXP = NEXP where as the polynomial time hierarchy collapses under the assumption that P = NP. If, in fact, the exponential hierarchy were known to collapse under this assumption then it would easily follow that P H ⊂ NEXP which remains an open question. For this reason, we specifically propose to characterize classes in the exponential time hierarchy, EXP H, using probabilistic models in the hopes that this characterization can be used to show general separations. We do not anticipate that a probabilistic model for classes in EXP H will exactly mirror the probabilistic model which has been used to define classes in P H [KLR^{+}94].

In the process of studying exponential time classes and their relationship to polynomial time classes several interesting questions have come to the forefront. Specifically, the following questions have directly motivated this proposal.

Is P^{NP} properly contained in NEXP?

Is BP P properly contained in NEXP?

Does co−NEXP ⊆ NEXP imply that the exponential time hierarchy collapses?

None of these questions has been answered. A positive answer to the last question would separate NEXP from the polynomial time hierarchy, P H.

To summerize, our goal is two fold, we wish to study the structure of high time/space classes described via nonrelativizing models and also to show separations between exponential time classes and classes in the polynomial hierarchy using these characterizations. First we intend to see if the characterization for EXP SP ACE in terms of a probabilistic game (as given in [FT95] ) can be used to characterize classes in EXP H in the same manner in which PCD’s were used to characterize classes in P H [CFS94, KLR^{+}94]. Such a characterization will be studied to see a collapse of the exponential time hierarchy can be proved using this characterization and given an assumption, such as NEXP = EXP. We are interested in this since the collapse of EXP H to some level can be used to separate classes in EXP H from classes in the polynomial time hierarchy. Finally, we intend to study classes such as P CP (n^{c}, poly) and P CP_{EXP} (2^{n^{c}}, exp) to see if any of the standard complexity classes above P^{NP [n^{c}]} and EXP^{NP [poly]}, respectively, can be shown to be contained in these classes. If so this may give a new proper subset of NEXP.

Current work, done under NSF grant number CCR-9410713, gives an indication of the potential for this line of research. We show that, by considering the structure of the probabilistically checkable proof model, P CP, diagonalization can be used to separate the classes P CP (n^{c}, poly) and NEXP. This is of interest P CP (poly, poly) = NEXP and, further, showing any class to be in P CP (n^{c}, poly) would then show the proper inclusion of that class in NEXP. Proof of the following, unpublished theorem in included.

Theorem 1.1 For any fixed constant c, P CP (n^{c}, poly) is a proper subset of NEXP.

Since it has been shown that NEXP = P CP (poly, poly) we get as a corollary that for any fixed constant c, P CP (n^{c}, poly) ⊂ P CP (poly, poly). Clearly this implies NP ⊂ NEXP since NP = P CP (log, 1). The obvious questions is: Is there some class A which contains P^{NP [n^{d}]}, for a fixed d, and is in NEXP such that A ∈ P CP (n^{c}, poly)? This would give a new separation from NEXP. One possible class to consider is BP P since it is not know if BP P is a proper subset of NEXP or not.

The section called Preliminaries gives useful definitions. Section 3 contains a more detailed discussion of the points just mentioned in the overview. This includes a brief history of work previously done on this topic and an explanation of how the proposed work relates to previous work. The last part of section 3 includes several theorems and proofs that demonstrate directly the type of work proposed. These theorems are current work and as yet not submitted for publication.

References

[ALM^{+}92] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. 33th IEEE Symp. on the Foundations of Computer Sci., pages 14–23, 1992.

[BFL90] L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. In Proc. 31th IEEE Symp. on Foundations of Computer Sci., pages 26–35, 1990.

[BG70] R. Book and S. Greibach. Quasi-realtime languages. Math. Systems Theory, 4:97–111, 1970.

[BGS75] T. Baker, J. Gill, and R. Solovay. Relativization of the P=NP? question. SIAM Journal on Computing, 4:431–442, 1975.

[BT93] H. Buhrman and L. Torenvliet. On the cutting edge of relativization: The resource bounded injury method. Technical report, Dept. of Computer Science, University of Toronto, 1993.

[CFS94] A. Condon, J. Feigenbaum, and C. Lundand P. Shor. Probabilistic checkable debate systems and nonapproximability of PSPCAE-hard functions. Chicago Journal of Theoretical Computer Science, 1994. Submitted.

[Coo73] S. A. Cook. A hierarchy for nondeterministic time complexity. Journal of Computer and System Sciences, 7(4):343–353, 1973.

[CS76] A. K. Chandra and L. Stockmeyer. Alternation. In Proc. 17th IEEE Symp. on Foundations of Computer Sci., pages 98–108, 1976.

[FT95] H. Buhrman L. Fortnow and L. Torenvliet. Using autoreductions to separate complexity classes. In Proc. 36th IEEE Symp. on Foundations of Computer Sci., pages 520–527, 1995.

[GJ79] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.

[HLS65] J. Hartmanis, P. Lewis, and R. Stearns. Hierarchies of memory limited computation. In Proc. 6th IEEE Symp. on Switching Circuit Theory and Logical Design., pages 179–190, 1965.

[HS65] J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Trans. American Math. Society, 117:285–306, 1965.

[KLR^{+}94] M. Kiwi, C. Lund, A. Russell, D. Spielman, and R. Sundaram. Alternation in interaction. In Proc. 9th IEEE Struct. Complexity Theory Conf., pages 294–303, 1994.

[Kre88] M. Krentel. The complexity of optimization problems. Journal Computer Systems Sci., 36:490–509, 1988.

[Moc93] S. E. Mocas. Separating Exponential Time Classes From Polynomial Time Classes. PhD thesis, College of Computer Science , Northeastern University, September 1993.

[Moc96] S. E. Mocas. Separating classes in the exponential-time hierarchy from classes in PH. Theoretical Computer Science, 158:221–231, 1996.

[SFM73] J. I. Seiferas, M. J. Fischer, and A. R. Meyer. Refinements of nondeterministic time and space hierarchies. In Proc. 14th IEEE Symposium on Switching and Automata Theory, pages 130–137, 1973.

[Sha90] A. Shamir. IP = PSPACE. In Proc. 31st IEEE Symp. on Foundations of Computer Sci., pages 11–15, 1990.

[Sto83] L. Stockmeyer. The complexity of approximate counting. In Proc. 15th ACM Symp. on Theory of Computing, pages 118–126, 1983.