NP-Complete Problems

[sophryu99]

An NP problem is a yes/no problem such that:

• There is polynomial-time proof for every instance of the problem with a "yes" answer that the answer is "yes", or (equivalently)
• There exists a polynomial-time algorithm (possibly using random variables) that has a non-zero probability of answering "yes" if the answer to an instance of the problem is "yes" and will say "no" 100% of the time if the answer is "no." In other words, the algorithm must have a false-negative rate less than 100% and no false positives.

A problem X is NP-Complete if

• X is in NP, and
• For any problem Y in NP, there is a "reduction" from Y to X: a polynomial-time algorithm that transforms any instance of Y into an instance of X such that the answer to the Y-instance is "yes" if and only if the answer X-instance is "yes".

[sophryu99]

P: refers to a solution of the problem of Polynomial Time.

NP: refers Polynomial Time yet to find a solution. We are not sure there is no Polynomial Time solution, but once you provide a solution, this solution can be verified in Polynomial Time.

NP Complete: refers in Polynomial Time we still yet to find a solution, but it can be verified in Polynomial Time . The problem NPC in NP is the more difficult problem, so if we can prove that we have P solution to NPC problem then NP problems that can be found in P solution.

NP Hard: refers Polynomial Time is yet to find a solution, but it sure is not able to be verified in Polynomial Time . NP Hard problem surpasses NPC difficulty.