Complexity Theory - NP and NP-completeness

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.

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 :

All of these can be carried out by efficient algorithms.

In summary:

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 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

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'

Finding version of f (f itself)

which asks

Is there any witness W for I (with f)

and

Verifying version of f (Check(f))

which asks

Is this specific W 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 are P and NP related?

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:

Is P a proper subset of NP?

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)

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:

transform and S 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

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:

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 = NP if and only if f has an efficient algorithm (i.e. f is in P)

A decision problem, f, which has these properties, i.e. (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 single NP-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 one NP-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

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:

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

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

Cook's Theorem

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

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

Primality

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.

PED Home Page