Complexity Theory - NP and NP-completeness

### The Complexity Class NP

Consider the following:

Composite:

Input: n-bit number, x

Output: 1 if x is a composite number; 0 otherwise.

Satisfiability: (SAT)

Input: A Boolean expression, F, over n variables (x1,. ..,xn)

Output: 1 if the variables of F can be fixed to values which make F equal true; 0 otherwise.

Hamiltonian Cycle (HC)

Input: n-node graph, G( V, E )

Output: 1 if there is a cycle of edges in G which includes each of the n nodes exactly once; 0 otherwise.

CLIQUE

Input: n-node graph G( V, E ); positive integer k

Output: 1 if there is a set of k nodes, W, in V such that every pair of nodes in W is joined by an edge in E; 0 otherwise.

3-Colourability (3-COL)

Input: n-node graph G(V,E)

Output: 1 if each node of G can be assigned one of three colours in such a way that no two nodes joined by an edge are given the same colour; 0 otherwise.

All 5 of these (and infinitely many other) decision problems share a certain property.

They are

### `Checkable' by efficient (polynomial time) algorithms

What does this mean?

In order to solve each of the decision problems above we have to demonstrate the existence of a particular object which has a certain relationship to the input.

That is, to show that:

x, is composite we `only' have to find a factor of x.

F(X) is satisfiable we `only' have to find an assignment to X that makes F true.

G(V,E) is hamiltonian we `only' have to find a suitable cycle in G.

G(V,E) has a k-clique we `only' have to find a suitable set of k nodes in V.

G(V,E) is 3-colourable we `only' have to find a suitable colouring of V

So for the examples:

Given an input instance, I, (number, Boolean expression, graph) one has to find a witness, W (number, assignment, cycle, set of nodes, colouring) such that a particular relationship holds between the witness and the input.

e.g.

• That W divides I with no remainder.
• That W makes I take the value true.
• That W is a cycle in I containing each node of I exactly once.
• That W is a set of k nodes in I each pair of which is connected by an edge of I.
• That W does not assign the same colour to two nodes in I which are joined by an edge of I.

How difficult is it to decide if something is indeed a valid witness for instances to these decision problems?

It is easy.

One can check if :

• W is a factor of I (by division)
• W satisfies I (by evaluating the expression)
• W is a hamiltonian cycle in I (by testing if I contains all the edges in W)
• W is a k-clique in I (test if each pair in W is joined by an edge of I)
• W is a colouring of I (test if each edge in I joins nodes with different colours in W)
All of these can be carried out by efficient algorithms.

In summary:

• For any decision problem, f, with each possible input size, n, there is a set of potential witnesses Wn.
• To solve a decision problem `all' that is needed is an algorithm to determine if there is a genuine witness, W is in Wn for any given input instance I of size n.

In principle, one could do this by going through each element, W of Wn, in turn and checking if W is a genuine witness for I.

However, the question

### `Is W a genuine witness for I' (for the decision problem f)

(e.g.
• Is y a factor of x? (for Composite)
• Does alpha make F(X) equal true? (for SAT)
• Is C a hamiltonian cycle in G(V,E)? (for HC)
• Is K a k-clique in G(V,E) (for Clique)
• Is chi is 3-colouring of G(V,E) (for 3-Col) )
is itself a decision problem (based on f)

So for any decision problem, f, we can define another decision problem, CHECK(f)

CHECK(f):

Input: I input instance for f; W possible witness that f(I)=1.

Output: 1 if W is a genuine witness that f(I)=1; 0 otherwise

Now we have seen that

• CHECK(Composite)
• CHECK(SAT)
• CHECK(HC)
• CHECK(Clique)
• CHECK(3-Col)
are all polynomial time decidable, i.e. all of these have efficient algorithms.

The notation, NP, denotes the class of all decision problems, f, with the property that CHECK(f) is polynomial time decidable,

### NP = { f : CHECK(f) is in P }

Thus for decision problems we have two `variants'

and

### Is this specificW a witness for I (with f)

P is the class of problems with efficient `finding' algorithms.

NP is the class of problems with efficient `verifying' algorithms.

### How arePandNPrelated?

If f is in P then certainly Check(f) is in P and so f is in NP also.

Thus,

### P is a subset of NP

Undoubtedly the most important open question in modern Computational Complexity Theory is:

### IsPa proper subset ofNP?

i.e. Are there decision problems f such that Check(f) is in P (i.e. f is in NP) but for which f is not in P.

Or, in informal terms,

Are there decision problems f such that checking a solution (witness) is much easier (polynomial time) than finding a solution?

The following problems are a fraction of the tens of thousands of problems which are known to be in NP but for which no efficient algorithm has been found (despite, in some cases, centuries of work on them)

• Hamiltonian Cycle
• Satisfiability
• 3-Colouring
• Clique
• Travelling Salesman Problem
• Integer Knapsack Problem
• Longest Path in a Graph
• Edge Colouring
• Optimal Scheduling
• Minimising Boolean Expressions
• Minimum Graph Partition
• Composite Number
• Primality
With the exception of the last 2, it is generally believed that no efficient algorithm exists for any of these decision problems. i.e. They are all intractable.

### This has yet to be proved.

The concept of NP-complete decision problems offers a possible route to resolving whether P = NP or P = NP.

### NP-completeness

The idea underlying the concept of NP-complete problems is to describe formally what can be understood as the

### `most difficult' problems in NP

