A decision problem which is not known to be in PH but will be in P if P=NP

Question

Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, 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 to Walter Bishop’s question “Consequences of #P = FP.”

Answer 1

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.

Answer 2

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?

Answer 3

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