Theoretical Computer Science
cc.complexity-theory conditional-results np polynomial-hierarchy
Updated Sat, 21 May 2022 17:44:25 GMT

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

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 LP without proving the unconditional result LPH? 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 LP.

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 LP. 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 Fitzsimonss interesting comment to my answer to Walter Bishops question Consequences of #P = FP.


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 (1)

  • +5 – Thanks, I see the point (define L={M: Turing machine M halts and PNP}). 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. — Oct 08, 2010 at 18:42