22.1. Introduction

A galaxy of computational problems exists in various disciplines, and researchers and scientists in general have striven hard or are still striving hard to solve these problems on a computer, by discovering or toiling hard to discover efficient algorithms for their solutions. Many of these problems have even offered them opportunities to discover an array of algorithms, one surpassing the other, in terms of efficiency or implementation.

There is a big class of problems that have been solved using algorithms having polynomial time complexity. For example, the time complexity T(n) of the best-known algorithms for the problems of finding the max/min element in a list or matrix multiplication or finding the first positive element in a list, to quote a well-known few, report polynomial time complexity. Such algorithms report T(n) = O(f(n)) or T(n) = Ω(f(n)) or T(n) = Θ(f(n)), where f(n) is a polynomial of a small degree and O(f(n)), Ω(f(n)) and Θ(f(n)) denote the upper bound, lower bound and both upper and lower bound, respectively, for T(n). The definitions and details pertaining to O(f(n)), Ω(f(n)) and Θ(f(n)) can be found in Chapter 2, Volume 1. Thus, the best-known algorithm to find the max/min element in a list reports Θ(n), the high school method of matrix multiplication reports O(n³) and the best case complexity for finding the first positive element in a list of real numbers reports Ω(1).

Such a class of problems is theoretically referred to as the Polynomial time class or P class of problems. However, a formal definition of P class includes only decision problems, which are problems that can be answered with yes/no type questions on the inputs specified.

Problems that can be solved in polynomial time are known as tractable problems and those that cannot be solved in polynomial time are known as intractable problems.

Another category of problems exists, which to date has failed to reveal the existence of any polynomial time algorithm to solve them. The best-known algorithms for these problems to date report exponential time complexity. Thus, if T(n) is the time complexity of such an algorithm, then T(n) = O(g(n)) or T(n) = Ω(g(n)) or T(n) = Θ(f(n)), where g(n) is larger than any polynomial. For example, the traveling salesperson problem discussed in section 21.3 reports an exponential time complexity of Θ(n².2ⁿ) when a dynamic programming strategy is applied to solve the problem. That exponential time complexity algorithms can turn unwieldy when due to their rapid growth rate they tend to consume humongous proportions of time even for moderate-sized problem inputs, was discussed and demonstrated in Chapter 2, Volume 1. Such a class of problems whose best-known algorithms report exponential time complexity and for which no polynomial time algorithms have been developed exists.

Some of these problems are decision problems and a vast majority of these decision problems are computationally difficult to solve and that is why they yield exponential time complexity solutions. However, when an oracle or somebody let us suppose, randomly calls out a solution, verification of the solution turns out to be computationally easy. In other words, verification of the solution can be done in polynomial time.

For example, a Hamiltonian circuit of a graph was defined in Chapter 9, Volume 2. To recall, a Hamiltonian circuit in a graph is a path that starts from a vertex, traverses through all other vertices exactly once, and returns to the start vertex. Given a graph with n vertices, finding a Hamiltonian circuit can be computationally difficult. However, given an ordered list of vertices by an oracle let us say, it is easy to check if the list describes a Hamiltonian circuit. All that it calls for is to check if there are (n+1) vertices with the starting and ending vertices being the same, whether the in-between vertices are all distinct, and lastly, every consecutive pair of vertices is connected by an edge.

This concept of “guessing” a solution and “verifying” it led to the concept of nondeterministic algorithms. The definition of NP class or Nondeterministic Polynomial class, which relies on nondeterministic algorithms, shall be detailed in the next section.

The concept of NP-completeness that evolved out of the NP class of problems will be the subject matter of this chapter.

So, what are we driving at?

Assume that a developer was assigned the task of designing an efficient algorithm for a problem that solves it within a reasonable time. Discovering a polynomial time algorithm should help the developer accomplish the task successfully. Let us suppose that the developer, despite all the efforts put forth, fails to obtain an algorithm that has reasonable performance. The developer has two options now, either to accept defeat saying that he/she is unable to find a polynomial time algorithm or assert with confidence that the given problem belongs to the NP class and is typically “hard” or intractable, and therefore no polynomial time algorithm exists for the said problem! The latter assertion could possibly lead to the developer being assigned the task of finding efficient algorithms for either special cases of the original problem or compromised versions of the problem or finding approximate solutions rather than exact solutions or employing heuristics to find near-optimal or acceptable solutions to the problem. Thus, a knowledge of NP-completeness is essential for algorithm designers and developers to rightly interpret their failures with regard to finding efficient algorithms for certain problems.

