Notes

Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

Optimization and Decision Problems Many problems of interest are optimization problems, in which each feasible solution has an associated value, and we wish to find a feasible solution with the best value. NP - Completeness applies directly not to optimization problems, however, but to decision problems, in which the answer is simply "yes" or "no" (or, more formally, "1" or "0").

Although NP - Complete problems are confined to the realm of decision problems, we can take advantage of a convenient relationship between optimization problems and decision problems. We usually can cast a given optimization problem as a related decision problem by imposing a bound on the value to be optimized. 

For example, a decision problem related to **shortest - path **is path: given an undirected graph G, vertices u and v, and an integer k, does a path exist from u to v consisting of at most k edges? 

The relationship between an optimization problem and its related decision problem works in our favor when we try to sow that the optimization problem is "hard". That is because the decision problem is in a sense "easier", or at least "no harder".

As a specific example, we can solve path by solving shortest-path and then comparing the number of edges in the shortest path found to the value of the decision-problem parameter k. In other words, if an optimization problem is easy, its related decision problem is easy as well. Stated in a way that has more relevance to NP-Completeness, if we can provide evidence that a decision problem is hard, we also provide evidence that its related optimization problem is hard.

Satisfiability Problem This problem has the historical honor of being the first problem ever shown to be NP-Complete.

We formulate the (formula) satisfiability problem in terms of the language SAT as follows. An instance of SAT is a boolean formula composed of:

• n boolean variables (literals): x1, x2, ..., xn
• m boolean connectives: and, or, ...
• parentheses.

A formula with a satisfying assignment is a satisfiable formula. The satisfiability problem asks whether a given boolean formula is satisfiable. 

We define 3-CNF Satisfiability using the following terms. A literal in a boolean formula is an occurence of a variable or its negation. A boolean formula is in Conjunctive Normal Form or CNF, if it is expressed as an AND of clauses, each of which is the OR of one or more literals. A boolean formula is in 3-conjunctive normal form, or 3-CNF, if each clause has exactly three distinct literals.

SAT to Independent Set: The natural algorithmic problem is, given a graph, find the largest Independent Set. To turn this optimization problem into a decision problem, we define IND as:

The set of pairs (G,K), where G is a graph, and K is an integer, such that G contains an independent set with K or more vertices. IND is in NP. We now show it is NP-complete. We can construct a reduction from 3SAT to IND. A Boolean expression φ in 3CNF with m clauses is mapped by the reduction to the pair (G, m), where G is the graph obtained from φ as follows: G contains m triangles, one for each clause of φ, with each node representing one of the literals in the clause.

Additionally, there is an edge between two nodes in different triangles if they represent literals where one is the negation of the other. If this graph has an independent set with m (or more) vertices then the such set would provide a solution for the associated 3-SAT problem. 

SAT to Vertex Cover: Let G be an undirected graph. A vertex cover of G is a subset COVER of V such that for every (u, v) ∈ E, at least one of u or v ∈ COVER.  Suppose our boolean formula for 3-SAT, φ, contains m variables and l clauses. For our vertex cover we will use k = m + 2l. For each variable in φ we will use the following variable gadget:

The variable x in a φ for 3-SAT is replaced by two nodes in the graph. One represents the literal x, while the other represents the literal ¬x. For each clause in φ we will use the clause gadget:

The 3-SAT clause is represented as a clique of 3 nodes, where each node represents a literal in the clause. The clause represented here is (X v Y v Z). Connect the literals in the variable gadgets to the matching literals in the clause gadgets with an edge. For example, if we have φ = (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ≥ x3) then we are looking for a vertex cover of size k = 3 + 2(3) = 9 on the graph in following figure: 

At this point the reduction is complete. We still have to prove that this reduction is correct, meaning that a vertex cover of size k = m + 2l exists if and only if the given is satisfiable.

Complexity Classes The branch of theoretical computer science known as computational complexity is concerned with classifying problems according to the computational resources required to solve them.

Almost all the algorithms we have studied thus far have been polynomial-time algorithms: on input of size n, their worst-case running time is O(n^k) for some constant k. However, not all problems can be solved in polynomial time.

From this assumption 3 Classes of Problems based on their computational complexity have been created: 

• Class P, consists of those problems that are solvable in polynomial time. 
• Class NP, consists of those problems that are verifiable in polynomial time. That is, if we were somehow given a "certificate" of a solution, then we could verify that the certificate is correct in time polynomial in the size of the input to the problem. Another way of saying the same thing is defining a problem in Class NP if and only if a nondeterministic algorithm can solve it in polynomial time.

Any problem in the class P is also in NP, since if a problem is in P then we can solve it in polynomial time without even being supplied a certificate. 

• Class NP - Complete, informally, a problem is in this class if it is in NP and is as "hard" as any problem in NP. Furthermore, if any NP-Complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. This peculiarity is given by the fact that each problem in NP can be polynomial reduced to an NP-Complete problem.

Cook's Theorem In computational complexity theory, the Cook-Levin Theorem, also known as Cook's Theorem, states that the boolean satisfiability is NP Complete. That is, any problem in NP can be reduced in polynomial time, by a deterministic Turing Machine to the problem of determining whether a boolean formula is satisfiable or not. 

Reductions Let us consider a decision problem A, which we would like to solve in polynomial time. We call the input to a particular problem an instance of that problem. Now, suppose that we already know how to solve a different decision problem B in polynomial time. Finally, suppose that we have a procedure that transforms any instance alpha of A into some instance beta of B with the following characteristics: 

• The transformation takes polynomial time.
• The answers are the same. That is, the answer for alpha is "yes" if and only if the answer for beta is also "yes".

We call such procedure a polynomial-time reduction algorithm and it provides us a way to solve problem A in polynomial time. 

Recalling that NP-Completeness is about showing how hard a problem is rather than how easy it is, we use polynomial-time reductions in the opposite way to show that a problem is NP-Complete. Let us take the idea a step further, and show how we could use polynomial-time reductions to show that no polynomial-time algorithm can exist for a particular problem B. Suppose we have a decision problem A for which we already know that no polynomial-time algorithm exist. Suppose further that we have a polynomial-time reduction transforming instances of A to instances of B. Now we can use a simple proof by contradiction to show that no polynomial-time algorithm can exist for B. Suppose otherwise, that is, suppose that B has a polynomial-time algorithm. Then we would have a way to solve problem A in polynomial time, which contradicts our assumption that there is no polynomial-time algorithm for A.