World's most popular travel blog for travel bloggers.

[Solved]: What are the hardest problems that are in P if and only if P=NP?

, , No Comments
Problem Detail: 

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?

Asked By : Albert Hendriks

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59545

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback