Asked By : Learning
Answered By : Gaste
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