Introduction to NP completeness

Category: Entertainment

Presentation Description

No description available.


Presentation Transcript

Introduction To NP-Completeness:

Introduction To NP-Completeness

Importance of NP-completeness:

Most of the algorithms we have studied have polynomial-time running times and the polynomial time algorithms are considered to be tractable. But no polynomial time algorithm has yet been discovered for any NP-complete problem and therefore are intractable , which needs the design of good approximation algorithm Importance of NP-completeness

Decision problem vs. Optimization problem:

In Decision problems we are trying to decide whether a statement is true or false. In Optimization problem we are trying to find the solution with the best possible score according to some scoring scheme. Optimization problem can either be maximization problem , where we are trying to maximize a certain score, or minimization problem ,where we are trying to minimize a cost function. Decision problem vs. Optimization problem


NP-Completeness has been studied in the framework of decision problems.Most problems are not decision problems , but optimization problem. In order to apply the theory of NP-Completeness to optiimization problems , we must recast them as decision problems. If the optimization problem is easy , then related decision problem is easy as well. Contd..

The class P:

Class P contains those decision problems that are solvable in polynomial time. They are problems that can be solved in O( n k ) time, where n is the input size and k is a constant. Example: The Minimization spanning tree problem is in class p. The class P

PowerPoint Presentation:

Formally the class P is defined as p={L | L=L(M) for some Turing machine M that runs in polynomial time} where L(M) is the language accepted by M solved by conventional computer in polynomial time O(1) constant O(log n) sub-linear O(n) linear O(n log n) nearly linear O(n 2 ) quadratic polynomial upper and lower bounds

The class NP:

NP is the set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time. Intuitively, NP is the set of decision problems where we can verify a YES answer quickly if we have the solution in front of us. The class NP


For example, the circuit satisfiability problem is in NP. If the answer is YES, then any set of m input values that produces TRUE output is a proof of this fact; we can check the proof by evaluating the circuit in polynomial time. Contd..

The class co-NP:

Co-NP is the opposite of NP. If the answer to a problem in co-NP , then there is a proof of this fact that can be checked in polynomial time. UNSAT : Given a boolean formula p, does p has no satisfiable assignment ? The class co-NP

Relationship between class P , NP and co-NP:

The class of question for which the answer is YES can be verified is called class NP. So P ⊆ NP The class of question for which the answer is NO can be verified is called class co-NP. So P ⊆ co-NP So, P ⊆ NP ∩ co-NP Relationship between class P , NP and co-NP

PowerPoint Presentation:

Whether P = NP ? for that we have to show, NP ⊆ P That is enough to show that if the optimization version of an NP-complete problem can be solved in polynomial time, then P = NP . A strong argument that you cannot solve the optimization version of an NP-complete problem in polynomial time.

Reduction -- Transformation:

The process of changing a problem to another problem. A problem Q is being reduced to another problem Q’– if any instance of Q can be easily rephrased as an instance of Q’. And hence-- the solution of the instance of Q’ is going to help to find out the solution of the instance of Q. Reduction -- Transformation

Yes, but ..What IS Reduction?? An Informal example:

Yes, but ..What IS Reduction?? An Informal example

Points to be noted:

It means Sorting is “no harder to solve” than Finding-Min We are ignoring the type of problem or the time complexity of ‘Finding-Min’ problem and ‘Sorting’ problem Checking whether the activity of Reducer , which does a Reduction , is performed in Polynomial time or not. Points to be noted

A Formal Example:

A solution to a linear equation ax + b = 0 is a problem It can be transformed to 0x2 + ax + b = 0 -- a quadratic equation The quadratic equation’s solution can be achieved by applying Shridhar Acharya Rule . --Hence this will provide a solution to the Linear equation’s solution A Formal Example

Why Reducibility is needed?:

On checking whether the problem is polynomial-time reducible to another problem will let us know the nature of the problem. We can say the hardness of a problem is almost same as that kind of a problem from which it is being reduced to. Why Reducibility is needed?

Reduction Function:

Using the method of Encoding , we can express a problem (specifically input instance) to a machine ( turing machine) understandable language/expression (Formal language). A formal language L’ is polynomial-time reducible to L, denoted as: L’  p L , if there exists a polynomial-time computable function f: {0,1}* → {0,1}* such that for all x  {0,1}*, x L’ if and only if f (x)  L The function f is reduction function and the polynomial-time algorithm F that computes f is a reduction algorithm . Reduction Function

Definition of NP-Hard and NP-Complete in light of Reducibility:

A Language L  {0,1}* . 1. L’  p L for every L ’  NP 2. L NP Property 1 is satisfied : L is NP-Hard Both Property 1 and 2 are satisfied: L is NP-Complete Definition of NP-Hard and NP-Complete in light of Reducibility

Satisfiability : the motivation:

By definition, to show a problem is NP complete, we use Reducibility. For that, initially at least one problem is to proved NP complete. This initial problem can be reduced in polynomial time to prove that other problems can be NP complete (and NP hard). Satisfiability : the motivation

Circuit Satisfiability Problem:

Problem statement: Given a Boolean Combinational Circuit composed of AND , OR and NOT gates, is it satisfiable? CIRCUIT-SAT={< C > : C is a satisfiable boolean combinational circuit} For a Boolean Combinational Circuit C, we say C has satisfying assignment when the truth assignments of the input variables finally makes the output evaluated as 1. Circuit Satisfiability Problem