Garey and Johnson (Garey and Johnson, 1979) in their treatise on NP-completeness summed up aptly when they wrote “…In short, the primary application of the theory of NP-completeness is to assist algorithm designers in directing their problem-solving efforts towards those approaches that have the greatest likelihood of leading to useful algorithms.”

The aim of this chapter is therefore to enlighten the reader on NP-completeness and its associated concepts.

22.2. Deterministic and nondeterministic algorithms

Deterministic algorithms exhibit the property of uniquely defined operations that produce a distinct output for a given input when executed on a computer, which is a deterministic machine or, theoretically, a deterministic Turing machine.

Nondeterministic algorithms, on the other hand, describe a theoretical framework where the restriction that a distinct output needs to be produced for a given input is removed and in its place, the generation of a specified set of possible outputs with a degree of randomness is allowed. From a deterministic standpoint, nondeterministic algorithms can be thought of as a deterministic algorithm that replicates itself in parallel as many times as to produce the specified set of possibilities as output, randomly! A theoretical machine capable of executing such a phenomenon is termed a nondeterministic machine.

A nondeterministic algorithm for practical reasons is seen as a procedure that takes a decision problem X and does (i) nondeterministic guessing of random candidate solutions to the problem instances of X and (ii) with unbounded parallelism proceeds to verify each of the candidate solutions to the problem instances concerned, emitting a success signal if it is a solution (the decision problem instance reports “yes”) and a failure signal if it is not a solution (the decision problem instance reports “no”).

If the nondeterministic algorithm emits at least one success signal during the verification, then we claim that the nondeterministic algorithm has successfully solved the decision problem. On the other hand, if the nondeterministic algorithm emits a failure signal during the verification of each of the randomly generated candidate solution sets, then we claim that the nondeterministic algorithm is unsuccessful in solving the decision problem.

A nondeterministic algorithm is said to be a nondeterministic polynomial time algorithm if the verification of the randomly generated candidate solution sets can be done in polynomial time by the algorithm.

A nondeterministic algorithm can be theoretically described by augmenting the following function and statements to a deterministic framework:

1. Choice (S): Given a set S of possibilities or inputs, the function arbitrarily chooses any element of S. This function executes the guessing stage.
2. Failure: Signals unsuccessful termination of a process or computation.
3. Success: Signals successful termination of a process or computation

Function choice([1:n]), for example, indicates a random choice of any x ∊ [1 : n] with no rule to explain why the value was chosen. The function undertakes arbitrary choices during its execution. failure and success functions play a significant role in determining the successful completion or termination of the nondeterministic algorithm. A nondeterministic algorithm terminates successfully, if any one set of choices has triggered a success signal on its completion. On the other hand, a nondeterministic algorithm terminates unsuccessfully, if and only if there exists no set of choices that can trigger a success signal.

All the three algorithm components are assumed to have a time complexity of O(1) when executed on a nondeterministic machine, which is still utopian to date!

Example 22.1 illustrates a nondeterministic algorithm to find an element X in an unordered array A[1:n].

For a given input, if there exists a sequence of choices that leads to the successful completion of a nondeterministic algorithm, then the minimum number of steps or operations required to reach the successful completion determines the time taken by a nondeterministic algorithm. If the nondeterministic algorithm completes unsuccessfully, then the time taken is O(1).

