<p>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 <i>do</i> know various separations between complexity classes, like P&ne;EXP, MA<sub>EXP</sub>&nsub;P/poly, NEXP&nsub;ACC, etc.  So, if you believe that a particular separation, like P&ne;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 <i>that</i> 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.</p>

<p>But to address your question anyway: well, the obvious challenge in answering is to find <b>any</b> 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 <i>equivalent</i> 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))&ne;NTIME(f(n)) for f(n)&le;n log*n, since NTIME(f(n)) can simulate time <i>slightly</i> greater than f(n)).  (An earlier version of this post claimed that was known for <i>all</i> 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.</p>

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

CC BY-SA 3.0
2013-04-08T01:47:46.967Z
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 ("http://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!"
John Sidles
CC BY-SA 3.0
2013-04-08T02:20:52.757Z
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
Scott Aaronson
CC BY-SA 3.0
2013-04-08T14:49:51.910Z
Thank you Ryan Williams, for your crucial correction to Scott's original answer.  The original question's "Further Update" sorts through the implications.
John Sidles
CC BY-SA 3.0
2013-05-06T18:53:22.267Z
your answer has been "accepted".  Also, congratulations on all the good things that have happened your life this past year... marriage, a child, promotion!
John Sidles
CC BY-SA 3.0
2013-04-07T22:57:36.187Z
2013-04-08T14:20:25.860Z
2013-04-08T14:20:25.860Z
Scott Aaronson
<p><strong>Accepted Answer</strong></p>

<p>Scott Aaronson's answer has been "accepted" (mainly because it's the <em>only</em> answer!)</p>

<p><strong>One-sentence summary of answer</strong>&nbsp; Plausibly natural generalizations of the P versus NP question are not obviously easier to resolve than P versus NP itself.</p>

<p><strong>One obstruction to a general answer</strong>&nbsp; The original question assumed that every complexity class A associates "naturally" to a nondeterministic generalization NA&nbsp;&mdash; 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 <em>and</em> manifestly natural specification.</p>

<p><strong>However&nbsp;&hellip;</strong>&nbsp; dkuper's comment (<a href="https://cstheory.stackexchange.com/questions/17187/do-natural-generalizations-of-pversusnp-exist#comment45494_17187">below</a>) provides a link to a talk by by Christos Kapoutsis (LIAFA), titled <a href="http://www.liafa.univ-paris-diderot.fr/web9/manifsem/description_fr.php?idcongres=1225" rel="nofollow noreferrer"><em>Minicomplexity</em></a>, that describes a research strategy along the lines indicated.</p>

<p>For further discussion, a recommended resource is the Dick Lipton/Ken Regan <em>G&ouml;del's Lost Letter and P=NP</em> essay titled <a href="http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little" rel="nofollow noreferrer"><em>We Believe A Lot, But Can Prove Little.</em></a></p>

<hr>

<p><strong>The question finally asked</strong></p>

<blockquote>
  <p><strong>The question</strong>&nbsp; What trait shared by every complexity class A ⊂ P that is richer than NTIME(n ln n), acts to obstruct proofs of A ⊂ NA?</p>
</blockquote>

<p>This question was motivated by <a href="http://www.scottaaronson.com/blog/?p=1293#comment-68939" rel="nofollow noreferrer">Scott Aaronson's recent weblog comments</a> (see below), and the complexity-theoretic richness of this question has subsequently been illuminated by comments/answers/essays by <a href="https://cstheory.stackexchange.com/questions/17187/aaronsons-extended-question-do-natural-generalizations-of-pversusnp-exist#comment44726_17187">Robin Kathari</a>, <a href="https://cstheory.stackexchange.com/a/17189/1519">Scott Aaronson</a>, <a href="https://cstheory.stackexchange.com/questions/17187/aaronsons-extended-question-do-natural-generalizations-of-pversusnp-exist#comment44762_17189">Ryan Williams</a>, <a href="http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little" rel="nofollow noreferrer">Dick Lipton and Ken Regan</a>, and <a href="https://cstheory.stackexchange.com/q/1079/1519">previous <em>TCS StackExchange</em> questions</a>.</p>

<blockquote>
  <p><b>Observations</b>&nbsp; (1)&nbsp;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)&nbsp;the reason(s) for this near-universal complexity-theoretic obstruction are not presently well-understood.</p>
