28
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Daniel Apon Oct 8 '10 at 17:43
  • $\begingroup$ Are you asking if there exists a complexity class X s.t. X is not a subset of PH, and P = NP --> X = P? $\endgroup$ – Philip White Oct 8 '10 at 19:17
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Oct 8 '10 at 19:41
  • $\begingroup$ 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 cse.sc.edu/~fenner/papers/hyp.pdf). Or maybe you really do want to ask for a natural such language. $\endgroup$ – Joshua Grochow Oct 8 '10 at 19:51
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Oct 8 '10 at 20:26
26
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Oct 8 '10 at 18:42
30
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Oct 8 '10 at 19:03
  • 3
    $\begingroup$ 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…. $\endgroup$ – Tsuyoshi Ito Oct 8 '10 at 19:40
  • 4
    $\begingroup$ Nice. This is a great answer. $\endgroup$ – Daniel Apon Oct 9 '10 at 0:08
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Aug 25 '11 at 15:58
18
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Tsuyoshi Ito Oct 9 '10 at 19:10
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Oct 9 '10 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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