A nondeterministic algorithm reports a complexity of O(f(n), if for all inputs of size n, n ≥ n₀, which yields a successful completion of the algorithm, the time required is at most c.f(n), for some constants c and n₀.

Going by the theoretical interpretation of a nondeterministic algorithm making several copies of itself every time a choice is made, the nondeterministic search for X in the unordered array A[1:n] reports O(1) time complexity. Contrast this with a deterministic algorithm which would report O(n) considering a for loop that would work through the unordered array A[1:n], one element at a time to check if it is X.

So the idea behind the theoretical concept of nondeterministic algorithms and their superior performance on a nondeterministic machine, when compared to deterministic algorithms, helps rephrase the definition of many problems belonging to the NP class. Thus, there exist many NP class problems whose best-known deterministic algorithms that yield exponential time complexity, are solvable on a nondeterministic machine using nondeterministic algorithms having polynomial time complexity.

If the P class alludes to problems with deterministic algorithms having polynomial time complexity when run on deterministic machines, the NP class alludes to problems with nondeterministic algorithms having polynomial time complexity when run on nondeterministic machines.

In light of the above, P class and NP class are defined as below:

P class

This is a class of decision problems that can be solved in polynomial time by deterministic algorithms.

NP class

This is a class of decision problems that can be solved by nondeterministic polynomial time algorithms, where verification of the solution can be done in polynomial time.

Most decision problems are in NP and P ⊆ NP, since the deterministic algorithm that solves the problem belonging to the P class can be used to verify the solution in polynomial time after ignoring the nondeterministic guessing of the candidate solution, both of which are hallmarks of nondeterministic algorithms.

22.3. Satisfiability problem

The satisfiability problem picked from the domain of logic, typically propositional logic or propositional calculus, is a simple problem that has found itself significantly linked to the concept of NP-completeness. The problem and its nondeterministic algorithm are detailed here.

Let x₁, x₂, … x_n indicate logical variables with truth values true or false, but not both. The logical variables are termed propositions in propositional logic and are defined as a statement, that is, either true or false but not both. Thus, the statement x₁: water boils at 50°C denoted by the proposition or logical variable x₁, is false, while the statement x₂: the sun rises in the east denoted by the proposition or logical variable x₂, is true.

To model real-world knowledge as logical formulae, connectives are required and propositional logic provides a set of them, for example, ¬,∧,∨,→ and =, named negation, conjunction, disjunction, implication and equality, respectively, and referred to as not,and, or, implies and equals.

If x₁, x₂ are two logical variables, then the syntax of the logical connectives is given by ¬x₁, x₁ ∧ x₂, x₂ ∨ x₂, x₁ → x₂ and x₁ = x₂ and the semantics of the connectives is defined using a truth table. Table 22.1 illustrates the truth table that defines the connectives of propositional logic.

A logical formula with n variables x₁, x₂, … x_n will evoke a truth table with 2ⁿ interpretations, where an interpretation is a row in a truth table that evaluates the truth value of the logical formula for a set of truth values assigned to the variables. For example, the truth table for the logical formula (x₁ ∧ x₂)∨ ¬x₃ shown in Table 22.2 evokes 2³ = 8 interpretations.

A logical formula that obtains the truth value true for all its interpretations in its truth table is called a tautology and if it obtains the truth value false for all its interpretations in its truth table, then it is called a contradiction.

22.4. NP-complete and NP-hard problems

The NP class was introduced as a class of problems to which the best-known algorithms to date report exponential time complexity. Also, these problems do not show evidence that polynomial time algorithms do not exist for them either. However, the best thing is that many of the problems for which no polynomial time algorithm exists, seem to be computationally related establishing two classes of problems, for example, NP-complete and NP-hard.

An NP-complete problem is one that can be solved in polynomial time if all other NP-complete problems can also be solved in polynomial time. An NP-hard problem is one which, if solvable in polynomial time, then all other NP-complete problems can be solved in polynomial time. Thus, all NP-complete problems are NP-hard but all NP-hard problems are not NP-complete.

The formal definitions that describe NP-completeness are listed in the next section.

22.4.1. Definitions

22.4.1.1. Problem reducibility

Let X and Y be two problems. X reduces to Y, denoted as X ∝ Y if there is a method to solve X by a deterministic polynomial time algorithm using a deterministic algorithm that solves Y in polynomial time.

It can be proved that problem reducibility satisfies the transitivity property. Thus, if X ∝ Y and Y ∝ Z then X ∝ Z.

22.4.1.2. NP-hard problem

The problem X is NP-hard if the satisfiability problem reduces to X, that is, SAT ∝ X.

22.4.1.3. NP-complete problem

A problem X is NP-complete if X is NP-hard and X ∈ NP.

It can be inferred from the definitions that there are NP-hard problems that are not NP-complete. If problem classes, in general, can be categorized as decision class and optimization class, only decision problems can be NP-complete. The optimization class of problems, however, may belong to the NP-hard class. Also, if D is a decision problem and O is an optimization problem then D ∝ O is quite possible.

For example, let us consider the 0/1 knapsack optimization problem discussed in section 21.2. The 0/1 knapsack decision problem concerns the 0/1 assignment of values to variables x_i, 1 ≤ i ≤ n such that and , 1 ≤ i ≤ n, where P and M are given numbers denoting an expected profit and capacity of the knapsack respectively, and nonnegative numbers p_i s and w_i s indicate profits and weights respectively. It can be trivially established that the 0/1 knapsack decision problem is reducible to the 0/1 knapsack optimization problem.

In general, decision problems can be NP-complete but optimization problems cannot be NP-complete. However, there do exist NP-hard decision problems that are not NP-complete. The halting problem from the theory of computation is a classic example of an NP-hard problem that is not NP-complete.

Given an arbitrary computer program and its input, the halting problem tries to determine whether the program will finish running and thereby come to a halt or keep on running forever. Alan Turing adopted the concept of a Turing machine to describe a computer and a program and went on to prove that a general algorithm that will determine the program-input combinations for which the machine will halt, does not exist. Therefore, the halting problem is termed an undecidable problem and hence halting problem ∉ NP. Therefore, the halting problem is not an NP-complete problem.

Figure 22.2 illustrates the relationship between the problem classes P, NP, NP-hard, NP-complete and undecidable problems.

22.4.1.4. Polynomial equivalence of problems

Two problems X and Y are said to be polynomially equivalent if X ∝ Y and Y ∝ X.

In order to show that a problem Z is NP-hard, it is enough to show that X ∝ Z, where X is a problem already known to be NP-hard. This can be easily inferred, since problem reducibility (∝) satisfies transitivity property and X is already NP-hard, we have satisfiability ∝ X and X ∝ Z implying satisfiability ∝ Z, which declares Z to be NP-hard.

To show that an NP-hard decision problem is NP-complete, it only needs to be shown that a nondeterministic algorithm that runs in polynomial time exists for it.

Therefore, to show that a problem M is NP-hard:

1. select a problem L that is already NP-hard, that is, SAT ∝ L;
2. show how to obtain in deterministic polynomial time an instance I^(M) of problem M, from any instance I^(L) of problem L, such that from the solution of instance I^(M), the solution to instance I^(L) can be obtained in deterministic polynomial time;
3. establish that L ∝ M from condition (ii);
4. establish from (i) and (iii) and the transitivity property of ∝, that SAT ∝ M. Hence M belongs to the NP-hard class.

22.5. Examples of NP-hard and NP-complete problems

There are numerous problems which are NP-hard only or NP-complete. A few of the well-known problems to serve as examples for the concepts discussed earlier has been given below.

i) Circuit satisfiability problem (CIRCUIT-SAT) finds if a Boolean combination circuit made up of AND, OR and NOT gates as illustrated and defined by means of their respective truth tables in Figure 22.3 is satisfiable.

