<p>If an artificial example is really as good as a natural one, then I can indeed provide such an example!</p>

<p><b>Edit:</b> Furthermore, my example is "somewhat" less of a cheat than the one suggested by Ravi Boppana (where we take L to be the empty language if P = NP and the halting problem otherwise), in that I'll define the language L by giving a finite procedure to decide whether $x \in$ L for any input x.  At no point will deciding whether x&isin;L require solving an "unbounded" mathematical question such as P vs. NP.</p>

<hr>

<p>Without further ado: let $M_1, M_2, ...$ be an enumeration of polytime Turing machines.  For all $n$, let $M_{t(n)}$ be the lexicographically first $M_i$ that correctly decides 3SAT on all inputs of length $n$ or less.  Then define the language L as follows: for all inputs $x$ of size $n$, $x \in$ L if and only if the Turing machine encoded by $x$ halts in at most $n^{t(n)}$ steps when run on a blank tape.</p>

<p><b>Claim 1:</b> If P = NP, then L $\in$ P.</p>

<p><b>Proof:</b> If P = NP, then there's some fixed $M_i$ that solves 3SAT for all inputs; hence $t(n) \le i$ for all $n$. QED</p>

<p><b>Claim 2:</b> If P $\ne$ NP, then L $\notin$ P.</p>

<p><b>Proof:</b> If $t(n)$ increases without bound, then we can simply apply the Time Hierarchy Theorem. QED</p>

<p>Now, not only is L not in P assuming P $\ne$ NP: one presumes it wouldn't be in PH (or even PSPACE) either!</p>

<p>Incidentally, I wonder if anyone can improve the above construction, to get a language L which is in P if P = NP, but <i>provably</i> not in PH or PSPACE if P $\ne$ NP?</p>

CC BY-SA 3.0
2011-08-25T15:58:52.067Z
@Tyson Williams: Just in case you have not realized, please be very careful not to introduce an error when you edit a post by other users.  It was fortunate that Joe noticed it and corrected it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-08T19:03:02.597Z
Thanks!  I have not been able to modify the construction to make nonmembership to PH provable, but this is sufficient to convince me that adding the condition that L is decidable with a constructive proof of the decidability will not probably change the situation much.  Hmm.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-08T19:40:54.407Z
I will accept Ravi Boppana’s answer because his was the first to arrive, although I want to accept both because both gave me more understanding on the problem.  I hope that you understand….
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T00:08:06.413Z
Nice. This is a great answer.
Daniel Apon
CC BY-SA 3.0
2010-10-08T18:48:08.927Z
2011-08-22T08:29:29.330Z
2011-08-22T08:29:29.330Z
Scott Aaronson
<p>Answering Scott Aaronson's question, but a bit too long for a comment, here is a construction of a language $L$ such that $P = NP$ implies $L \in P$, but $P \neq NP$ implies $L \notin PH$.</p>

<p>Let $M_1, M_2, M_3, \dotsc$ and $t(n)$ be as in Scott's construction. We make it so that $L$ does not reduce to $\Sigma_{k} SAT$ for each $k$, but we only do this if $t(n) \to \infty$ (i.e. if $P \neq NP$). The construction proceeds in stages.  At stage $s=(i,j)$ (using some easily computable and easily invertible bijection $\Sigma^* \to \Sigma^* \times \Sigma^*$), we ensure that $M_i$ is not a many-one reduction from $L$ to $\Sigma_{j} SAT$.  Let $n_{s}$ be the least integer such that $t(n_{s}) > t(n_{s-1})$ (base case: $n_{0} = 1$).  If there is such an integer $n_{s}$, then set $L(1^{n_{s}}) = 1 - \Sigma_{k}SAT(M_{i}(1^{n_{s}}))$.  If there is no such integer $n_{s}$, we let $L$ be empty forever after.</p>

<p>If $P \neq NP$, then $t(n) \to \infty$ as $n \to \infty$, so there is always such an $n_{s}$, hence $L$ is not in $PH$.  If $P = NP$, then my $L$ is only finitely different from Scott's $L$, and hence is in $P$.</p>

