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.

Asked by user567 (1 )
Oct 08, 2010 at 17:17