A circuit is satisfiable if it produces an output of 1. The circuit satisfiability problem surfaces in the domain of computer-aided hardware optimization problem, where a sub-circuit that always produces a 0 as output can be eliminated to reduce the clutter and be replaced by a simpler circuit that constantly outputs a 0. An instance of the CIRCUIT-SAT problem has been discussed in illustrative problem 22.2. CIRCUIT-SAT is an NP-complete problem.

ii) Satisfiability problem (SAT) and 3-CNF satisfiability problem (3-CNF SAT) are NP-complete. Both the problems belong to NP class and are NP-hard, for it is possible to find an NP-hard problem that reduces to it. It can be shown that CIRCUIT-SAT-SAT ∝ SAT and SAT ∝ 3-CNF SAT, where both CIRCUIT-SAT and SAT are NP-hard problems.

Illustrative problem 22.3 demonstrates CIRCUIT-SAT ∝ SAT and illustrative problem 22.6 demonstrates SAT ∝ 3-CNF SAT.

iii) Directed Hamiltonian circuit problem (DHC) finds if a digraph has a directed Hamiltonian cycle, which is a path that begins from a vertex of the graph, traverses through all other vertices once and returns to the starting vertex.

This problem is NP-hard since it can be shown that SAT ∝ DHC. Also, DHC ∈ NP since verification of a candidate solution for the problem can be done in polynomial time. Hence DHC is an NP-complete problem.

