Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 34

The author defines polynomial time algorithm as algorithm that on input of size $n$, has a worst-case running time of $O(n^k)$ where $k$ is any constant. The author describes that not all the problems can be solved in polynomial time. The author then focuses on "NP-complete" problems, the problems for which no polynomial time algorithm exists and nobody has been able to prove that no polynomial time algorithm can exist.

The author defines an abstract problem to be a binary relation on a set $I$ of problem instances and a set $S$ of problem solutions. An instance of a SHORTEST-PATH problem is a triple with a graph and two vertices while its solution is a sequence of vertices in the graph.

The authors provide definitions of alphabet and language. The authors also define operations such as union and intersection. The authors then define concatenation, closure/Kleene star, and complement. The author explains the meaning of an algorithm accepting a string and the language defined by acceptance of set of strings.

The author then calls a language decided by an algorithm $A$ if every binary string in $L$ is accepted by $A$ and every binary string not in $L$ is rejected by $A$.

A language $L$ is decided in polynomial time by an algorithm $A$ if there is a constant $k$ such that for any length-n string $ x \in L $, algorithm $A$ accepts $x$ in time $O(n^k)$. A language $L$ is decided in polynomial time by an algorithm $A$ if there is a constant $k$ such that for any length-n string $x \in \{0,1\}*$, the algorithm correctly decides whether $x \in L$ in time $O(n^k)$.

The author defines Hamiltonian Cycle and Hamiltonian Graph. A verification algorithm takes two arguments, an ordinary input string $x$ and a binary string $y$ called certificate. The algorithm $A$ verifies the input string $x$ if there exists a certificate $y$ such that $A(x,y)=1$.

The authors define complexity class NP as the class of languages that can be verified by a polynomial time algorithm. The complexity class co-NP is defined as set of languages $L$ such that $\overline{L} \in NP$.

A language $L_1$ is called polynomial time reducible to a language $L_2$, written $L_1 \le _P L_2$, if there exists a polynomial time computable function $ f : \{0,1\}* \rightarrow \{0,1\}* $ such that for all $ x \in \{0,1\}* $, $ x \in L_1 $ if and only if $ f(x) \in L_2$. $f$ is called the reduction function and a polynomial time algorithm $F$ that computes $f$ is called reduction algorithm.

A language $L \subseteq \{0,1\}*$ is NP-complete if

1. $L \in NP$, and
2. $L' \le _P L$ for every $L \in NP$.

If a language $L$ satisfies property 2, but not necessarily property 1, we say that $L$ is NP-hard.

A truth assignment for a boolean combinational circuit is a set of boolean input values. A one output boolean combinational circuit is satisfiable if it has a satisfying assignment, a truth assignment that causes the output of the circuit to be 1.

The circuit-satisfiability-problem is to determine whether a boolean combinational circuit composed of AND, OR and NOT gates satisfiable.

The size of a boolean combinational circuit is the number of boolean combinational elements plus the number of wires in the circuit. The authors then prove two lemmas based on which they derive the theorem that circuit-satisfiability-problem is NP-complete.

The author prove a Lemma and a theorem to show that satisfiability of boolean formulas is NP-complete.

The authors then discuss following problems to be NP-complete:

• The clique problem
• The vertex-cover problem
• The hamiltonian-cycle problem
• The travelling-salesman problem
• The subset-sum problem