NP Completeness- SAT, CLIQUE (Part-1)

 

           Introduction

•We have been concerned with problems that are solvable in polynomial time i.e. the run-time can be bounded by O(nk) for some constant k.
•However there is another interesting class of problems that to this point are not solvable in polynomial time, i.e. we can do no better than brute force. This class of problems is intuitively known as NP-hard. Furthermore, in this class there are certain problems that are the "hardest" problems in the class which are known as NP-complete.
•Computability:
–Often we assume that all (well-posed) problems are computable, even if not efficiently. However in 1936 Alan Turing proved a problem that is incomputable known as the Halting Problem.

NP Completeness

•Complexity theory is a field that investigates the run-time of decision problems, i.e. problems that return true/false as the answer.
•While many of the problems we have looked at are optimization problems (e.g. minimum spanning trees, shortest paths, maximal flow, etc.), optimization problems can be recast as decision problems by simply asking "is the value of the solution < k for some constant k?" Foregoing problems that are incomputable, we would like to classify computable problems into "tractable".

Tractable/Intractable Problems

•Generally we think of problems that are solvable by polynomial time algorithms as being tractable (i.e. efficiently solvable) and problems that require super polynomial time as being intractable  (i.e. inefficiently solvable)..
•Sometimes the line between what is an ‘easy’ problem and what is a ‘hard’ problem is a fine one.
•For example, “Find the shortest path from vertex x to vertex y in a given weighted graph”. This can be solved efficiently without much difficulty.
•However, if we ask for the longest path (without cycles) from x to y, we have a problem for which no one knows a solution better than an exhaustive search.

Intractable Problems

•Can be classified in various categories based on their degree of difficulty, e.g.,
–NP
–NP-complete
–NP-hard

P Type:

•Deterministic Polynomial Time.
•Problems that are solvable in polynomial time.
•Running time is O(nk), for input size n and some constant k.
•P = { L | L is accepted by a deterministic Turing Machine in polynomial time }

NP Type

•Non-Deterministic polynomial time.
•Given a solution we can check that it is correct in polynomial time
•NP = { L | L is accepted by a non-deterministic Turing Machine in polynomial time }

P vs NP

•Any problem in P is also in NP:
•The big (and open question) is whether NP Í P or P = NP
–i.e., if it is always easy to check a solution, should it also be easy to find a solution?

•Most computer scientists believe that this is false but we do not have a proof …

NP Complete

•In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard.
•A problem B is NP-complete if:
•If B satisfies only property (2) we say that B is NP-hard.
•Within NP-hard class, we define a subset of problems that are the "hardest" ones which are known as NP-complete problems.
•These are the problems to which all other problems in NP can be reduced (i.e. recast into) in polynomial time.
•Thus if we can find a solution to ONE NP-complete problem, we can solve ALL NP-complete problems (which means all NP problems). If this solution is polynomial, then we will have proven that P = NP, i.e. all problems (in NP) have efficient solutions.
•The question of whether or not P = NP is one of the fundamental questions in CS and is the basis of much graduate level research. The "proof" would simply consist of finding ONE polynomial time solution to ANY NP-complete problem..

Reducibility

•In order to show that a new problem is also NP-complete, we will construct a (polynomial time) reduction from an instance of a known NP-complete problem (e.g. circuit Satisfiability) to an instance of the new problem.
•Thus if we could solve the new problem in polynomial time, we could solve the NP-complete problem in polynomial time by simply converting it to an instance of the new problem (in polynomial time), solving the new problem (in polynomial time), and then interpreting the decision result for the NP-complete problem (in polynomial time).
•Since every problem in NP can be represented as an instance of the original NP-complete problem, if we can show that every instance of the NP-complete problem can be reduced to an instance of the new problem, then the new problem must also be NP-complete (assuming the new problem is ∈ NP itself).
•This technique has been used to show many interesting problems are NP-complete.
Polynomial Reductions
•Given two problems A, B, we say that A is polynomialy reducible to B (A £p B) if:
1.There exists a function f  that converts the input of A to inputs of B in polynomial time.
2.A(i) = YES Û B(f(i)) = YES

  P Í NP
  (1) B Î NP

  (2) A £p B for all A Î NP