CIRCUIT-SAT is NP: verification:

Providing a 2-input polynomial-time algorithm A which can verify CIRCUIT-SAT is possible. A checks that for each logic gate in the circuit, the values provided by the truth assignment computes the correct value of the final output. Whenever a satisfiable circuit C is input to A , there exists a satisfying assignment that causes the output of A to be 1. For unsatisfiable circuit C as input, output is 0. As algorithm A itself is polynomial, CIRCUIT-SAT is verified in polynomial time. CIRCUIT-SAT is NP: verification

Formula satisfiability Problem :

1 st ever problem to be proved as NP-complete. Problem statement: Given a boolean formula (consisting of variables, connectives and parentheses), is it satisfiable? The formal language form: SAT={< ɸ > : ɸ is a satisfiable boolean formula } Formula satisfiability Problem

SAT (contd.):

Example: ɸ = (x1→x2) ⋁ ˥ ((˥x1↔x3) ⋁x4)) ⋀˥x2 This has the satisfying assignment: x1=0, x2=0, x3=1, x4=1. Cook-Levin’s Theorem : SAT is NP-Complete Verification: T he Boolean formula ɸ or any arbitrary satisfiable Boolean formula does not run in polynomial time. SAT (contd.)

SAT is NP : verification:

A formula with m variables has 2 m possible assignments. If the length of ɸ is polynomial, then checking every assignment would take ( 2 m ) time. It is superpolynomial. Hence it is verifiable with the help of certificate assignments. SAT is NP : verification

NP Completeness: examples:



Clique Clique is a subset of vertices in an undirected graph such that each vertex in the subset is adjacent to all the other vertices in the subset. The clique decision problem is to determine for a graph and a positive integer ‘k’ whether the graph has a clique containing at least k vertices.

An example of clique:

An example of clique

To prove clique to be in NP-complete:

Prove the clique to be in NP. Prove that some NP Complete problem B reduces to a clique. NP: A problem is said to be NP if its solution comes from a finite set of possibilities, and it takes polynomial time to verify the correctness of a candidate solution . To prove clique to be in NP-complete

NP Algorithm for clique:

An NP algorithm is an algorithm that has 2 stages: The first stage is a guessing stage that uses choose() to find a solution to the problem. The second stage is verification, which checks the correctness of the solution produced by the first stage. The time of this stage is polynomial in the input size n. NP Algorithm for clique

Behavior of Choose():

Behavior of "choose()": if a problem has a solution of N components, choose(i) magically returns the i-th component of the CORRECT solution in constant time if a problem has no solution, choose(i) returns mere "garbage", that is, it returns an uncertain value. Behavior of Choose()

The algorithm:

begin /* The following for-loop is the guessing stage*/ for i =1 to k do X[ i ] := choose( i ); endfor /* Next is the verification stage */ for i =1 to k do for j=i+1 to k do if (X[ i ] = X[j] or (X[ i ],X[j]) is not an edge) then return(no); endif endfor endfor return(yes); end The algorithm


The solution size of the k-clique is O(k)=O(n), and the time of the verification stage is O(n 2 ). Therefore, the k-clique problem is NP. Complexity

NP-Completeness of the K-Clique Problem:

The k-clique problem was already shown to be NP. It remain to prove that an NP-complete problem reduces to k-clique . NP-Completeness of the K-Clique Problem


3SAT is NP Complete problem. 3SAT reduces to the k-clique problem. B is a logical expressionin CNF (Conjunctive Normal Form). B= C₁ ^ C₂ ^ C₃ ^ C₄ ^ …………… ^Cĸ Here C₁= Clause of B x₁……..xn= Variables in B. 3SAT

PowerPoint Presentation:

Transform B to graph G(V,E) V={( y,i ) such that y is a literal in clause C і } E={(( y,i )( z,j )) such that i != j and z̄!= y} B= (x₁ v x₂ v x̄₃) Λ (x₁ v x̄₂ v x₃)

3SAT Continued..:

3SAT is satisfiable, if one variable from each clause should be true. (x₁ v x̄₂ v x̄₃) Λ ( x̄₁ v x₂ v x₃) Λ (x₁ v x₂ v x₃ ) To prove 3SAT is reducible to Clique we need to show that B is CNF-satisfiable if and only if G has a clique of at least k. 3SAT Continued..

Proof of NP Completeness for clique:

1. Necessary Condition : Given- B is CNF satisfiable To prove-G has a clique of size atleast k. If B is CNF satisfiable ,there are truth assignments for x₁…….. xĸ such that each clause is true with these assignments. This means that there is atleast one literal in each C і that is true. V’={( y,i ) such that y is the true literal picked from Ci } Therefore V’ forms a clique in G of size k. Proof of NP Completeness for clique


2.Sufficient Condition: Given- G has a Clique of size at least k To prove- B is CNF satisfiable. Contd..


So if G has a clique (V’,E’) of size at least k the no. of vertices in V’ must be exactly k. - Therefore if we set S={ y such that (y,i) є V’ } S contains k literals. S contains a literal from each of the k clauses because there is no edge connecting (y,i) and (z,i) for any literals y and z and index i. Contd..


Finally S cannot contain both a literal y and its complement ȳ because there is no edge connecting (y, i) and (ȳ ,j) for any i and j. therefore if we set xi= true if xi є S = false if x̄i є S And assign arbitrary values to variables not in S,all clauses in B are true. Therefore B is CNF satisfiable. Contd..

authorStream Live Help