NPvollständiges

NPvollständiges, or NP-complete, is a term used in computational complexity theory to describe a set of decision problems that are among the most difficult in the class of NP problems. A problem is considered NP-complete if it is in the class NP (nondeterministic polynomial time) and is at least as hard as any problem in NP. This means that if an efficient algorithm (one that runs in polynomial time) is found for any NP-complete problem, then efficient algorithms exist for all problems in NP.

The concept of NP-completeness was introduced by Stephen Cook in 1971. Cook's theorem established that the Boolean satisfiability problem (SAT) is NP-complete, meaning that if SAT can be solved in polynomial time, then all problems in NP can be solved in polynomial time. Since then, thousands of problems have been shown to be NP-complete, including problems in fields such as logic, mathematics, and optimization.

NP-complete problems are of particular interest because they represent the boundary between what is known to be solvable in polynomial time and what is not. While no polynomial-time algorithm has been found for any NP-complete problem, it is also unknown whether such an algorithm exists. This question is one of the most important open problems in theoretical computer science.

Examples of NP-complete problems include the traveling salesman problem, the subset sum problem, and the vertex cover problem. These problems have been studied extensively, and many heuristics and approximation algorithms have been developed for them. However, no polynomial-time algorithm is known for any of these problems.