iv) Traveling salesperson decision problem (TSP-decision) finds whether the cost of undertaking a tour of n cities, beginning from a city, visiting all other cities once without revisiting any one of them again, before returning to the starting city from where the tour started, can be at most M. Note that this problem is a decision problem and not an optimization problem as was discussed in section 21.3, where a dynamic programming based algorithm was evolved to solve it.

The TSP-decision problem is NP-hard since it is possible to show that the Directed Hamiltonian Cycle problem which is NP-hard can be reduced to the TSP-decision problem, that is, DHC ∝ TSP-decision. Also, TSP-decision ∈ NP and therefore the TSP-decision problem is NP-complete.

v) Chromatic number (CN) decision problem is associated with the graph coloring problem, where, given a graph, the chromatic number, that is the smallest number of colors required to color the graph in such a way that no two adjacent vertices are assigned the same color, needs to be found. The CN problem is a decision problem that only tries to determine if the graph has a coloring for a given chromatic number k.

CN is NP-hard since 3-CNF SAT, which is a restricted version of the CNF satisfiability problem, is NP-hard and it can be shown that 3-CNF SAT ∝ CN. Also, CN ∈ NP and hence CN is an NP-complete problem.

22.6. Cook’s theorem

It is now understood that P class refers to the set of all decision problems solvable by deterministic algorithms in polynomial time and NP class refers to the set of all decision problems solvable by nondeterministic algorithms in polynomial time.

As illustrated in Figure 22.1, deterministic algorithms are a subclass of nondeterministic algorithms and therefore P ⊆ NP. The question of whether P = NP or P ≠ NP has intrigued researchers for many years now. Is it possible to obtain deterministic algorithms that run in polynomial time for all the problems in NP, thereby rendering P = NP? The answer seems elusive for now, despite all the tremendous efforts that have been put in this direction, giving rise to the now famous unsolved problem .

However, thanks to the efforts of S. Cook, who formulated Cook’s theorem, that has served to make a breakthrough in the solution of the original problem. Cook asserted that there does exist a problem in NP which if showed to be in P would automatically imply that P = NP and that special problem was none other than the satisfiability problem!

The statement of Cook’s theorem is as below:

Theorem: Satisfiability is in P if and only if P = NP.

An informal proof to the theorem is as described below:

Let us suppose that P = NP. To show that satisfiability is in P.

It is already known that satisfiability is in NP. Hence if P = NP then satisfiability is in P.

Let us suppose that satisfiability is in P. To show that P = NP.

To show that P = NP, we need to show that P ⊆ NP and NP ⊆ P. That P ⊆ NP is trivial and known.

To show that NP ⊆ P, it can be proved that from any nondeterministic polynomial time algorithm A and an input I, a logical formula Q(A, I) can be obtained such that Q is satisfiable if A terminates successfully for input I. It is possible to obtain a deterministic algorithm Z to determine the outcome of A on any input instance I. Z merely computes Q and then uses the deterministic algorithm for the satisfiability problem to determine whether or not Q is satisfiable. This construction only shows that every problem in NP reduces to satisfiability. Since satisfiability is in P, we have NP ⊆ P.

Therefore, from P ⊆ NP and NP ⊆ P, we have P = NP.

22.7. The unsolved problem

The now famous problem just depends on whether a deterministic polynomial time algorithm can be found for the satisfiability problem. Not an easy one though, for it is one among 7 Millennium Problems listed by the Clay Mathematical Institute, with a standing offer of $1 million for anyone who can prove or disprove it.

However, a lot of research efforts are under way to obtain SAT solvers and, in certain cases, they have even matured to the point of being commercially exploited in industrial applications. Malik and Zhang (2009) present a good review of SAT solvers and their effective deployment for practical problems and applications.

22.8. Illustrative problems