</blockquote>

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

<hr>

<p><strong>The question originally asked</strong></p>

<p>On his weblog <em>Shtetl Optimized</em>, Scott Aaronson <a href="http://www.scottaaronson.com/blog/?p=1293#comment-68939" rel="nofollow noreferrer">issued the following TCS challenge</a>: </p>

<blockquote>
  <p><strong>The <em>Shtetl Optimized</em> TCS Challenge</strong>&nbsp;&nbsp; <em>If</em> you believe P vs. NP is undecidable, then you need to answer:</p>
  
  <p><strong>The <em>Shtetl Optimized</em> TCS Question</strong>&nbsp;&nbsp; Why does whatever intuition tells you that [<em>P&nbsp;vs&nbsp;NP is undecidable</em>] 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? </p>
  
  <p>(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.)</p>
</blockquote>

<p>Answers to the following specific question will be accepted:</p>

<blockquote>
  <p><strong>Q1</strong> <em>(TCS literature question)</em>&nbsp;&nbsp; Do any known complexity classes A and B provably satisfy A&nbsp;&sub;&nbsp;B and NA&nbsp;&supe;&nbsp;B, for NA the natural non-deterministic extension of A?</p>
</blockquote>

<p>Supposing that the answer to <strong>Q1</strong> is "yes", an explanation is desired of how it happens that the strict inclusion A&nbsp;&sub;&nbsp;B has been proved, while the (superficially similar) strict inclusion P&nbsp;&sub;&nbsp;NP is hard to prove.</p>

<p>Alternatively, if the answer to <strong>Q1</strong> is "no", one further question is asked:</p>

<blockquote>
  <p><strong>Q2</strong> (<em>The Extended</em> Shtetl Optimized <em>TCS Question</em>)&nbsp;&nbsp; Are complexity-class inclusions of the general form A&nbsp;&sub;&nbsp;B and NA&nbsp;&supe;&nbsp;B provable&nbsp;&mdash; in ZFC or any finite extension of ZFC&nbsp;&mdash; for any "natural" complexity classes whatsoever? (if "yes" construct examples; if "no" prove the obstruction).</p>
</blockquote>

<hr>

<p><strong>PostScript</strong>&nbsp; &nbsp;Appreciation and thanks are extended to <em>TCS StackExchange</em> for sustaining this wonderfully inspiring and helpful mathematical community, and to Scott Aaronson for sustaining his admirable weblog <em>Shtetl Optimized!</em></p>

