NP-complete
Introduction
In the field of computer science, NP-complete is a class of decision problems. A decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC.
Definition
The class of problems known as NP-complete was first defined by Stephen Cook in his seminal 1971 paper "The Complexity of Theorem-Proving Procedures". In this paper, Cook introduced the concept of NP-completeness and defined the class of problems known as NP-complete.
A decision problem C is NP-complete if:
1. C is in NP, and 2. Every problem in NP is reducible to C in polynomial time.
C can be shown to be in NP by demonstrating that a candidate solution to C can be checked quickly, and that every problem in NP can be quickly reduced to C.
NP Problems
An NP problem is one for which a potential solution can be verified quickly. In other words, if you are given a "yes" answer to an NP problem, you can check that the answer is correct in polynomial time.
The class NP is the set of decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes". These proofs have to be verifiable in polynomial time by a deterministic Turing machine.
NP-Hard Problems
A problem H is NP-hard if every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, we can use H's solution to solve L in polynomial time.
Examples of NP-Complete Problems
There are many known NP-complete problems. Some of the most famous include the Travelling Salesman Problem, the Knapsack Problem, and the Boolean Satisfiability Problem.
1. Travelling Salesman Problem: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
2. Knapsack Problem: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
3. Boolean Satisfiability Problem: Given a Boolean expression, find a truth assignment for the variables in the expression such that the expression evaluates to true, if such an assignment exists.
Importance of NP-Completeness
The concept of NP-completeness is important because it helps us understand the inherent difficulty of problems. If a problem is NP-complete, then it is unlikely that there is an efficient algorithm to solve it. This means that computer scientists can focus their efforts on finding approximate solutions or heuristics, rather than wasting time trying to find an exact solution that likely doesn't exist.
P vs NP Question
The P vs NP problem is a major unsolved question in computer science. It asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. In other words, it asks whether P equals NP.