That NP-complete problems are (intuitively) the most difficult in NP follows from the fact that we may prove

### P = NP

if and only if some NP-complete problem, f, has a polynomial-time algorithm

Suppose S and T are two decision problems and suppose we can construct an ADA program (algorithm) to solve T that is of the form

```procedure T is
x : T_input_type;
y : S_input_type;
function S ( z : S_input_type)
return boolean is
--***************************************
-- ADA function for decision problem S
-- goes in here.
--***************************************
end S;
function transform ( t : T_input_type)
return S_input_type is
--*****************************************
-- ADA function which transforms an
-- input instance for T into an input
-- instance for S.
--*****************************************
end transform;
begin
get (x);
y := transform (x);
if S(y) then
put (1);
else
put (0);
end if;
end T;
```
In this transform is a function which takes an input instance for T and changes it into an input instance for S. For example if T is a decision problem on numbers and S is one on graphs, then transform given a number would construct a graph using that number.

Now suppose that both:

### transformandS have efficient (polynomial) algorithms

Then the procedure above gives an efficient algorithm for T.

It follows that (with the above procedure form)

### There is an efficient algorithm for T

if there is an efficient algorithm for S

But, more importantly,

### If we can prove that there is NO efficient algorithm for S

then we have also proved that there is NO efficient algorithm for T

This means that if we have of an efficient procedure, tau which

• transforms input instances x for T into input instances, tau( x), for S
• is such that T( x ) = 1 if and only if S( tau( x ) ) = 1
Then we have established a relationship between the Time-Complexity of S and the Time-Complexity of T.

If S and T are decision problems for which such an efficient transformation procedure from inputs for T to inputs for S exists then we say that

### The decision problem T is polynomially reducible to the decision problem S

This relationship is denoted

### T < =p S

How does the idea of `polynomial reducibility' help in addressing the question of whether P equals NP?

Suppose we have a decision problem, f, for which we can prove the following:

• f is in NP, i.e. f there is an efficient checking algorithm for f.
• For every other decision problem, g in NP, it is the case that g < =p f,
i.e. for every decision problem, g with an efficient checking algorithm there is an efficient procedure, tau-g, that transforms inputs for g into inputs for f.

Then if there are decision problems in NP for which efficient algorithms do not exist then

### the decision problem f must be one such problem

In other words, for such a decision problem f:

### P = NPif and only iff has an efficient algorithm (i.e. f is in P)

A decision problem, f, which has these properties, i.e.
• f is in NP
• For all g in NP, g < =p f
(f has an efficient checking algorithm and every problem with an efficient checking algorithm can be efficiently transformed to f) is called an

### NP-complete decision problem

The NP-complete decision problems are the `most difficult' problems in NP in the sense that if

### Any singleNP-complete problem does not have an efficient algorithm

then NO NP-complete problem has an efficient algorithm Conversely

### If we find an efficient algorithm for just oneNP-complete problem

then we can construct efficient algorithms for all decision problems in NP

Problem: The definition of NP-completeness requires the following to be done in order to show that a problem f is NP-complete

• We have to find an efficient checking algorithm for f (i.e. prove f is in NP)
• We have to show that every problem with an efficient checking algorithm can be transformed into f (i.e. prove for all g in NP, g < =p f)
The first is usually (relatively) easy.

But for the second, how can we reduce infinitely many decision problems to a single problem?

Before dealing with this we can note the following: suppose we have shown for two decision problems, f and g say, that:

• f is NP-complete.
• g is in NP
• f < =p g
Then we have also shown that g is NP-complete.

Why?

So we have a polynomial reduction from every problem in NP to g by

• Converting an input instance x for h (in NP) to one tau(h)(x) for f.
• Converting the input tau(h)(x) for f to an input instance for g.
The first is possible since f is NP-complete. The second since there is a polynomial reduction from f to g.

This argument shows that once we have identified a single NP-complete decision problem, f, in order to prove that another decision problem, g, is NP-complete `all' we have to do is find an efficient algorithm for transforming input instances for f into input instances for g, i.e. prove

### f < =p g

But, this still leaves the problem of finding a `first' NP-complete problem, that is of finding some way of

### transforming infinitely many decision problems into just one decision problem

In 1971 Steven Cook proved one of the most important results in modern computational complexity theory. This result is (now) known as

### SAT is NP-complete

Proof: Omitted (not difficult, just long)

Within a few months of Cook's result dozens of new NP-complete problems had been identified. By 1994 well over 10,000 basic NP-complete decision problems were known.

Thus it is known that the following problems are all NP-complete

• CLIQUE
• Hamiltonian Cycle
• Travelling Salesman Problem
• 3-Colouring
• Set Partitioning
• Edge Colouring
• Longest Path
• Integer Knapsack
A proof that a decision problem is NP-complete is accepted as evidence that the problem is intractable since a fast method of solving a single NP-complete problem would immediately give fast algorithms for all NP-complete problems.

It generally though to be extremely unlikely that any NP-complete problem has a fast algorithm.

It has still to be proved that any NP-complete problem does not have an efficient algorithm, i.e. the question of whether P=NP is still open.

While most of the classical decision problems have now been determined as being in P or being NP-complete a number of important problems are still open. In particular

### Composite Number

Both are known to be in NP. Neither has been shown to be NP-complete. It is believed that both are in fact solvable by efficient algorithms.