CC BY-SA 3.0
2013-04-07T23:03:12.173Z
Isn't Q1 equivalent to the existence of a class A such that A is strictly contained in the non-deterministic version of A?
Robin Kothari
CC BY-SA 3.0
2013-04-07T23:05:22.513Z
Yep. :-)  (And my answer below took advantage of that.)
Scott Aaronson
CC BY-SA 3.0
2013-04-08T01:24:01.613Z
As my own thinking has evolved, please refer to the "Further Update" that now begins the question.  My thanks to all *TCS StackExchange* participants.
John Sidles
CC BY-SA 3.0
2013-05-06T13:29:56.680Z
I don't know if it is in the range of your question, but you might be interested by the following: http://www.liafa.univ-paris-diderot.fr/web9/manifsem/description_fr.php?idcongres=1225
Denis
CC BY-SA 3.0
2013-05-06T21:16:32.270Z
-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!
Huck Bennett
CC BY-SA 3.0
2013-05-06T22:34:37.597Z
Huck suggests "If you have a follow-up question, ask it separately" ... That is a good suggestion, Huck!  As it turns out, I am composing *two* follow-up questions, that seek to formalize the above question via "pullback", specifically, pullback onto (a) languages for which [ZFC provides certificates of class-membership](http://rjlipton.wordpress.com/2013/04/24/can-we-prove-better-independence-theorems/#comment-36450), and (b) computational state-spaces for which algebraic geometry provides certificates of thermodynamic/informatic consistency. Thank you for your suggestion!
John Sidles
CC BY-SA 3.0
2013-05-07T01:34:58.223Z
Thank you dkuper ... the (very interesting) link that you supplied, to Christos Kapoutsis' talk, has been added to the summary of the question.
John Sidles
CC BY-SA 3.0
2013-05-07T15:50:33.627Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2013-05-08T14:39:38.117Z
Niel, I will attempt an editing pass in the next week or so ... it will take awhile to assimilate the implications of the link that Christos Kapoutsis supplied.  Even the edited question will (most likely) not be entirely satisfactory ... for the common-sense reason, that posing these questions in forms that are natural, rigorous, concise, and amenable to proof, is comparably difficult to answering them.
John Sidles
CC BY-SA 3.0
2013-05-08T14:54:08.600Z
Neil, per your request, the question/answer are now edited with a view to improved concision and rigor.  Thanks!
John Sidles
<cc.complexity-theory><decidability>
Do natural generalizations of P versus NP exist?
John Sidles
# Do natural generalizations of P versus NP exist?

(Asked by: username_0 on 2013-04-07)

**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](https://cstheory.stackexchange.com/questions/17187/do-natural-generalizations-of-pversusnp-exist#comment45494_17187)) provides a link to a talk by by Christos Kapoutsis (LIAFA), titled [*Minicomplexity*](http://www.liafa.univ-paris-diderot.fr/web9/manifsem/description_fr.php?idcongres=1225), 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.*](http://rjlipton.wordpress.com/2011/01/19/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](http://www.scottaaronson.com/blog/?p=1293#comment-68939) (see below), and the complexity-theoretic richness of this question has subsequently been illuminated by comments/answers/essays by [Robin Kathari](https://cstheory.stackexchange.com/questions/17187/aaronsons-extended-question-do-natural-generalizations-of-pversusnp-exist#comment44726_17187), [Scott Aaronson](https://cstheory.stackexchange.com/a/17189/1519), [Ryan Williams](https://cstheory.stackexchange.com/questions/17187/aaronsons-extended-question-do-natural-generalizations-of-pversusnp-exist#comment44762_17189), [Dick Lipton and Ken Regan](http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little), and [previous *TCS StackExchange* questions](https://cstheory.stackexchange.com/q/1079/1519).

> **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](http://www.scottaaronson.com/blog/?p=1293#comment-68939):

> **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!*

**Tags:** cc.complexity-theory, decidability
> **Comments:**
> **username_1**: Isn't Q1 equivalent to the existence of a class A such that A is strictly contained in the non-deterministic version of A?  
> **username_2**: Yep. :-)  (And my answer below took advantage of that.)  
> **username_0**: As my own thinking has evolved, please refer to the "Further Update" that now begins the question.  My thanks to all *TCS StackExchange* participants.  
> **username_3**: I don't know if it is in the range of your question, but you might be interested by the following: http://www.liafa.univ-paris-diderot.fr/web9/manifsem/description_fr.php?idcongres=1225  
> **username_4**: -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!  
> **username_0**: Huck suggests "If you have a follow-up question, ask it separately" ... That is a good suggestion, Huck!  As it turns out, I am composing *two* follow-up questions, that seek to formalize the above question via "pullback", specifically, pullback onto (a) languages for which [ZFC provides certificates of class-membership](http://rjlipton.wordpress.com/2013/04/24/can-we-prove-better-independence-theorems/#comment-36450), and (b) computational state-spaces for which algebraic geometry provides certificates of thermodynamic/informatic consistency. Thank you for your suggestion!  
> **username_0**: Thank you dkuper ... the (very interesting) link that you supplied, to Christos Kapoutsis' talk, has been added to the summary of the question.  
> **username_5**: 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.  
> **username_0**: Niel, I will attempt an editing pass in the next week or so ... it will take awhile to assimilate the implications of the link that Christos Kapoutsis supplied.  Even the edited question will (most likely) not be entirely satisfactory ... for the common-sense reason, that posing these questions in forms that are natural, rigorous, concise, and amenable to proof, is comparably difficult to answering them.  
> **username_0**: Neil, per your request, the question/answer are now edited with a view to improved concision and rigor.  Thanks!  

---

## 1 answers

### Answer by username_2 on 2013-04-07. Score: 15 | Accepted answer

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!]

> **Comments:**
> **username_0**: 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 ("http://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!"  
> **username_2**: 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  
> **username_0**: Thank you Ryan Williams, for your crucial correction to Scott's original answer.  The original question's "Further Update" sorts through the implications.  
> **username_0**: your answer has been "accepted".  Also, congratulations on all the good things that have happened your life this past year... marriage, a child, promotion!  

---

