What is a complete NP problem?

Question

What is a complete NP problem? What examples can be given to illustrate a complete NP problem? Why these problems are considered important?

Answer 1

P, NP and NP-complete problems:

The problem P is a decision problem (i.e., the answer may be sim or não), that might be solved polynomial-time.

The problem NP (Non-deterministic Polynomial time), i.e., "Nondeterministic polynomial time". The NP problem may be a P problem (actually the subject is more complex), with the characteristic of "nondeterministic", that is, it can be proven polynomial-time.

An example of NP is Factorization:

Dice n and m, there is a whole f in range 1 < f < m which is a factor of n (split with entire result)? This is a decision problem as the answer may be only sim or não. However, we are dealing with a specific case (the f provided). To verify, we have to test concrete cases by checking n / f for each f.

The NP-complete problem, According to Wikipedia, "is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP can be equivalently defined as the set of decision problems that can be solved in polynomial time on a nondeterministic Turing machine. A p problem in NP is also in NPC If and only if all other problems in NP can be transformed into p in polynomial time (...)

A decision problem C is NP-complete if:

1. C is in NP, and
2. Every NP-complete problem is reducible to C polynomial-time.

C can be shown to belong to NP demonstrating that a candidate solution for C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard, whether it satisfies condition 1 or not. A consequence of this definition is that if we had a polynomial time algorithm for C, we could solve all NP problems in polynomial time."

The "importance" of NP-complete problems:

Still according to the Wikipedia, "NP-complete problems are studied because the ability to quickly verify solutions to a problem (NP) seems to correlate with the ability to quickly solve that problem (P). It is not known whether all problems in NP can be quickly solved - this is called the P versus NP problem. But if any problem in NP-complete can be solved quickly, then every problem in NP can also be, because of the NP-complete definition states that every problem in NP must be quickly reducible to every problem in NP-complete (i.e., it can be reduced in polynomial time). Because of this, it is generally said that NP-complete problems are more difficult than NP problems in general."

An example of a complete NP problem is a Tower of Hanoi, which is a jigsaw puzzle in which you have discs of different sizes, in ascending order of diameter, with the smallest ones on top, on a pin, and have two more free pins. The goal is to pass all the disks to another pin, but passing only one at a time, and so as to never get a bigger one on the smaller.

In practice, the great discussion is that NP-complete problems are the key to determining whether P = NP or P ≠ NP. If at some point an NP problem cannot be solved in P-time, no NP-complete problem can be solved in P-time. On the other hand, if any NP-complete problem can be solved in P-time, P = NP

Algorithms for NP-complete troubleshooting:

• Approximating: An algorithm that quickly finds a solution not necessarily optimal, however within a certain error range. In some cases, finding a good approximation is enough to solve the problem, but not all NP-complete problems have good approximation algorithms.
• Probabilistic: An algorithm that can get on average a good solution to a problem presented from an input data distribution.
• Constraint: Restricting the structure of the input, faster algorithms are possible.
• Parameterization: Usually there are fast algorithms if certain input parameters are fixed.
• Heuristics: An algorithm that works reasonably well in many cases, but there is no proof that they are always fast and that they always produce good results.

Answer 2

An NP-complete problem is a problem belonging to problem class NP which may be reduced in polynomial time to boolean satisfiability problem (SAT):

Given a Boolean expression expressed as a conjunction of disjunctions between n variables, denied or not, for example:

(x1 ou x2 ou não x3 ou x4) e (x1 ou não x2 ou x3 ou não x4) e ...

Find a set of values for x1, x2, x3, ... xn such that the expression is true.

P vs NP

A problem is said to be "polynomial", or belonging to Class P, whether there is a known algorithm capable of solving the same order of complexity [in the worst case] is polynomial with respect to the "size" of the input. If no such algorithm is known, the problem does not belong to this class (for more precise definitions, see the response of Bacco).

Some non-polynomial problems, however, have another feature: given a candidate solution (i.e. a set of values that may or may not be a solution to this problem) one can verify whether or not it is a polynomial-time solution. These problems are said to be "nondeterministic polynomials", or belonging to class NP, because they can be solved in a "generation and testing" scheme (choose from the space of solutions a candidate, and test to see if it is in fact a solution).

Naturally, the solution space may be larger than "polynomial relative to input size"; choosing a candidate in that space is not something that can be done deterministically in polynomial time. But there must be a way to do it "not deterministically", that is, given two choices A and B, "guess" which is the right choice and move on. If on the other hand the space of solutions is so large that even guessing right is still not possible to reach the answer in polynomial time, then this problem is more difficult than NP.

Downsizing

What does it mean that one problem is "reduced" to another? Simply that there is a process that can transform one problem into another, solve the other, and turn the solution found into a solution to the original problem. Example:

What is the common minimum multiple between 6 and 15?

Instead of solving this problem directly, one can turn this problem into a maximum common divisor problem:

mmc(x, y) = abs(x * y)/mdc(x, y)

Solve the problem mdc(6, 15) (much more "easy" - given the euclidean algorithm or, if efficiency is the issue, the MDC Binary) and, in possession of its solution (3), get the final solution:

mmc(6, 15) = abs(6 * 15)/mdc(6, 15) = 90/3 = 30

Sometimes the importance of reduction is only theoretical (more on that below), in others one can have concrete benefits in doing so - reuse a ready-made implementation, for example. Since of course the process to convert the problem and the solution is not more costly than simply solving the original problem.

SAT

The satisfiability problem, mentioned earlier, is of special importance for two reasons: 1) was the first known example of the NP-complete class (i.e. it "inaugurated" the class); and 2) it is self-reducible, that is, any algorithm capable of telling whether or not such a SAT instance has a solution is also able to say what is this solution (i.e. does not need to be only "yes" or "no", for this particular problem at least).

Clarifying, when I say that he "inaugurated the class" it means that it has been proved that any problem belonging to the class NP can be reduced to SAT. The problems in P can also be reduced to SAT, of course, but as a good solution for them is already known, these are not considered part of NP-Complete (i.e. if P NP, then we have P NP and NP-Complete NP but P NP-Complete = Ø).

In general, one can say that a problem is NP-complete if it reduces to any other NP-complete problem, not necessarily the SAT (the problem of the click is very popular in this sense), but as this is of theoretical importance I found it interesting to give this prominence. And if it has not become clear, it is believed that the SAT does not belong to P (until now a deterministic solution for SAT in polynomial time is not known).

Practical Importance

Okay, but what is the practical importance of knowing that such a problem is NP-Complete or not? Everything is a matter of deciding, quickly, whether a given problem can be satisfactorily solved given the current techniques of resolution or not (depending on its scale, of course). Instead of smashing your head for hours trying to find a solution to a problem, realizing that it is equivalent (or reducible) to another problem can save you a lot of time:

1. This problem is reducible to another in P, so it can be solved! Just need to know the best way;
2. This problem is reducible to another NP-complete, so you can’t guaranteed find the best solution, we will have to settle for an approximate solution;
3. This problem is reducible to another that is not [demonstrably] NP, so you better give up and try to find another problem that’s simpler, feasible and "good enough" for me.