# What are the hardest problems that are in P if and only if P=NP?

I used to think that NP complete problems are the "hardest" problems of all problems that would still be in P if P=NP. Now I think otherwise. What I'm asking is if there are any problems that are proved (/believed/maybe) to be harder than NP-Complete if $P\neq NP$, but are certainly in P if $P=NP$.

I was thinking of the sequence

$x_0 = P$

$x_{n+1} =$"All problems that have a checking algorithm in $x_n$"

e.g. $x_1 = NP$

If $P=NP$, then $x_n = P$ for all $n$. But if $P\neq NP$ is then $x_{n+1}$ different from $x_n$ for all $n$? Is this an ever continuing sequence so that there is no "hardest problem that meets the criteria" (because there would always be a harder one), or does this also hold for $x_\infty$ and would that be the hardest problem that meets the criteria? Or are there even harder such problems?

• See PH and these two questions. ​ ​ – user12859 Jun 12 '16 at 6:00

Well, here is a trivial example of a problem.

Inputs: a program P, an input x
Desired output: if P=NP, output "sweet!", else if P halts on x output "halts", else output "doesn't halt"

If P=NP, then this problem is in P. If P$\ne$NP, then this problem is very hard (it's undecidable).

I realize this might not be what you're looking for; if so, perhaps it illustrates just how tricky it is to specify properties of this sort.

• How would you implement "if p=np" on a TM? – adrianN Jun 12 '16 at 13:14
• @adrianN It's the specification, not the implementation. You don't need to implement it. – Tom van der Zanden Jun 12 '16 at 13:19
• @adrianN It's a constant. – Raphael Jun 12 '16 at 18:04

You have to say what "harder" means, that is which kind of reduction you want to use to order problems.

If you consider poly-time many-one reductions, all problems in P are equally hard.

If you consider log-space many-one reductions, we get a non-trivial set of P-complete problems.

If you consider ... I think you get the idea.

• P-complete problems are still in P if P!=NP, that doesn't meet the criterium "and only if" – Albert Hendriks Aug 22 '16 at 3:57