3
$\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?

Improve this question
$\endgroup$
1
  • $\begingroup$ See PH and these two questions. ​ ​ $\endgroup$
    – user12859
    Commented Jun 12, 2016 at 6:00

3 Answers 3

Reset to default
10
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How would you implement "if p=np" on a TM? $\endgroup$
    – adrianN
    Commented Jun 12, 2016 at 13:14
  • 2
    $\begingroup$ @adrianN It's the specification, not the implementation. You don't need to implement it. $\endgroup$
    – Tom van der Zanden
    Commented Jun 12, 2016 at 13:19
  • 2
    $\begingroup$ @adrianN It's a constant. $\endgroup$
    – Raphael
    Commented Jun 12, 2016 at 18:04
  • $\begingroup$ (P = NP) is a constant boolean expression with currently unknown value. We don't know today if it is a trivial problem or an undecidable problem, but it is either one or the other. $\endgroup$
    – gnasher729
    Commented Feb 16, 2023 at 12:36
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.

Improve this answer
$\endgroup$
0
0
$\begingroup$

Your answer: Any problem that is NP-hard, that is today believed not to be in NP, but that actually can be proved to be in NP (except for the fact that nobody has yet been able to do so).

Obviously if P = NP then any problem that can be proved to be in NP is actually in P.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.