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

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

Local articles referenced by this article: