-1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ There is no such thing as a "hard instance". Any single instance of a problem can be solved in linear time: just check for that instance and output the correct answer, which is either "yes" or "no" and can be pre-computed. Since the answer to any problem in NP is either "yes" or "no", there is no such thing as an optimal solution. $\endgroup$ – David Richerby Mar 22 '14 at 19:54
  • $\begingroup$ If you give me an instance of sat and always I give you back yes or no correctly. Is this a proof? That's my question. $\endgroup$ – Learning Mar 22 '14 at 20:07
  • 1
    $\begingroup$ Related question. But suspect you need this one. $\endgroup$ – Raphael Mar 22 '14 at 23:04
  • 2
    $\begingroup$ No, demonstrating that you can solve individual SAT instances says nothing about P=NP. $\endgroup$ – dimo414 Mar 26 '14 at 4:34
5
$\begingroup$

$\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.

$\endgroup$
  • $\begingroup$ Can you give me a good reference in P vs. NP definitions and related topics, ...? Like the definitions you used. Books, Tutorial, ... $\endgroup$ – Learning Mar 22 '14 at 20:09
  • $\begingroup$ @user3439590 Most of my knowledge and definitions are from lectures at my university. One source is he book Introduction to Automata Theory, Languages, and Computation by Hopcroft et. al., which is very comprehensive. $\endgroup$ – Gaste Mar 22 '14 at 20:41
  • 1
    $\begingroup$ Your effort is appreciated, but I think your answer (and the question, for that matter) is redundant given the reference question we have. If you disagree, feel free to drop by in Computer Science Chat and discuss the matter! $\endgroup$ – Raphael Mar 22 '14 at 23:05
  • $\begingroup$ Ok. It is off-topic and duplicate. I will delete it to not discuss the matter. $\endgroup$ – Learning Mar 22 '14 at 23:22

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