Do natural generalizations of P versus NP exist?

Question

Accepted Answer

Scott Aaronson's answer has been "accepted" (mainly because it's the only answer!)

One-sentence summary of answer  Plausibly natural generalizations of the P versus NP question are not obviously easier to resolve than P versus NP itself.

One obstruction to a general answer  The original question assumed that every complexity class A associates "naturally" to a nondeterministic generalization NA — however a general complexity class A can be defined in so many ways, that the class-map N$\colon\,$A$\,\to\,$NA cannot (apparently) be readily given a completely general and manifestly natural specification.

However …  dkuper's comment (below) provides a link to a talk by by Christos Kapoutsis (LIAFA), titled Minicomplexity, that describes a research strategy along the lines indicated.

For further discussion, a recommended resource is the Dick Lipton/Ken Regan Gödel's Lost Letter and P=NP essay titled We Believe A Lot, But Can Prove Little.

---

The question finally asked

The question  What trait shared by every complexity class A ⊂ P that is richer than NTIME(n ln n), acts to obstruct proofs of A ⊂ NA?

This question was motivated by Scott Aaronson's recent weblog comments (see below), and the complexity-theoretic richness of this question has subsequently been illuminated by comments/answers/essays by Robin Kathari, Scott Aaronson, Ryan Williams, Dick Lipton and Ken Regan, and previous TCS StackExchange questions.

Observations  (1) For all known complexity classes A ⊂ P that are sufficiently large as to include NTIME(n ln n) ⊂ A, the problem A $\overset{?}{\subset}$ NA is open, and (2) the reason(s) for this near-universal complexity-theoretic obstruction are not presently well-understood.

Like many folks, I had long appreciated the immense difficulty of proving P ⊂ NP, but had not previously appreciated that proving A ⊂ NA is an open problem for (essentially) all computational complexity classes.

---

The question originally asked

On his weblog Shtetl Optimized, Scott Aaronson issued the following TCS challenge:

The Shtetl Optimized TCS Challenge   If you believe P vs. NP is undecidable, then you need to answer:

The Shtetl Optimized TCS Question   Why does whatever intuition tells you that [P vs NP is undecidable] not also tell you that the P versus EXP, NL versus PSPACE, MAEXP versus P/poly, TC0 versus AC0, and NEXP versus ACC questions are similarly undecidable?

(In case you don’t know, those are five pairs of complexity classes that have been proved different from each other, sometimes using very sophisticated ideas.)

Answers to the following specific question will be accepted:

Q1 (TCS literature question)   Do any known complexity classes A and B provably satisfy A ⊂ B and NA ⊇ B, for NA the natural non-deterministic extension of A?

Supposing that the answer to Q1 is "yes", an explanation is desired of how it happens that the strict inclusion A ⊂ B has been proved, while the (superficially similar) strict inclusion P ⊂ NP is hard to prove.

Alternatively, if the answer to Q1 is "no", one further question is asked:

Q2 (The Extended Shtetl Optimized TCS Question)   Are complexity-class inclusions of the general form A ⊂ B and NA ⊇ B provable — in ZFC or any finite extension of ZFC — for any "natural" complexity classes whatsoever? (if "yes" construct examples; if "no" prove the obstruction).

---

PostScript   Appreciation and thanks are extended to TCS StackExchange for sustaining this wonderfully inspiring and helpful mathematical community, and to Scott Aaronson for sustaining his admirable weblog Shtetl Optimized!

Answer 1

John, while your kind comments are appreciated, I confess that I don't understand how your question relates to the simple point I was making in the quoted remark. All I was saying was that we do know various separations between complexity classes, like P≠EXP, MA_EXP⊄P/poly, NEXP⊄ACC, etc. So, if you believe that a particular separation, like P≠NP, is "too deep to be either proved or disproved in ZF set theory" (or whatever), then it seems to me that the burden falls on you to explain why you think that separation has to be independent of ZF, while other separations turned out not to be. For this argument to have force, I see no necessity for the other separations to have the particular form you specified.

But to address your question anyway: well, the obvious challenge in answering is to find any complexity class A for which we can prove that A is strictly contained in NA, where NA is "the natural non-deterministic extension of A"! (Indeed, as Robin points out above, finding such an A is equivalent to answering your question as you've stated it.) And the only examples of such A's that I can think of are things like TIME(f(n)) (it was proved in the 1970s that TIME(f(n))≠NTIME(f(n)) for f(n)≤n log*n, since NTIME(f(n)) can simulate time slightly greater than f(n)). (An earlier version of this post claimed that was known for all f(n). Thanks to Ryan Williams for the correction!) So setting A=TIME(n) and B=NTIME(n) would indeed answer your question in the affirmative. A more "natural" example will probably need to await a breakthrough in complexity theory.

[Endnote: I wish to clarify that I didn't give things portentous names like "The Shtetl Optimized this or that"---those were Sidles's elaborations!]