[Solved]: If I solve hard instance, therefore I prove NP=P?

Problem Detail: If someone (off-topic) asks a question (on-topic) like this: Suppose that he claims that $mathcal{P=NP}$. Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that cannot be solved by any computer optimally, i.e., to get the optimal solution, one must run an algorithm for very long time (the age of the universe for example). If this someone (off-topic) solves this instance very fast optimally. Because the problem is NP-complete, we know that it can be easily verified. Can we verify easily that it is the optimal solution or we can only verify that it is just a solution? In the other hand, if this someone (off-topic) solves every instance (hard instances) of an NP-hard problem very fast. Can we claim that he proved that $mathcal{P=NP}$? I want an answer, not a vote up/down or on/off-topic.

Asked By : Learning

Answered By : Gaste

$mathrm{P}$ and $mathrm{NP}$ are both sets of languages. A language $A subseteq Sigma^{star}$ is in $mathrm{P}$ ($mathrm{NP}$), if and only if there exists a deterministic (nondeterministic) turing machine $M$, that can decide in polynomial time for all $x in Sigma^star$, whether $x in A$. There is an alternative definition of $mathrm{NP}$: $A subseteq Sigma^star$ is in $NP$, if there is an language $L_0 in mathrm{P}$ and an polynom $p(x)$, such that $A = left{ x mid exists y text{ with } |y| leq p(|x|) text{ and } x#y in L_0 right}$ That $y$ is called proof (or witness) that $x$ is in $A$. For example, the satisfiability problem is to check whether a given boolean formula is satisfiable or not. $mathrm{SAT}$ is the language of all satisfiable boolean formula. Given a boolean formula $phi$ (a instance of the satisfiability problem), we want to check whether $phi$ is satisfiable (if $phi in mathrm{SAT}$). A witness for $phi$ is an interpretation. We can determine in polynomial time, whether the interpretation of that formula is true or false.

Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that cannot be solved by any computer optimally, i.e., to get the optimal solution, one must run an algorithm for very long time (the age of the universe for example)

For descition problems, there no such thing as an optimal solution. The answer is yes or no (since the question is whether a string over an alphabet is in the language or not). Also, just because an algorithm runs for a very long time does not imply that the problem is in $mathrm{NP}$: Consider the worst case time complexity of something like $n^{100}$, which is even for small input sizes very high, but in $mathrm{P}$. But lets consider we give him an instance of an $mathrm{NP}$-complete problem, for example of the satisfiability problem:

If this someone (off-topic) solves this instance very fast optimally. Because the problem is NP-complete, we know that it can be easily verified. Can we verify easily that it is the optimal solution or we can only verify that it is just a solution?

Again, for descition problems there is no such thing as an optimal solution. Therefore, we can verify an solution in polynomial time.

In the other hand, if this someone (off-topic) solves every instance (hard instances) of an NP-hard problem very fast. Can we claim that he proved that P=NP?

If he presents us an (correct) deterministic polynomial time algorithm, the answer is yes. Theoretically, he could just got lucky everytime and guess a correct solution, or own a non-deterministic turing machine. Since there is an infinite amount of $mathrm{NP}$-complete problems and only limited time, there is no way of solving all instances. Also, for only a finite amount of instances, one could use an (huge) lookup table. For futher information regarding the $mathrm{P}$ vs $mathrm{NP}$ problem, you could look at the official problem description of the Clay Mathematics Institute.

Best Answer from StackOverflow

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

Leave a Reply