# Do natural generalizations of P versus NP exist?

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  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.

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!

• Isn't Q1 equivalent to the existence of a class A such that A is strictly contained in the non-deterministic version of A? Apr 7 '13 at 23:03
• Yep. :-) (And my answer below took advantage of that.) Apr 7 '13 at 23:05
• I don't know if it is in the range of your question, but you might be interested by the following: liafa.univ-paris-diderot.fr/web9/manifsem/… May 6 '13 at 13:29
• -1: After the perfectly good answer below, it seems that you edited the question 15 times, changing it so that the answer is no longer valid before adding the patronizing note "[the answer] has been 'accepted' (mainly because it's the only answer!)." If you have a follow-up question ask it separately! May 6 '13 at 21:16
• John, could you please revise this so that it is somewhat more concise, and so that the "Further Developments" do not appear at the beginning of the post? I find such posts difficult to read, and perhaps the follow-up discussion should be reserved as motivation for the follow-up questions which you will hopefully be writing. May 7 '13 at 15:50