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!

  • 3
    $\begingroup$ Isn't Q1 equivalent to the existence of a class A such that A is strictly contained in the non-deterministic version of A? $\endgroup$ Apr 7, 2013 at 23:03
  • $\begingroup$ Yep. :-) (And my answer below took advantage of that.) $\endgroup$ Apr 7, 2013 at 23:05
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Denis
    May 6, 2013 at 13:29
  • 2
    $\begingroup$ -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! $\endgroup$ May 6, 2013 at 21:16
  • 1
    $\begingroup$ 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. $\endgroup$ May 7, 2013 at 15:50

1 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, MAEXP⊄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!]

  • 1
    $\begingroup$ Scott, a welcome reference would elucidate the oracular (and to me, non-obvious) declaration "It was proved in the 1970s that TIME(f(n))≠NTIME(f(n)), since NTIME(f(n)) can simulate time slightly greater than f(n)." The Complexity Zoo and Wikipedia provide little illumination, however at least one TCS StackExchange question ("cstheory.stackexchange.com/q/1079/1519") apparently suggests that the assertion is closely linked to CT problems that are deep and open. Summary "Oliver Twist is asking for further illumination, please!" $\endgroup$ Apr 8, 2013 at 1:47
  • 5
    $\begingroup$ OK, I guess it was the 80s: W. J. Paul, N. Pippenger, E. Szemerédi, and W. T. Trotter. On determinism versus nondeterminism and related problems, Proceedings of IEEE FOCS'83, pp. 429-438, 1983 $\endgroup$ Apr 8, 2013 at 2:20
  • $\begingroup$ Thank you Ryan Williams, for your crucial correction to Scott's original answer. The original question's "Further Update" sorts through the implications. $\endgroup$ Apr 8, 2013 at 14:49
  • 2
    $\begingroup$ your answer has been "accepted". Also, congratulations on all the good things that have happened your life this past year... marriage, a child, promotion! $\endgroup$ May 6, 2013 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.