patternModerate
What are the hardest problems that are in P if and only if P=NP?
Viewed 0 times
thewhatarehardestthatandproblemsonly
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#59545, answer score: 10
Revisions (0)
No revisions yet.