2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ See PH and these two questions. ​ ​ $\endgroup$ – user12859 Jun 12 '16 at 6:00
9
$\begingroup$

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.

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

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.

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

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.