NP-Completeness

Does P equal NP?  is probably the most important unsolved problem in theoretical computer science.

P and NP are classifications of decision problems.

A decision problem is a program whose output is a single bit.  (The input can be anything.)

Classic example of a decision problem.  Traveling Salesman.

Given a list of cities and their distances from each other and a total distance, is there a way to visit all the cities and return to the starting point without exceeding the given total distance?

NP-Completeness only applies to decision problems.

P is that class of decision problems that can be solved in polynomial time.

NP is that class of decision problems that can be solved in polynomial time on a non-deterministic machine.

How can I solve Traveling Salesman "quickly" (meaning in polynomial time) on a nondeterministic machine.

Using the metaphor of an infinite parallel machine.  I can have each processor select a different permutation of the cities.  (One processor gets ABCDE another ECABD, etc.)  Each processor works out the distance traveled to visit the cities in the order in which that processor has them, returning to the starting point, and checks to see if that number is less then or equal to the given total.  If it is, it ACCEPTS.  If it is not, it REJECTS.  If any processor ACCEPTS, the program is said to give the answer of YES.  If all processors REJECT, then it gives an answer of NO.  This is Theta (n) time on an NTM (nondeterministic Turing Machine).

But, on a regular machine, can Traveling Salesman be solved in polynomial time?  Nobody knows.  The best known algorithm involves trying every possible path to see whether there is a solution.  And that takes Theta (n!) time.  Traveling Salesman is certainly in NP.  But we don't know whether it's in P.

A "polynomial time reduction":  This is an algorithm that converts the input from decision problem A to decision problem B in such a way that the answer remains the same, and this conversion takes place in polynomial time.

Let's say A is Traveling Salesman.

Let's say B is Partition.  (Partition is:  given a collection of positive integers, is there a way to split them into two collections with identical sums?)

So, a reduction from A to B would involve taking the list of cities, their distances, and the total distance and building a collection of integers for partition to use.

A reduction from B to A would be to take a collection of positive integers and from these integers construct a list of cities, the distances between them, and a total distance, such that problem A could use it.

A reduction does not attempt to solve either A or B; it is simply a conversion from valid input of A to valid input B such that the answer to the problem remains the same.

So, if I have a certain input for problem A  and I run my reduction to get valid input for B, when A on its input and B on the input I gave it, I'd better have the same answer for both!


BAD REDUCTION:

I will take the input for Traveling Salesman, which is a set of cities, the distances between them, and a total distance.

If I can visit all the cities, returning to the starting point, without exceeding the total distance, I will pass the collection <2,2> to Partition.  So, if my Traveling Salesman input gives me a YES answer, I will give Partition input guaranteed to give a YES answer.

If I cannot visit all the cities within the total distance, I will pass the collection <1,2> to Partition.  So, my Traveling Salesman problem gives me a NO answer, I will give Partition input guaranteed to give a NO answer.

Why is this a "bad reduction?"

The reduction has to run in polynomial time.  The reduction above actually solves Traveling Salesman to determine what the input to Partition should be.  And there is no known algorithm that solves Traveling Salesman in polynomial time.

For a reduction to be meaningful it has to convert the input from one problem to another WITHOUT actually attempting to solve either problem.  (But they still have to both yield YES or both yield NO.)


A problem, A, in NP is NP-complete if, for EVERY problem, B, in NP there is a polynomial-time reduction from B to A.  (Every problem in NP reduces to A.)


SATISFIABILITY:  Given a logical expression with ands ors and nots and as many variables as you want, is there a "truth assignment" to those variables that makes the expression true?

For example P && Q && !R.  The answer here is YES.  If I set P to true, Q to true, and R to false, the expression P && Q && !R is true.

(P || Q) &&   (!P || Q)  && !Q.  Is there a way to make this logical expression true?  NO.  Q has to be false, and once we know Q is false, P has to be true to make the first clause true and false to make the second clause true.

Well, SATISFIABILITY is NP-complete.  Every single problem in NP reduces to SATISFIABILITY.

If problem A is in NP, and a known NP-Complete problem reduces to A then A is also NP-complete.

If B is a known NP-complete problem, then we know that every problem in NP reduces to B.  So, if we find just one reduction, from B to A, then we can reduce any problem in NP to A very simply.  First reduce it to B (polynomial time) and from B reduce it to A (polynomial time, using the algorithm we just came up with).  Total:  polynomial time.






<1,2,3,4>  Does Partition give yes or no?    <1,4>  <2,3> YES

<5,6,7>.  Does Partition give yes or no? NO

<2,2>  Does Partition give yes or no?  YES

<1,2>  Does Partition give yes or no?  NO