CC BY-SA 2.5
2010-10-09T19:10:44.053Z
Thank you for your answer, but I am not sure if I understand the construction.  It seems to me that to compute $n_s$, it might be necessary to search indefinitely, and therefore it seems to me that we do not have an explicit algorithm for deciding the language L.  If we do not need an explicit algorithm, Ravi Boppana’s answer shows that there exists a language L such that P=NP⇒L∈P and P≠NP⇒L∉R (i.e., L is undecidable).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T22:12:28.577Z
@Tsuyoshi Ito: I don't think you have to compute $n_s$ given $s$ in order to decide L; all you have to do is, on input $1^n$, decide if $n$ is of the form $n_s$ for some $s$, and figure out which $s$ it is (if any).  Here's how: on input $1^n$, compute $t(n)$, and compute $t(m)$ for all $m < n$.  If there is an $m < n$ such that $t(n)=t(m)$, then $n$ is not $n_s$ for any $s$, so $L(1^n) = 0$.  Otherwise, figure out which stage $s$ corresponds to this $n_s$ (which can be done since you've computed all previous values of $t$) and then compute $L(1^n)$ as described in the answer.
Joshua Grochow
CC BY-SA 2.5
2010-10-08T19:47:38.717Z
2010-10-09T04:28:24.733Z
2010-10-09T04:28:24.733Z
Joshua Grochow
<p>Since you don't mind an artificial language, how about defining $L$ to be empty if P equals NP and to be the Halting Problem if P doesn't equal NP.  Okay, it's a bit of a cheat, but I think you'll need to rephrase the problem to avoid such cheats.  </p>

CC BY-SA 2.5
2010-10-08T18:42:59.727Z
Thanks, I see the point (define L={M: Turing machine M halts and P≠NP}).  Of course, this does not answer what I wanted to ask, but I guess that I have to think more to formulate the question which I wanted to ask correctly.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-08T18:05:32.733Z
2010-10-08T18:05:32.733Z
Ravi Boppana
<p><em>Edit</em>: As Ravi Boppana correctly pointed out in <a href="https://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-pnp/2033#2033">his answer</a> and Scott Aaronson also added another example in <a href="https://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-pnp/2035#2035">his answer</a>, the answer to this question turned out to be “yes” in a way which I had not expected at all.  First I thought that they did not answer the question I had <em>wanted</em> to ask, but after some thinking, these constructions answer at least one of the questions I wanted to ask, that is, “Is there any way to prove a conditional result ‘P=NP ⇒ <i>L</i>∈P’ without proving the unconditional result <i>L</i>∈PH?”  Thanks, Ravi and Scott!</p>

<hr>

<p>Is there a decision problem <i>L</i> such that the following conditions are both satisfied?</p>

<ul>
<li><i>L</i> is not known to be in the polynomial hierarchy.</li>
<li>It is known that P=NP will imply <i>L</i>∈P.</li>
</ul>

<p>An artificial example is as good as a natural one.  Also, although I use the letter “<i>L</i>,” it can be a promise problem instead of a language if it helps.</p>

<p><strong>Background</strong>.  If we know that a decision problem <i>L</i> is in the polynomial hierarchy, then we know that “P=NP ⇒ <i>L</i>∈P.”  The intent of the question is to ask whether the converse holds.  If a language <i>L</i> satisfying the above two conditions exists, then it can be thought of as an evidence that the converse fails.</p>

<p>The question has been motivated by Joe Fitzsimons’s interesting comment to my <a href="https://cstheory.stackexchange.com/questions/2021/consequences-of-p-fp/2028#2028">answer</a> to Walter Bishop’s question “<a href="https://cstheory.stackexchange.com/questions/2021/consequences-of-p-fp">Consequences of #P = FP</a>.”</p>

CC BY-SA 2.5
2011-03-14T11:14:07.193Z
See also related questions http://cstheory.stackexchange.com/questions/5399/why-doesnt-p-np-imply-p-ap-i-e-p-pspace and http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph
András Salamon
CC BY-SA 2.5
2010-10-08T17:43:25.450Z
Proving a universal negative is always hard(er), but I would be surprised if such a language existed. The Generalized Linial-Nisan Conjecture (if it had ended up true) wouldn't have implied what you're asking, I don't believe. It would've just meant that BQP wasn't contained in PH. If PH collapsed to P, BQP still wouldn't have been contained in P(H).
Daniel Apon
CC BY-SA 2.5
2010-10-08T19:41:54.670Z
@Philip: Yes, but I do not think that that changes the problem because we can usually convert a decision problem L to a class X of decision problems reducible to L.  At least that was my intent of asking this question in terms of decision problems.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-08T19:51:19.030Z
Maybe you want to require that the language $L$ be somehow close to PH, in addition to your current requirements?  Maybe, say, in PSPACE (although it's arguable how close PSPACE is to PH; see S. Fenner, S. Homer, M. Schaefer, R. Pruim. Hyper-polynomial hierarchies and the polynomial jump. Theoretical Computer Science. Volume 262 (2001), pp. 241-256 http://www.cse.sc.edu/~fenner/papers/hyp.pdf).  Or maybe you really do want to ask for a *natural* such language.
Joshua Grochow
CC BY-SA 2.5
2010-10-08T20:26:34.893Z
@Joshua: Thank you for the comment and the reference.  As stated in the update (revision 3), now I think I had asked the right question (contrary to what I added in revision 2).  I had wanted to know “Is there any way to prove a conditional result ‘P=NP ⇒ L∈P’ without proving the unconditional result L∈PH?”  For this purpose, the naturalness of the problem should not be required because once there is a proof method, it should apply equally to both natural and contrived examples.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-08T21:08:40.310Z
@Daniel: Thanks for the comment.  Yes, I thought that it would be surprising that such a language existed.  Now I _am_ surprised (see the answers)!
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T00:06:53.890Z
@Tsuyoshi, I'm quite surprised too. This was really informative for me!
Daniel Apon
<cc.complexity-theory><conditional-results><np><polynomial-hierarchy>
A decision problem which is not known to be in PH but will be in P if P=NP
Tsuyoshi Ito
# A decision problem which is not known to be in PH but will be in P if P=NP

(Asked by: username_0 on 2010-10-08)

*Edit*: As Ravi Boppana correctly pointed out in [his answer](https://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-pnp/2033#2033) and Scott Aaronson also added another example in [his answer](https://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-pnp/2035#2035), the answer to this question turned out to be “yes” in a way which I had not expected at all. First I thought that they did not answer the question I had *wanted* to ask, but after some thinking, these constructions answer at least one of the questions I wanted to ask, that is, “Is there any way to prove a conditional result ‘P=NP ⇒ *L*∈P’ without proving the unconditional result *L*∈PH?” Thanks, Ravi and Scott!

---

Is there a decision problem *L* such that the following conditions are both satisfied?

* *L* is not known to be in the polynomial hierarchy.
* It is known that P=NP will imply *L*∈P.

An artificial example is as good as a natural one. Also, although I use the letter “*L*,” it can be a promise problem instead of a language if it helps.

**Background**. If we know that a decision problem *L* is in the polynomial hierarchy, then we know that “P=NP ⇒ *L*∈P.” The intent of the question is to ask whether the converse holds. If a language *L* satisfying the above two conditions exists, then it can be thought of as an evidence that the converse fails.

The question has been motivated by Joe Fitzsimons’s interesting comment to my [answer](https://cstheory.stackexchange.com/questions/2021/consequences-of-p-fp/2028#2028) to Walter Bishop’s question “[Consequences of #P = FP](https://cstheory.stackexchange.com/questions/2021/consequences-of-p-fp).”

**Tags:** cc.complexity-theory, conditional-results, np, polynomial-hierarchy
> **Comments:**
> **username_2**: Proving a universal negative is always hard(er), but I would be surprised if such a language existed. The Generalized Linial-Nisan Conjecture (if it had ended up true) wouldn't have implied what you're asking, I don't believe. It would've just meant that BQP wasn't contained in PH. If PH collapsed to P, BQP still wouldn't have been contained in P(H).  
> **username_0**: @Philip: Yes, but I do not think that that changes the problem because we can usually convert a decision problem L to a class X of decision problems reducible to L.  At least that was my intent of asking this question in terms of decision problems.  
> **username_3**: Maybe you want to require that the language $L$ be somehow close to PH, in addition to your current requirements?  Maybe, say, in PSPACE (although it's arguable how close PSPACE is to PH; see S. Fenner, S. Homer, M. Schaefer, R. Pruim. Hyper-polynomial hierarchies and the polynomial jump. Theoretical Computer Science. Volume 262 (2001), pp. 241-256 http://www.cse.sc.edu/~fenner/papers/hyp.pdf).  Or maybe you really do want to ask for a *natural* such language.  
> **username_0**: @Joshua: Thank you for the comment and the reference.  As stated in the update (revision 3), now I think I had asked the right question (contrary to what I added in revision 2).  I had wanted to know “Is there any way to prove a conditional result ‘P=NP ⇒ L∈P’ without proving the unconditional result L∈PH?”  For this purpose, the naturalness of the problem should not be required because once there is a proof method, it should apply equally to both natural and contrived examples.  
> **username_0**: @Daniel: Thanks for the comment.  Yes, I thought that it would be surprising that such a language existed.  Now I _am_ surprised (see the answers)!  
> **username_2**: @Tsuyoshi, I'm quite surprised too. This was really informative for me!  
> **username_1**: See also related questions http://cstheory.stackexchange.com/questions/5399/why-doesnt-p-np-imply-p-ap-i-e-p-pspace and http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph  

---

## 3 answers

### Answer by username_5 on 2010-10-08. Score: 27 | Accepted answer

Since you don't mind an artificial language, how about defining $L$ to be empty if P equals NP and to be the Halting Problem if P doesn't equal NP. Okay, it's a bit of a cheat, but I think you'll need to rephrase the problem to avoid such cheats.

> **Comments:**
> **username_0**: Thanks, I see the point (define L={M: Turing machine M halts and P≠NP}).  Of course, this does not answer what I wanted to ask, but I guess that I have to think more to formulate the question which I wanted to ask correctly.  

---

### Answer by username_4 on 2010-10-08. Score: 32

If an artificial example is really as good as a natural one, then I can indeed provide such an example!

**Edit:** Furthermore, my example is "somewhat" less of a cheat than the one suggested by Ravi Boppana (where we take L to be the empty language if P = NP and the halting problem otherwise), in that I'll define the language L by giving a finite procedure to decide whether $x \in$ L for any input x. At no point will deciding whether x∈L require solving an "unbounded" mathematical question such as P vs. NP.

---

Without further ado: let $M\_1, M\_2, ...$ be an enumeration of polytime Turing machines. For all $n$, let $M\_{t(n)}$ be the lexicographically first $M\_i$ that correctly decides 3SAT on all inputs of length $n$ or less. Then define the language L as follows: for all inputs $x$ of size $n$, $x \in$ L if and only if the Turing machine encoded by $x$ halts in at most $n^{t(n)}$ steps when run on a blank tape.

**Claim 1:** If P = NP, then L $\in$ P.

**Proof:** If P = NP, then there's some fixed $M\_i$ that solves 3SAT for all inputs; hence $t(n) \le i$ for all $n$. QED

**Claim 2:** If P $\ne$ NP, then L $\notin$ P.

**Proof:** If $t(n)$ increases without bound, then we can simply apply the Time Hierarchy Theorem. QED

Now, not only is L not in P assuming P $\ne$ NP: one presumes it wouldn't be in PH (or even PSPACE) either!

Incidentally, I wonder if anyone can improve the above construction, to get a language L which is in P if P = NP, but *provably* not in PH or PSPACE if P $\ne$ NP?

> **Comments:**
> **username_0**: Thanks!  I have not been able to modify the construction to make nonmembership to PH provable, but this is sufficient to convince me that adding the condition that L is decidable with a constructive proof of the decidability will not probably change the situation much.  Hmm.  
> **username_0**: I will accept Ravi Boppana’s answer because his was the first to arrive, although I want to accept both because both gave me more understanding on the problem.  I hope that you understand….  
> **username_2**: Nice. This is a great answer.  
> **username_0**: @Tyson Williams: Just in case you have not realized, please be very careful not to introduce an error when you edit a post by other users.  It was fortunate that Joe noticed it and corrected it.  

---

### Answer by username_3 on 2010-10-08. Score: 20

Answering Scott Aaronson's question, but a bit too long for a comment, here is a construction of a language $L$ such that $P = NP$ implies $L \in P$, but $P \neq NP$ implies $L \notin PH$.

Let $M\_1, M\_2, M\_3, \dotsc$ and $t(n)$ be as in Scott's construction. We make it so that $L$ does not reduce to $\Sigma\_{k} SAT$ for each $k$, but we only do this if $t(n) \to \infty$ (i.e. if $P \neq NP$). The construction proceeds in stages. At stage $s=(i,j)$ (using some easily computable and easily invertible bijection $\Sigma^\* \to \Sigma^\* \times \Sigma^\*$), we ensure that $M\_i$ is not a many-one reduction from $L$ to $\Sigma\_{j} SAT$. Let $n\_{s}$ be the least integer such that $t(n\_{s}) > t(n\_{s-1})$ (base case: $n\_{0} = 1$). If there is such an integer $n\_{s}$, then set $L(1^{n\_{s}}) = 1 - \Sigma\_{k}SAT(M\_{i}(1^{n\_{s}}))$. If there is no such integer $n\_{s}$, we let $L$ be empty forever after.

If $P \neq NP$, then $t(n) \to \infty$ as $n \to \infty$, so there is always such an $n\_{s}$, hence $L$ is not in $PH$. If $P = NP$, then my $L$ is only finitely different from Scott's $L$, and hence is in $P$.

> **Comments:**
> **username_0**: Thank you for your answer, but I am not sure if I understand the construction.  It seems to me that to compute $n_s$, it might be necessary to search indefinitely, and therefore it seems to me that we do not have an explicit algorithm for deciding the language L.  If we do not need an explicit algorithm, Ravi Boppana’s answer shows that there exists a language L such that P=NP⇒L∈P and P≠NP⇒L∉R (i.e., L is undecidable).  
> **username_3**: @Tsuyoshi Ito: I don't think you have to compute $n_s$ given $s$ in order to decide L; all you have to do is, on input $1^n$, decide if $n$ is of the form $n_s$ for some $s$, and figure out which $s$ it is (if any).  Here's how: on input $1^n$, compute $t(n)$, and compute $t(m)$ for all $m < n$.  If there is an $m < n$ such that $t(n)=t(m)$, then $n$ is not $n_s$ for any $s$, so $L(1^n) = 0$.  Otherwise, figure out which stage $s$ corresponds to this $n_s$ (which can be done since you've computed all previous values of $t$) and then compute $L(1^n)$ as described in the answer.  

---

