+ All Categories
Home > Engineering > 27 NP Completness

27 NP Completness

Date post: 14-Apr-2017
Category:
Upload: andres-mendez-vazquez
View: 292 times
Download: 2 times
Share this document with a friend
401
Analysis of Algorithms NP-Completeness Andres Mendez-Vazquez November 30, 2015 1 / 163
Transcript
Page 1: 27 NP Completness

Analysis of AlgorithmsNP-Completeness

Andres Mendez-Vazquez

November 30, 2015

1 / 163

Page 2: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

2 / 163

Page 3: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

3 / 163

Page 4: 27 NP Completness

Polynomial Time

Algorithms Until NowAll the algorithms, we have studied this far have been polynomial-timealgorithms.

HoweverThere is a collection of algorithms that cannot being solved inpolynomial time!!!

ExampleIn the Turing’s “Halting Problem,” we cannot even say if thealgorithm is going to stop!!!

4 / 163

Page 5: 27 NP Completness

Polynomial Time

Algorithms Until NowAll the algorithms, we have studied this far have been polynomial-timealgorithms.

HoweverThere is a collection of algorithms that cannot being solved inpolynomial time!!!

ExampleIn the Turing’s “Halting Problem,” we cannot even say if thealgorithm is going to stop!!!

4 / 163

Page 6: 27 NP Completness

Polynomial Time

Algorithms Until NowAll the algorithms, we have studied this far have been polynomial-timealgorithms.

HoweverThere is a collection of algorithms that cannot being solved inpolynomial time!!!

ExampleIn the Turing’s “Halting Problem,” we cannot even say if thealgorithm is going to stop!!!

4 / 163

Page 7: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

5 / 163

Page 8: 27 NP Completness

The Intuition

Class PThey are algorithms that on inputs of size n have a worst case runningtime of O

(nk)for some constant k.

Class NPInformally, the Non-Polynomial (NP) time algorithms are the ones thatcannot be solved in O

(nk)for any constant k.

6 / 163

Page 9: 27 NP Completness

The Intuition

Class PThey are algorithms that on inputs of size n have a worst case runningtime of O

(nk)for some constant k.

Class NPInformally, the Non-Polynomial (NP) time algorithms are the ones thatcannot be solved in O

(nk)for any constant k.

6 / 163

Page 10: 27 NP Completness

There are still many thing to say about NP problems

But the one that is making everybody crazyThere is a theorem that hints to a possibility of NP = P

ThusWe have the following vision of the world of problems in computer science.

7 / 163

Page 11: 27 NP Completness

There are still many thing to say about NP problems

But the one that is making everybody crazyThere is a theorem that hints to a possibility of NP = P

ThusWe have the following vision of the world of problems in computer science.

7 / 163

Page 12: 27 NP Completness

The Two Views of The World

The Paradox

Incr

easi

ng C

om

ple

xit

y

NP-Hard NP-Hard

NP-Complete

NP

P

P=NP=NP-Complete

8 / 163

Page 13: 27 NP Completness

However, There are differences pointing to P 6= NP

Shortest Path is in PEven with negative edge weights, we can find a shortest path for a singlesource in a directed graph G = (V ,E) in O (VE) time.

Longest Path is in NPMerely determining if a graph contains a simple path with at least a givennumber of edges is NP.

It is moreA simple change on a polynomial time problem can move it from P to NP.

9 / 163

Page 14: 27 NP Completness

However, There are differences pointing to P 6= NP

Shortest Path is in PEven with negative edge weights, we can find a shortest path for a singlesource in a directed graph G = (V ,E) in O (VE) time.

Longest Path is in NPMerely determining if a graph contains a simple path with at least a givennumber of edges is NP.

It is moreA simple change on a polynomial time problem can move it from P to NP.

9 / 163

Page 15: 27 NP Completness

However, There are differences pointing to P 6= NP

Shortest Path is in PEven with negative edge weights, we can find a shortest path for a singlesource in a directed graph G = (V ,E) in O (VE) time.

Longest Path is in NPMerely determining if a graph contains a simple path with at least a givennumber of edges is NP.

It is moreA simple change on a polynomial time problem can move it from P to NP.

9 / 163

Page 16: 27 NP Completness

And here, a simplified classification of problems

Different Complexity ClassesComplexity Class Model of Computation Resource Constraint

P Deterministic Turing Machine Solvable using poly(n) timeNP Non-deterministic Turing Machine Verifiable in poly(n) time

PSPACE Deterministic Turing Machine Solvable using poly(n) SpaceEXPTIME Deterministic Turing Machine Solvable using 2poly(n) timeEXPSPACE Deterministic Turing Machine Space 2poly(n)

NL Non-deterministic Turing Machine Space O (log n)

10 / 163

Page 17: 27 NP Completness

Graphically

What is contained into what

NL

P

NP

PSPACE

EXPTIME

EXSPACE

Beyond the Turing Machine

Halting Problem

11 / 163

Page 18: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

12 / 163

Page 19: 27 NP Completness

We start by formalizing the notion of polynomial time

Polynomial Time ProblemsWe generally regard these problems as tractable, but for philosophical, notmathematical, reasons.

FirstIt is possible to regard a problem with complexity O

(n100) as intractable,

really few practical problems require time complexities with such highdegree polynomial.

It is moreExperience has shown that once the first polynomial-time algorithm for aproblem has been discovered, more efficient algorithms often follow.

13 / 163

Page 20: 27 NP Completness

We start by formalizing the notion of polynomial time

Polynomial Time ProblemsWe generally regard these problems as tractable, but for philosophical, notmathematical, reasons.

FirstIt is possible to regard a problem with complexity O

(n100) as intractable,

really few practical problems require time complexities with such highdegree polynomial.

It is moreExperience has shown that once the first polynomial-time algorithm for aproblem has been discovered, more efficient algorithms often follow.

13 / 163

Page 21: 27 NP Completness

We start by formalizing the notion of polynomial time

Polynomial Time ProblemsWe generally regard these problems as tractable, but for philosophical, notmathematical, reasons.

FirstIt is possible to regard a problem with complexity O

(n100) as intractable,

really few practical problems require time complexities with such highdegree polynomial.

It is moreExperience has shown that once the first polynomial-time algorithm for aproblem has been discovered, more efficient algorithms often follow.

13 / 163

Page 22: 27 NP Completness

Reasons

SecondFor many reasonable models of computation, a problem that can be solvedin polynomial time in one model can be solved in polynomial time inanother.

ExampleProblems that can be solved in polynomial time by a serial random-accessmachine can be solved in a Turing Machine.

ThirdThe class of polynomial-time solvable problems has nice closureproperties.Since polynomials are closed under addition, multiplication, andcomposition.

14 / 163

Page 23: 27 NP Completness

Reasons

SecondFor many reasonable models of computation, a problem that can be solvedin polynomial time in one model can be solved in polynomial time inanother.

ExampleProblems that can be solved in polynomial time by a serial random-accessmachine can be solved in a Turing Machine.

ThirdThe class of polynomial-time solvable problems has nice closureproperties.Since polynomials are closed under addition, multiplication, andcomposition.

14 / 163

Page 24: 27 NP Completness

Reasons

SecondFor many reasonable models of computation, a problem that can be solvedin polynomial time in one model can be solved in polynomial time inanother.

ExampleProblems that can be solved in polynomial time by a serial random-accessmachine can be solved in a Turing Machine.

ThirdThe class of polynomial-time solvable problems has nice closureproperties.Since polynomials are closed under addition, multiplication, andcomposition.

14 / 163

Page 25: 27 NP Completness

Reasons

Why?For example, if the output of one polynomial time algorithm is fed into theinput of another, the composite algorithm is polynomial.

15 / 163

Page 26: 27 NP Completness

Polynomial time

To understand a polynomial time we need to define:What is the meaning of an abstract problem?How to encode problems.A formal language framework.

16 / 163

Page 27: 27 NP Completness

Polynomial time

To understand a polynomial time we need to define:What is the meaning of an abstract problem?How to encode problems.A formal language framework.

16 / 163

Page 28: 27 NP Completness

Polynomial time

To understand a polynomial time we need to define:What is the meaning of an abstract problem?How to encode problems.A formal language framework.

16 / 163

Page 29: 27 NP Completness

Polynomial time

To understand a polynomial time we need to define:What is the meaning of an abstract problem?How to encode problems.A formal language framework.

16 / 163

Page 30: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

17 / 163

Page 31: 27 NP Completness

What do we need to understand the polynomial time?What is an abstract problem?We define an abstract problem Q to be a binary relation on a set I ofproblem instances and a set S of problem solutions:

Q : I → S , Q(i) = s (1)

Q

I S

i Q(i)=s

18 / 163

Page 32: 27 NP Completness

Abstract problem as decision problems

Something NotableThe formulation is too general to our purpose!!!

Thus, we do a restrictionThe theory of NP-completeness restricts attention to decision problems:

Those having a YES/NO solution.

ThenWe can view an abstract decision problem as a function that maps theinstance set I to the solution set 0, 1:

Q : I → 0, 1

19 / 163

Page 33: 27 NP Completness

Abstract problem as decision problems

Something NotableThe formulation is too general to our purpose!!!

Thus, we do a restrictionThe theory of NP-completeness restricts attention to decision problems:

Those having a YES/NO solution.

ThenWe can view an abstract decision problem as a function that maps theinstance set I to the solution set 0, 1:

Q : I → 0, 1

19 / 163

Page 34: 27 NP Completness

Abstract problem as decision problems

Something NotableThe formulation is too general to our purpose!!!

Thus, we do a restrictionThe theory of NP-completeness restricts attention to decision problems:

Those having a YES/NO solution.

ThenWe can view an abstract decision problem as a function that maps theinstance set I to the solution set 0, 1:

Q : I → 0, 1

19 / 163

Page 35: 27 NP Completness

Abstract problem as decision problems

Something NotableThe formulation is too general to our purpose!!!

Thus, we do a restrictionThe theory of NP-completeness restricts attention to decision problems:

Those having a YES/NO solution.

ThenWe can view an abstract decision problem as a function that maps theinstance set I to the solution set 0, 1:

Q : I → 0, 1

19 / 163

Page 36: 27 NP Completness

Example

Example of optimization problem: SHORTEST-PATHThe problem SHORTEST-PATH is the one that associates each graph Gand two vertices with the shortest path between them.

Problem, this is a optimization problemWe need a decision problem!!!

What do we do?We can cast a given optimization problem as a related decision problem byimposing a bound on the value to be optimized.

20 / 163

Page 37: 27 NP Completness

Example

Example of optimization problem: SHORTEST-PATHThe problem SHORTEST-PATH is the one that associates each graph Gand two vertices with the shortest path between them.

Problem, this is a optimization problemWe need a decision problem!!!

What do we do?We can cast a given optimization problem as a related decision problem byimposing a bound on the value to be optimized.

20 / 163

Page 38: 27 NP Completness

Example

Example of optimization problem: SHORTEST-PATHThe problem SHORTEST-PATH is the one that associates each graph Gand two vertices with the shortest path between them.

Problem, this is a optimization problemWe need a decision problem!!!

What do we do?We can cast a given optimization problem as a related decision problem byimposing a bound on the value to be optimized.

20 / 163

Page 39: 27 NP Completness

Thus

Example PATH ProblemGiven a undirected graph G, vertices u and v, and an integer k, we needto answer the following question:

Does a path exist from u to v consisting of at most k edges?

21 / 163

Page 40: 27 NP Completness

In a more formal way

We have the following optimization problemmin

td [t]

s.t.d[v] ≤ d[u] + w(u, v) for each edge (u, v) ∈ Ed [s] = 0

Then, we have the following decision problemPATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,

u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

22 / 163

Page 41: 27 NP Completness

In a more formal way

We have the following optimization problemmin

td [t]

s.t.d[v] ≤ d[u] + w(u, v) for each edge (u, v) ∈ Ed [s] = 0

Then, we have the following decision problemPATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,

u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

22 / 163

Page 42: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

23 / 163

Page 43: 27 NP Completness

Why Encoding?

We need to represent our problems in a way that the Turing machinecan understand.That is called an encoding.

ExampleGiven a graph G = (V ,E):

We can encode each vertex 1, 2, ... as 0, 1, 10, ...Then, each edge, for example 1, 2 as 0, 1Clearly you need to encode some kind of delimiter for each element inthe description

24 / 163

Page 44: 27 NP Completness

Why Encoding?

We need to represent our problems in a way that the Turing machinecan understand.That is called an encoding.

ExampleGiven a graph G = (V ,E):

We can encode each vertex 1, 2, ... as 0, 1, 10, ...Then, each edge, for example 1, 2 as 0, 1Clearly you need to encode some kind of delimiter for each element inthe description

24 / 163

Page 45: 27 NP Completness

Why Encoding?

We need to represent our problems in a way that the Turing machinecan understand.That is called an encoding.

ExampleGiven a graph G = (V ,E):

We can encode each vertex 1, 2, ... as 0, 1, 10, ...Then, each edge, for example 1, 2 as 0, 1Clearly you need to encode some kind of delimiter for each element inthe description

24 / 163

Page 46: 27 NP Completness

Why Encoding?

We need to represent our problems in a way that the Turing machinecan understand.That is called an encoding.

ExampleGiven a graph G = (V ,E):

We can encode each vertex 1, 2, ... as 0, 1, 10, ...Then, each edge, for example 1, 2 as 0, 1Clearly you need to encode some kind of delimiter for each element inthe description

24 / 163

Page 47: 27 NP Completness

Why Encoding?

We need to represent our problems in a way that the Turing machinecan understand.That is called an encoding.

ExampleGiven a graph G = (V ,E):

We can encode each vertex 1, 2, ... as 0, 1, 10, ...Then, each edge, for example 1, 2 as 0, 1Clearly you need to encode some kind of delimiter for each element inthe description

24 / 163

Page 48: 27 NP Completness

Why a Turing machine or a RAM machine?

Given an encoding...We need a computational device to solve the encoded problem

Some factsThis means that when the device solves a problem in reality solves theencoded version of Q.This encoded problem is called a concrete problem.This tells us how important encoding is!!!

25 / 163

Page 49: 27 NP Completness

Why a Turing machine or a RAM machine?

Given an encoding...We need a computational device to solve the encoded problem

Some factsThis means that when the device solves a problem in reality solves theencoded version of Q.This encoded problem is called a concrete problem.This tells us how important encoding is!!!

25 / 163

Page 50: 27 NP Completness

Why a Turing machine or a RAM machine?

Given an encoding...We need a computational device to solve the encoded problem

Some factsThis means that when the device solves a problem in reality solves theencoded version of Q.This encoded problem is called a concrete problem.This tells us how important encoding is!!!

25 / 163

Page 51: 27 NP Completness

Why a Turing machine or a RAM machine?

Given an encoding...We need a computational device to solve the encoded problem

Some factsThis means that when the device solves a problem in reality solves theencoded version of Q.This encoded problem is called a concrete problem.This tells us how important encoding is!!!

25 / 163

Page 52: 27 NP Completness

It is more!!!

We want time complexities of O (T (n))When it is provided with a problem instance i of length |i| = n.

ThenThe algorithm can produce the solution in O (T (n)).

26 / 163

Page 53: 27 NP Completness

It is more!!!

We want time complexities of O (T (n))When it is provided with a problem instance i of length |i| = n.

ThenThe algorithm can produce the solution in O (T (n)).

26 / 163

Page 54: 27 NP Completness

Using Encodings

Something NotableGiven an abstract decision problem Q mapping an instance set I to 0, 1.

ThenAn encoding e : I −→ 0, 1∗ can induce a related concrete decisionproblem, denoted as by e (Q).

IMPORTANTIf the solution to an abstract-problem instance i ∈ I is Q (i) ∈ 0, 1.Then the solution to the concrete-problem instance e (i) ∈ 0, 1∗ isalso Q (i).

27 / 163

Page 55: 27 NP Completness

Using Encodings

Something NotableGiven an abstract decision problem Q mapping an instance set I to 0, 1.

ThenAn encoding e : I −→ 0, 1∗ can induce a related concrete decisionproblem, denoted as by e (Q).

IMPORTANTIf the solution to an abstract-problem instance i ∈ I is Q (i) ∈ 0, 1.Then the solution to the concrete-problem instance e (i) ∈ 0, 1∗ isalso Q (i).

27 / 163

Page 56: 27 NP Completness

Using Encodings

Something NotableGiven an abstract decision problem Q mapping an instance set I to 0, 1.

ThenAn encoding e : I −→ 0, 1∗ can induce a related concrete decisionproblem, denoted as by e (Q).

IMPORTANTIf the solution to an abstract-problem instance i ∈ I is Q (i) ∈ 0, 1.Then the solution to the concrete-problem instance e (i) ∈ 0, 1∗ isalso Q (i).

27 / 163

Page 57: 27 NP Completness

Using Encodings

Something NotableGiven an abstract decision problem Q mapping an instance set I to 0, 1.

ThenAn encoding e : I −→ 0, 1∗ can induce a related concrete decisionproblem, denoted as by e (Q).

IMPORTANTIf the solution to an abstract-problem instance i ∈ I is Q (i) ∈ 0, 1.Then the solution to the concrete-problem instance e (i) ∈ 0, 1∗ isalso Q (i).

27 / 163

Page 58: 27 NP Completness

What do we want?

Something NotableWe would like to extend the definition of polynomial-time solvability fromconcrete problems to abstract problems by using encodings as the bridge.

IMPORTANT!!!We want the definition to be independent of any particular encoding.

In other wordsThe efficiency of solving a problem should not depend on how the problemis encoded.

HOWEVER, it depends quite heavily on the encoding.

28 / 163

Page 59: 27 NP Completness

What do we want?

Something NotableWe would like to extend the definition of polynomial-time solvability fromconcrete problems to abstract problems by using encodings as the bridge.

IMPORTANT!!!We want the definition to be independent of any particular encoding.

In other wordsThe efficiency of solving a problem should not depend on how the problemis encoded.

HOWEVER, it depends quite heavily on the encoding.

28 / 163

Page 60: 27 NP Completness

What do we want?

Something NotableWe would like to extend the definition of polynomial-time solvability fromconcrete problems to abstract problems by using encodings as the bridge.

IMPORTANT!!!We want the definition to be independent of any particular encoding.

In other wordsThe efficiency of solving a problem should not depend on how the problemis encoded.

HOWEVER, it depends quite heavily on the encoding.

28 / 163

Page 61: 27 NP Completness

An example of a really BAD situation

Imagine the followingYou could have an algorithm that takes k as the sole input with analgorithm that runs in Θ(k).

Now, if the integer is provided in an unary representation (Only ones)Quite naive!!!

ThenRunning time of the algorithm is O(n) on n-length inputs, which ispolynomial.

29 / 163

Page 62: 27 NP Completness

An example of a really BAD situation

Imagine the followingYou could have an algorithm that takes k as the sole input with analgorithm that runs in Θ(k).

Now, if the integer is provided in an unary representation (Only ones)Quite naive!!!

ThenRunning time of the algorithm is O(n) on n-length inputs, which ispolynomial.

29 / 163

Page 63: 27 NP Completness

An example of a really BAD situation

Imagine the followingYou could have an algorithm that takes k as the sole input with analgorithm that runs in Θ(k).

Now, if the integer is provided in an unary representation (Only ones)Quite naive!!!

ThenRunning time of the algorithm is O(n) on n-length inputs, which ispolynomial.

29 / 163

Page 64: 27 NP Completness

For example

Now, use the more natural binary representation of the integer kNow, given a binary representation:

I Thus the input length is n = blog kc+ 1→ Θ (k) = Θ (2n)

RemarkThus, depending on the encoding, the algorithm runs in either polynomialor superpolynomial time.

30 / 163

Page 65: 27 NP Completness

For example

Now, use the more natural binary representation of the integer kNow, given a binary representation:

I Thus the input length is n = blog kc+ 1→ Θ (k) = Θ (2n)

RemarkThus, depending on the encoding, the algorithm runs in either polynomialor superpolynomial time.

30 / 163

Page 66: 27 NP Completness

For example

Now, use the more natural binary representation of the integer kNow, given a binary representation:

I Thus the input length is n = blog kc+ 1→ Θ (k) = Θ (2n)

RemarkThus, depending on the encoding, the algorithm runs in either polynomialor superpolynomial time.

30 / 163

Page 67: 27 NP Completness

More Observations

ThusHow we encode an abstract problem matters quite a bit to how weunderstand it!!!

It is moreWe cannot talk about solving an abstract problem without specifying theencoding!!!

NeverthelessIf we rule out expensive encodings such as unary ones, the actual encodingof a problem makes little difference to whether the problem can be solvedin polynomial time.

31 / 163

Page 68: 27 NP Completness

More Observations

ThusHow we encode an abstract problem matters quite a bit to how weunderstand it!!!

It is moreWe cannot talk about solving an abstract problem without specifying theencoding!!!

NeverthelessIf we rule out expensive encodings such as unary ones, the actual encodingof a problem makes little difference to whether the problem can be solvedin polynomial time.

31 / 163

Page 69: 27 NP Completness

More Observations

ThusHow we encode an abstract problem matters quite a bit to how weunderstand it!!!

It is moreWe cannot talk about solving an abstract problem without specifying theencoding!!!

NeverthelessIf we rule out expensive encodings such as unary ones, the actual encodingof a problem makes little difference to whether the problem can be solvedin polynomial time.

31 / 163

Page 70: 27 NP Completness

Some properties of the polynomial encoding

FirstWe say that a function f : 0, 1∗ → 0, 1∗ is polynomial timecomputable, if there exists a polynomial time algorithm A that, given anyinput x ∈ 0, 1∗, produces as output f (x).

SecondFor some set I of problem instances, we say that two encodings e1 and e2are polynomially related

if there exist two polynomial time computable functions f12 and f21such that for any i ∈ I , we have f12 (e1(i)) = e2(i) andf21 (e2(i)) = e1(i).

32 / 163

Page 71: 27 NP Completness

Some properties of the polynomial encoding

FirstWe say that a function f : 0, 1∗ → 0, 1∗ is polynomial timecomputable, if there exists a polynomial time algorithm A that, given anyinput x ∈ 0, 1∗, produces as output f (x).

SecondFor some set I of problem instances, we say that two encodings e1 and e2are polynomially related

if there exist two polynomial time computable functions f12 and f21such that for any i ∈ I , we have f12 (e1(i)) = e2(i) andf21 (e2(i)) = e1(i).

32 / 163

Page 72: 27 NP Completness

Some properties of the polynomial encoding

FirstWe say that a function f : 0, 1∗ → 0, 1∗ is polynomial timecomputable, if there exists a polynomial time algorithm A that, given anyinput x ∈ 0, 1∗, produces as output f (x).

SecondFor some set I of problem instances, we say that two encodings e1 and e2are polynomially related

if there exist two polynomial time computable functions f12 and f21such that for any i ∈ I , we have f12 (e1(i)) = e2(i) andf21 (e2(i)) = e1(i).

32 / 163

Page 73: 27 NP Completness

Some properties of the polynomial encoding

FirstWe say that a function f : 0, 1∗ → 0, 1∗ is polynomial timecomputable, if there exists a polynomial time algorithm A that, given anyinput x ∈ 0, 1∗, produces as output f (x).

SecondFor some set I of problem instances, we say that two encodings e1 and e2are polynomially related

if there exist two polynomial time computable functions f12 and f21such that for any i ∈ I , we have f12 (e1(i)) = e2(i) andf21 (e2(i)) = e1(i).

32 / 163

Page 74: 27 NP Completness

Observation

We have thatA polynomial-time algorithm can compute the encoding e2 (i) from theencoding e1 (i), and vice versa.

Something NotableIf two encodings e1 and e2 of an abstract problem are polynomially related

We have that if the problem is polynomial-time solvable or not isindependent of which encoding we use.

33 / 163

Page 75: 27 NP Completness

Observation

We have thatA polynomial-time algorithm can compute the encoding e2 (i) from theencoding e1 (i), and vice versa.

Something NotableIf two encodings e1 and e2 of an abstract problem are polynomially related

We have that if the problem is polynomial-time solvable or not isindependent of which encoding we use.

33 / 163

Page 76: 27 NP Completness

Observation

We have thatA polynomial-time algorithm can compute the encoding e2 (i) from theencoding e1 (i), and vice versa.

Something NotableIf two encodings e1 and e2 of an abstract problem are polynomially related

We have that if the problem is polynomial-time solvable or not isindependent of which encoding we use.

33 / 163

Page 77: 27 NP Completness

Observation

We have thatA polynomial-time algorithm can compute the encoding e2 (i) from theencoding e1 (i), and vice versa.

Something NotableIf two encodings e1 and e2 of an abstract problem are polynomially related

We have that if the problem is polynomial-time solvable or not isindependent of which encoding we use.

33 / 163

Page 78: 27 NP Completness

An important lemma

Lemma 34.1Let Q be an abstract decision problem on an instance set I , and let e1 ande2 be polynomially related encodings on I . Then, e1(Q) ∈ P if and only ife2(Q) ∈ P.

Proof in the board

34 / 163

Page 79: 27 NP Completness

An important lemma

Lemma 34.1Let Q be an abstract decision problem on an instance set I , and let e1 ande2 be polynomially related encodings on I . Then, e1(Q) ∈ P if and only ife2(Q) ∈ P.

Proof in the board

34 / 163

Page 80: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

35 / 163

Page 81: 27 NP Completness

Formal language framework to handle representation

Definitions1 An alphabet Σ is a finite set of symbols.2 A language L over Σ is any set of strings made up of symbols from

Σ∗.3 The empty language is ε.4 The language of all strings over Σ is denoted Σ∗.

36 / 163

Page 82: 27 NP Completness

Formal language framework to handle representation

Definitions1 An alphabet Σ is a finite set of symbols.2 A language L over Σ is any set of strings made up of symbols from

Σ∗.3 The empty language is ε.4 The language of all strings over Σ is denoted Σ∗.

36 / 163

Page 83: 27 NP Completness

Formal language framework to handle representation

Definitions1 An alphabet Σ is a finite set of symbols.2 A language L over Σ is any set of strings made up of symbols from

Σ∗.3 The empty language is ε.4 The language of all strings over Σ is denoted Σ∗.

36 / 163

Page 84: 27 NP Completness

Formal language framework to handle representation

Definitions1 An alphabet Σ is a finite set of symbols.2 A language L over Σ is any set of strings made up of symbols from

Σ∗.3 The empty language is ε.4 The language of all strings over Σ is denoted Σ∗.

36 / 163

Page 85: 27 NP Completness

Special languages and operations

Union, intersection and complementL1⋂L2 = x ∈ Σ∗| x ∈ L1∧x ∈ L2

L1⋃L2 = x ∈ Σ∗| x ∈ L1∨x ∈ L2

L = x ∈ Σ∗| x 6= L

ConcatenationL = x1x2 | x1 ∈ L1 and x2 ∈ L2

Kleene closureL∗ = ε

⋃L2⋃L3⋃ ...

37 / 163

Page 86: 27 NP Completness

Special languages and operations

Union, intersection and complementL1⋂L2 = x ∈ Σ∗| x ∈ L1∧x ∈ L2

L1⋃L2 = x ∈ Σ∗| x ∈ L1∨x ∈ L2

L = x ∈ Σ∗| x 6= L

ConcatenationL = x1x2 | x1 ∈ L1 and x2 ∈ L2

Kleene closureL∗ = ε

⋃L2⋃L3⋃ ...

37 / 163

Page 87: 27 NP Completness

Special languages and operations

Union, intersection and complementL1⋂L2 = x ∈ Σ∗| x ∈ L1∧x ∈ L2

L1⋃L2 = x ∈ Σ∗| x ∈ L1∨x ∈ L2

L = x ∈ Σ∗| x 6= L

ConcatenationL = x1x2 | x1 ∈ L1 and x2 ∈ L2

Kleene closureL∗ = ε

⋃L2⋃L3⋃ ...

37 / 163

Page 88: 27 NP Completness

Special languages and operations

Union, intersection and complementL1⋂L2 = x ∈ Σ∗| x ∈ L1∧x ∈ L2

L1⋃L2 = x ∈ Σ∗| x ∈ L1∨x ∈ L2

L = x ∈ Σ∗| x 6= L

ConcatenationL = x1x2 | x1 ∈ L1 and x2 ∈ L2

Kleene closureL∗ = ε

⋃L2⋃L3⋃ ...

37 / 163

Page 89: 27 NP Completness

Special languages and operations

Union, intersection and complementL1⋂L2 = x ∈ Σ∗| x ∈ L1∧x ∈ L2

L1⋃L2 = x ∈ Σ∗| x ∈ L1∨x ∈ L2

L = x ∈ Σ∗| x 6= L

ConcatenationL = x1x2 | x1 ∈ L1 and x2 ∈ L2

Kleene closureL∗ = ε

⋃L2⋃L3⋃ ...

37 / 163

Page 90: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

38 / 163

Page 91: 27 NP Completness

Observation

We have thatFrom the point of view of language theory,

The set of instances for any decision problem Q is simply the set∑∗

with∑

= 0, 1.

Something NotableQ is entirely characterized by instances that produce a YES or ONEanswer.

39 / 163

Page 92: 27 NP Completness

Observation

We have thatFrom the point of view of language theory,

The set of instances for any decision problem Q is simply the set∑∗

with∑

= 0, 1.

Something NotableQ is entirely characterized by instances that produce a YES or ONEanswer.

39 / 163

Page 93: 27 NP Completness

Observation

We have thatFrom the point of view of language theory,

The set of instances for any decision problem Q is simply the set∑∗

with∑

= 0, 1.

Something NotableQ is entirely characterized by instances that produce a YES or ONEanswer.

39 / 163

Page 94: 27 NP Completness

This allow us to define a language that is solvable by Q

We can write it down as the language

L = x ∈ Σ∗|Q(x) = 1 (2)

40 / 163

Page 95: 27 NP Completness

Thus, we can express the duality DecisionProblem-Algorithm

ImportantThe formal-language framework allows to express concisely the relationbetween decision problems and algorithms that solve them.

I

i

Decision Problems Set of Algorithms

41 / 163

Page 96: 27 NP Completness

Next

Given an instance x of a problemAn algorithm A accepts a string x ∈ 0, 1∗, if given x , thealgorithm’s output is A(x) = 1.

The language accepted by an algorithm A is the set of strings

L = x ∈ 0, 1∗ |A (x) = 1 . (3)

42 / 163

Page 97: 27 NP Completness

Next

Given an instance x of a problemAn algorithm A accepts a string x ∈ 0, 1∗, if given x , thealgorithm’s output is A(x) = 1.

The language accepted by an algorithm A is the set of strings

L = x ∈ 0, 1∗ |A (x) = 1 . (3)

42 / 163

Page 98: 27 NP Completness

Nevertheless

We have a problemEven if language L is accepted by an algorithm A.The algorithm will not necessarily reject a string x /∈ L provided as input toit.

I Example: The algorithm could loop forever.

43 / 163

Page 99: 27 NP Completness

Nevertheless

We have a problemEven if language L is accepted by an algorithm A.The algorithm will not necessarily reject a string x /∈ L provided as input toit.

I Example: The algorithm could loop forever.

43 / 163

Page 100: 27 NP Completness

Nevertheless

We have a problemEven if language L is accepted by an algorithm A.The algorithm will not necessarily reject a string x /∈ L provided as input toit.

I Example: The algorithm could loop forever.

43 / 163

Page 101: 27 NP Completness

Nevertheless

We need to be more stringentA language L is decided by an algorithm A if every binary string in L is acceptedby A and every binary string not in L is rejected by A.

L

UU-L

Algorithm A

0

1

44 / 163

Page 102: 27 NP Completness

Finally

Thus, a language L is decided by A, ifGiven a string x ∈ 0, 1∗, only one of two things can happen:

An algorithm A accepts, if given x ∈ L the algorithm outputsA(x) = 1.An algorithm A rejects, if if given x /∈ L the algorithm outputsA(x) = 0.

45 / 163

Page 103: 27 NP Completness

Finally

Thus, a language L is decided by A, ifGiven a string x ∈ 0, 1∗, only one of two things can happen:

An algorithm A accepts, if given x ∈ L the algorithm outputsA(x) = 1.An algorithm A rejects, if if given x /∈ L the algorithm outputsA(x) = 0.

45 / 163

Page 104: 27 NP Completness

Finally

Thus, a language L is decided by A, ifGiven a string x ∈ 0, 1∗, only one of two things can happen:

An algorithm A accepts, if given x ∈ L the algorithm outputsA(x) = 1.An algorithm A rejects, if if given x /∈ L the algorithm outputsA(x) = 0.

45 / 163

Page 105: 27 NP Completness

Now, it is possible to define acceptance in polynomial time

We have thatA language L is accepted in polynomial time by an algorithm A, if itis accepted by A in polynomial time:

I There exists a constant k such that for any n-length string x ∈ L ⇒algorithm A accepts x in time O

(nk).

ThusA language L is decided in polynomial time by an algorithm A, ifthere exists a constant k such that for any n-length string x ∈ 0, 1∗:

I The algorithm correctly decides whether x ∈ L in time O(nk).

46 / 163

Page 106: 27 NP Completness

Now, it is possible to define acceptance in polynomial time

We have thatA language L is accepted in polynomial time by an algorithm A, if itis accepted by A in polynomial time:

I There exists a constant k such that for any n-length string x ∈ L ⇒algorithm A accepts x in time O

(nk).

ThusA language L is decided in polynomial time by an algorithm A, ifthere exists a constant k such that for any n-length string x ∈ 0, 1∗:

I The algorithm correctly decides whether x ∈ L in time O(nk).

46 / 163

Page 107: 27 NP Completness

Now, it is possible to define acceptance in polynomial time

We have thatA language L is accepted in polynomial time by an algorithm A, if itis accepted by A in polynomial time:

I There exists a constant k such that for any n-length string x ∈ L ⇒algorithm A accepts x in time O

(nk).

ThusA language L is decided in polynomial time by an algorithm A, ifthere exists a constant k such that for any n-length string x ∈ 0, 1∗:

I The algorithm correctly decides whether x ∈ L in time O(nk).

46 / 163

Page 108: 27 NP Completness

Now, it is possible to define acceptance in polynomial time

We have thatA language L is accepted in polynomial time by an algorithm A, if itis accepted by A in polynomial time:

I There exists a constant k such that for any n-length string x ∈ L ⇒algorithm A accepts x in time O

(nk).

ThusA language L is decided in polynomial time by an algorithm A, ifthere exists a constant k such that for any n-length string x ∈ 0, 1∗:

I The algorithm correctly decides whether x ∈ L in time O(nk).

46 / 163

Page 109: 27 NP Completness

Example of polynomial accepted problems

Example of polynomial accepted problem

PATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

What does the polynomial times accepting algorithm do?One polynomial-time accepting algorithm does the following

I It verifies that G encodes an undirected graph.I It calculate the shortest path between vertices and compares the

number of edges of that path with k.I If it finds such a path outputs ONE and halt.I If it does not, it runs forever!!! ⇐= PROBLEM!!!

47 / 163

Page 110: 27 NP Completness

Example of polynomial accepted problems

Example of polynomial accepted problem

PATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

What does the polynomial times accepting algorithm do?One polynomial-time accepting algorithm does the following

I It verifies that G encodes an undirected graph.I It calculate the shortest path between vertices and compares the

number of edges of that path with k.I If it finds such a path outputs ONE and halt.I If it does not, it runs forever!!! ⇐= PROBLEM!!!

47 / 163

Page 111: 27 NP Completness

Example of polynomial accepted problems

Example of polynomial accepted problem

PATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

What does the polynomial times accepting algorithm do?One polynomial-time accepting algorithm does the following

I It verifies that G encodes an undirected graph.I It calculate the shortest path between vertices and compares the

number of edges of that path with k.I If it finds such a path outputs ONE and halt.I If it does not, it runs forever!!! ⇐= PROBLEM!!!

47 / 163

Page 112: 27 NP Completness

Example of polynomial accepted problems

Example of polynomial accepted problem

PATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

What does the polynomial times accepting algorithm do?One polynomial-time accepting algorithm does the following

I It verifies that G encodes an undirected graph.I It calculate the shortest path between vertices and compares the

number of edges of that path with k.I If it finds such a path outputs ONE and halt.I If it does not, it runs forever!!! ⇐= PROBLEM!!!

47 / 163

Page 113: 27 NP Completness

Example of polynomial accepted problems

Example of polynomial accepted problem

PATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

What does the polynomial times accepting algorithm do?One polynomial-time accepting algorithm does the following

I It verifies that G encodes an undirected graph.I It calculate the shortest path between vertices and compares the

number of edges of that path with k.I If it finds such a path outputs ONE and halt.I If it does not, it runs forever!!! ⇐= PROBLEM!!!

47 / 163

Page 114: 27 NP Completness

Example of polynomial accepted problems

Example of polynomial accepted problem

PATH = 〈G, u, v, k〉 |G = (V ,E) is an undirected graph,u, v ∈ V , k ≥ 0 is an integer and there exist a path fromu to v in G consisting of at most k edges

What does the polynomial times accepting algorithm do?One polynomial-time accepting algorithm does the following

I It verifies that G encodes an undirected graph.I It calculate the shortest path between vertices and compares the

number of edges of that path with k.I If it finds such a path outputs ONE and halt.I If it does not, it runs forever!!! ⇐= PROBLEM!!!

47 / 163

Page 115: 27 NP Completness

What we will like to have...

A decision algorithmBecause we want to avoid the infinite loop, we do the following...

StepsIt verifies that G encodes an undirected graph.It calculate the shortest path between vertices and compares thenumber of edges of that path with k.If it finds such a path outputs ONE and halt.If it does not find such a path output ZERO and halt.

48 / 163

Page 116: 27 NP Completness

What we will like to have...

A decision algorithmBecause we want to avoid the infinite loop, we do the following...

StepsIt verifies that G encodes an undirected graph.It calculate the shortest path between vertices and compares thenumber of edges of that path with k.If it finds such a path outputs ONE and halt.If it does not find such a path output ZERO and halt.

48 / 163

Page 117: 27 NP Completness

What we will like to have...

A decision algorithmBecause we want to avoid the infinite loop, we do the following...

StepsIt verifies that G encodes an undirected graph.It calculate the shortest path between vertices and compares thenumber of edges of that path with k.If it finds such a path outputs ONE and halt.If it does not find such a path output ZERO and halt.

48 / 163

Page 118: 27 NP Completness

What we will like to have...

A decision algorithmBecause we want to avoid the infinite loop, we do the following...

StepsIt verifies that G encodes an undirected graph.It calculate the shortest path between vertices and compares thenumber of edges of that path with k.If it finds such a path outputs ONE and halt.If it does not find such a path output ZERO and halt.

48 / 163

Page 119: 27 NP Completness

What we will like to have...

A decision algorithmBecause we want to avoid the infinite loop, we do the following...

StepsIt verifies that G encodes an undirected graph.It calculate the shortest path between vertices and compares thenumber of edges of that path with k.If it finds such a path outputs ONE and halt.If it does not find such a path output ZERO and halt.

48 / 163

Page 120: 27 NP Completness

HoweverThere are problemsAs the Turing’s Halting Problem where:

There exists an accepting algorithmBut no decision algorithm exist

What!?It turns out there are perfectly decent computational problems for whichno algorithms exist at all!

For example, an arithmetical version of what will talk later, the SATproblemGiven a polynomial equation in many variables, perhaps:

x3yz + 2y4z2 − 7xy5z = 6

are there integer values of x, y, z that satisfy it?49 / 163

Page 121: 27 NP Completness

HoweverThere are problemsAs the Turing’s Halting Problem where:

There exists an accepting algorithmBut no decision algorithm exist

What!?It turns out there are perfectly decent computational problems for whichno algorithms exist at all!

For example, an arithmetical version of what will talk later, the SATproblemGiven a polynomial equation in many variables, perhaps:

x3yz + 2y4z2 − 7xy5z = 6

are there integer values of x, y, z that satisfy it?49 / 163

Page 122: 27 NP Completness

HoweverThere are problemsAs the Turing’s Halting Problem where:

There exists an accepting algorithmBut no decision algorithm exist

What!?It turns out there are perfectly decent computational problems for whichno algorithms exist at all!

For example, an arithmetical version of what will talk later, the SATproblemGiven a polynomial equation in many variables, perhaps:

x3yz + 2y4z2 − 7xy5z = 6

are there integer values of x, y, z that satisfy it?49 / 163

Page 123: 27 NP Completness

HoweverThere are problemsAs the Turing’s Halting Problem where:

There exists an accepting algorithmBut no decision algorithm exist

What!?It turns out there are perfectly decent computational problems for whichno algorithms exist at all!

For example, an arithmetical version of what will talk later, the SATproblemGiven a polynomial equation in many variables, perhaps:

x3yz + 2y4z2 − 7xy5z = 6

are there integer values of x, y, z that satisfy it?49 / 163

Page 124: 27 NP Completness

HoweverThere are problemsAs the Turing’s Halting Problem where:

There exists an accepting algorithmBut no decision algorithm exist

What!?It turns out there are perfectly decent computational problems for whichno algorithms exist at all!

For example, an arithmetical version of what will talk later, the SATproblemGiven a polynomial equation in many variables, perhaps:

x3yz + 2y4z2 − 7xy5z = 6

are there integer values of x, y, z that satisfy it?49 / 163

Page 125: 27 NP Completness

Actually

Something NotableThere is no algorithm that solves this problem.No algorithm at all, polynomial, exponential, doubly exponential, or worse!

I Such problems are called unsolvable.

This was discovered byThe first unsolvable problem was discovered in 1936 by Alan M. Turing, then astudent of mathematics at Cambridge, England.

50 / 163

Page 126: 27 NP Completness

Actually

Something NotableThere is no algorithm that solves this problem.No algorithm at all, polynomial, exponential, doubly exponential, or worse!

I Such problems are called unsolvable.

This was discovered byThe first unsolvable problem was discovered in 1936 by Alan M. Turing, then astudent of mathematics at Cambridge, England.

50 / 163

Page 127: 27 NP Completness

Actually

Something NotableThere is no algorithm that solves this problem.No algorithm at all, polynomial, exponential, doubly exponential, or worse!

I Such problems are called unsolvable.

This was discovered byThe first unsolvable problem was discovered in 1936 by Alan M. Turing, then astudent of mathematics at Cambridge, England.

50 / 163

Page 128: 27 NP Completness

ActuallySomething Notable

There is no algorithm that solves this problem.No algorithm at all, polynomial, exponential, doubly exponential, or worse!

I Such problems are called unsolvable.

This was discovered byThe first unsolvable problem was discovered in 1936 by Alan M. Turing, then astudent of mathematics at Cambridge, England.

50 / 163

Page 129: 27 NP Completness

What did he do?

Basic Idea1 Suppose that given a program p and an input x.

1 There is an algorithm, called TERMINATE, that takes p and x and tellus if p will ever terminate in x.

51 / 163

Page 130: 27 NP Completness

What did he do?

Basic Idea1 Suppose that given a program p and an input x.

1 There is an algorithm, called TERMINATE, that takes p and x and tellus if p will ever terminate in x.

51 / 163

Page 131: 27 NP Completness

ThenWe have the following programfunction PARADOX(z : file)

1 if TERMINATES(z, z) goto 1

Notice what paradox doesIt terminates if and only if program z does not terminate when given itsown code as input.

What if run PARADOX(PARADOX)Funny PARDOX!!!

1 Case I : The PARADOX terminates -> Then TERMINATE saysfalse!!!

2 Case II : The PARADOX never terminates -> Then TERMINATEsays true!!!

52 / 163

Page 132: 27 NP Completness

ThenWe have the following programfunction PARADOX(z : file)

1 if TERMINATES(z, z) goto 1

Notice what paradox doesIt terminates if and only if program z does not terminate when given itsown code as input.

What if run PARADOX(PARADOX)Funny PARDOX!!!

1 Case I : The PARADOX terminates -> Then TERMINATE saysfalse!!!

2 Case II : The PARADOX never terminates -> Then TERMINATEsays true!!!

52 / 163

Page 133: 27 NP Completness

ThenWe have the following programfunction PARADOX(z : file)

1 if TERMINATES(z, z) goto 1

Notice what paradox doesIt terminates if and only if program z does not terminate when given itsown code as input.

What if run PARADOX(PARADOX)Funny PARDOX!!!

1 Case I : The PARADOX terminates -> Then TERMINATE saysfalse!!!

2 Case II : The PARADOX never terminates -> Then TERMINATEsays true!!!

52 / 163

Page 134: 27 NP Completness

ThenWe have the following programfunction PARADOX(z : file)

1 if TERMINATES(z, z) goto 1

Notice what paradox doesIt terminates if and only if program z does not terminate when given itsown code as input.

What if run PARADOX(PARADOX)Funny PARDOX!!!

1 Case I : The PARADOX terminates -> Then TERMINATE saysfalse!!!

2 Case II : The PARADOX never terminates -> Then TERMINATEsays true!!!

52 / 163

Page 135: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

53 / 163

Page 136: 27 NP Completness

Complexity Classes

ThenWe can informally define a complexity class as a set of languages.

NowThe membership to this class is determined by a complexity measure,such as running time, of an algorithm that determines whether a givenstring x belongs to language L.

HoweverThe actual definition of a complexity class is somewhat more technical.

54 / 163

Page 137: 27 NP Completness

Complexity Classes

ThenWe can informally define a complexity class as a set of languages.

NowThe membership to this class is determined by a complexity measure,such as running time, of an algorithm that determines whether a givenstring x belongs to language L.

HoweverThe actual definition of a complexity class is somewhat more technical.

54 / 163

Page 138: 27 NP Completness

Complexity Classes

ThenWe can informally define a complexity class as a set of languages.

NowThe membership to this class is determined by a complexity measure,such as running time, of an algorithm that determines whether a givenstring x belongs to language L.

HoweverThe actual definition of a complexity class is somewhat more technical.

54 / 163

Page 139: 27 NP Completness

Thus

We can use this framework to say the followingP = L ⊆ 0, 1∗ | There exists an algorithm A that decides L inpolynomial time

I In fact, P is also the class of languages that can be accepted inpolynomial time

Theorem 34.2P=L| L is accepted by a polynomial-time algorithm

55 / 163

Page 140: 27 NP Completness

Thus

We can use this framework to say the followingP = L ⊆ 0, 1∗ | There exists an algorithm A that decides L inpolynomial time

I In fact, P is also the class of languages that can be accepted inpolynomial time

Theorem 34.2P=L| L is accepted by a polynomial-time algorithm

55 / 163

Page 141: 27 NP Completness

Thus

We can use this framework to say the followingP = L ⊆ 0, 1∗ | There exists an algorithm A that decides L inpolynomial time

I In fact, P is also the class of languages that can be accepted inpolynomial time

Theorem 34.2P=L| L is accepted by a polynomial-time algorithm

55 / 163

Page 142: 27 NP Completness

Exercises

From Cormen’s book solve34.1-134.1-234.1-334.1-434.1-534.1-6

56 / 163

Page 143: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

57 / 163

Page 144: 27 NP Completness

What is verification?

Intuitive definitionGiven an instance of a decision problem:

For example 〈G, u, v, k〉 of PATH.

ThenWe are given :

A path p from A to F .Then, check if the length of p is at most k (i.e. Belongs toPATH), then it is called a “certificate.”

58 / 163

Page 145: 27 NP Completness

What is verification?

Intuitive definitionGiven an instance of a decision problem:

For example 〈G, u, v, k〉 of PATH.

ThenWe are given :

A path p from A to F .Then, check if the length of p is at most k (i.e. Belongs toPATH), then it is called a “certificate.”

58 / 163

Page 146: 27 NP Completness

What is verification?

Intuitive definitionGiven an instance of a decision problem:

For example 〈G, u, v, k〉 of PATH.

ThenWe are given :

A path p from A to F .Then, check if the length of p is at most k (i.e. Belongs toPATH), then it is called a “certificate.”

58 / 163

Page 147: 27 NP Completness

What is verification?

Intuitive definitionGiven an instance of a decision problem:

For example 〈G, u, v, k〉 of PATH.

ThenWe are given :

A path p from A to F .Then, check if the length of p is at most k (i.e. Belongs toPATH), then it is called a “certificate.”

58 / 163

Page 148: 27 NP Completness

It is more

In factWe would like to be able to verify in polynomial time the certificate ofcertain types of problems.For example:

I Polynomial time problems.I Non-Polynomial time problems.

59 / 163

Page 149: 27 NP Completness

It is more

In factWe would like to be able to verify in polynomial time the certificate ofcertain types of problems.For example:

I Polynomial time problems.I Non-Polynomial time problems.

59 / 163

Page 150: 27 NP Completness

It is more

In factWe would like to be able to verify in polynomial time the certificate ofcertain types of problems.For example:

I Polynomial time problems.I Non-Polynomial time problems.

59 / 163

Page 151: 27 NP Completness

It is more

In factWe would like to be able to verify in polynomial time the certificate ofcertain types of problems.For example:

I Polynomial time problems.I Non-Polynomial time problems.

59 / 163

Page 152: 27 NP Completness

Example of verifiable problemsHamiltonian cycleA Hamiltonian cycle of an undirected graph G = (V , E) is asimple cycle that contains each vertex in V .

Certificate

60 / 163

Page 153: 27 NP Completness

As a formal language

Does a graph G have a Hamiltonian cycle?

HAM − CYCLES = 〈G〉 |G is a Hamiltonian graph (4)

How do we solve this decision problem?Can we even solve it?

61 / 163

Page 154: 27 NP Completness

As a formal language

Does a graph G have a Hamiltonian cycle?

HAM − CYCLES = 〈G〉 |G is a Hamiltonian graph (4)

How do we solve this decision problem?Can we even solve it?

61 / 163

Page 155: 27 NP Completness

As a formal language

Does a graph G have a Hamiltonian cycle?

HAM − CYCLES = 〈G〉 |G is a Hamiltonian graph (4)

How do we solve this decision problem?Can we even solve it?

61 / 163

Page 156: 27 NP Completness

Decision algorithm for Hamiltonian

Given an instance < G > and encode itIf we use the “reasonable” encoding of a graph as its adjacencymatrix.

1 2 3 4 512345

0 0 0 1 00 0 0 1 10 0 0 0 11 1 0 0 10 1 1 1 0

62 / 163

Page 157: 27 NP Completness

Thus

We can then say the followingIf the number of vertices is m = Ω (

√n)

We have then√

n︷ ︸︸ ︷1 2 3 4 5

√n

12345

0 0 0 1 00 0 0 1 10 0 0 0 11 1 0 0 10 1 1 1 0

63 / 163

Page 158: 27 NP Completness

Thus

We can then say the followingIf the number of vertices is m = Ω (

√n)

We have then√

n︷ ︸︸ ︷1 2 3 4 5

√n

12345

0 0 0 1 00 0 0 1 10 0 0 0 11 1 0 0 10 1 1 1 0

63 / 163

Page 159: 27 NP Completness

Then

The encoding size is√

n ×√

n = n = |〈G〉|

64 / 163

Page 160: 27 NP Completness

Then, I decide to go NAIVE!!!

The algorithm does the followingIt lists the all permutations of the vertices of G and then checks eachpermutation to see if it is a Hamiltonian path.

65 / 163

Page 161: 27 NP Completness

Complexity

Performance analysis on the previous algorithmWe have then m = Ω(

√n)

Then, for our naive algorithm produce m! permutations.Then Ω(m!) = Ω(

√n!) = Ω(2

√n) EXPONENTIAL TIME!!!

Something NotableStill, with no-naive algorithm the Hamiltonian is not solvable in polynomialtime!

66 / 163

Page 162: 27 NP Completness

Complexity

Performance analysis on the previous algorithmWe have then m = Ω(

√n)

Then, for our naive algorithm produce m! permutations.Then Ω(m!) = Ω(

√n!) = Ω(2

√n) EXPONENTIAL TIME!!!

Something NotableStill, with no-naive algorithm the Hamiltonian is not solvable in polynomialtime!

66 / 163

Page 163: 27 NP Completness

Complexity

Performance analysis on the previous algorithmWe have then m = Ω(

√n)

Then, for our naive algorithm produce m! permutations.Then Ω(m!) = Ω(

√n!) = Ω(2

√n) EXPONENTIAL TIME!!!

Something NotableStill, with no-naive algorithm the Hamiltonian is not solvable in polynomialtime!

66 / 163

Page 164: 27 NP Completness

Complexity

Performance analysis on the previous algorithmWe have then m = Ω(

√n)

Then, for our naive algorithm produce m! permutations.Then Ω(m!) = Ω(

√n!) = Ω(2

√n) EXPONENTIAL TIME!!!

Something NotableStill, with no-naive algorithm the Hamiltonian is not solvable in polynomialtime!

66 / 163

Page 165: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

67 / 163

Page 166: 27 NP Completness

Verification Algorithms

A more formal definition in terms of formal languagesA verification algorithm is a two-argument algorithm A, where:

1 There is an input string x (Instance of the problem).2 There is a binary string y, certificate (The possible solution).

Then, a two-argument algorithm A verifiesA verifies x by using a certificate y.Then, it verifies x by taking y and outputting ONE i.e. A (x, y) = 1.

68 / 163

Page 167: 27 NP Completness

Verification Algorithms

A more formal definition in terms of formal languagesA verification algorithm is a two-argument algorithm A, where:

1 There is an input string x (Instance of the problem).2 There is a binary string y, certificate (The possible solution).

Then, a two-argument algorithm A verifiesA verifies x by using a certificate y.Then, it verifies x by taking y and outputting ONE i.e. A (x, y) = 1.

68 / 163

Page 168: 27 NP Completness

Verification Algorithms

A more formal definition in terms of formal languagesA verification algorithm is a two-argument algorithm A, where:

1 There is an input string x (Instance of the problem).2 There is a binary string y, certificate (The possible solution).

Then, a two-argument algorithm A verifiesA verifies x by using a certificate y.Then, it verifies x by taking y and outputting ONE i.e. A (x, y) = 1.

68 / 163

Page 169: 27 NP Completness

Verification Algorithms

A more formal definition in terms of formal languagesA verification algorithm is a two-argument algorithm A, where:

1 There is an input string x (Instance of the problem).2 There is a binary string y, certificate (The possible solution).

Then, a two-argument algorithm A verifiesA verifies x by using a certificate y.Then, it verifies x by taking y and outputting ONE i.e. A (x, y) = 1.

68 / 163

Page 170: 27 NP Completness

Verification Algorithms

A more formal definition in terms of formal languagesA verification algorithm is a two-argument algorithm A, where:

1 There is an input string x (Instance of the problem).2 There is a binary string y, certificate (The possible solution).

Then, a two-argument algorithm A verifiesA verifies x by using a certificate y.Then, it verifies x by taking y and outputting ONE i.e. A (x, y) = 1.

68 / 163

Page 171: 27 NP Completness

Finally we have

The language verified by a verification algorithm isL = x ∈ 0, 1∗|∃y ∈ 0, 1∗such that A(x, y) = 1

Important remark!For any string x /∈ L there must be no certificate proving x ∈ L(consistency is a must).

69 / 163

Page 172: 27 NP Completness

Finally we have

The language verified by a verification algorithm isL = x ∈ 0, 1∗|∃y ∈ 0, 1∗such that A(x, y) = 1

Important remark!For any string x /∈ L there must be no certificate proving x ∈ L(consistency is a must).

69 / 163

Page 173: 27 NP Completness

The NP class

DefinitionThe complexity class NP is the class of the languages that can beverified by a polynomial time algorithm.

L = x ∈ 0, 1∗|∃y ∈ 0, 1∗ with |y| = O(|x|c) such that A(x, y) = 1

NoteWe say that A verifies language L in polynomial time.Clearly, the size of the certificate must be polynomial in size!!!

70 / 163

Page 174: 27 NP Completness

The NP class

DefinitionThe complexity class NP is the class of the languages that can beverified by a polynomial time algorithm.

L = x ∈ 0, 1∗|∃y ∈ 0, 1∗ with |y| = O(|x|c) such that A(x, y) = 1

NoteWe say that A verifies language L in polynomial time.Clearly, the size of the certificate must be polynomial in size!!!

70 / 163

Page 175: 27 NP Completness

The NP class

DefinitionThe complexity class NP is the class of the languages that can beverified by a polynomial time algorithm.

L = x ∈ 0, 1∗|∃y ∈ 0, 1∗ with |y| = O(|x|c) such that A(x, y) = 1

NoteWe say that A verifies language L in polynomial time.Clearly, the size of the certificate must be polynomial in size!!!

70 / 163

Page 176: 27 NP Completness

Observation of the class NP and co-NP

ExampleHAM-CYCLE is NP, thus NP class is not empty.Observation: L ∈ P → L ∈ NP or P ⊆ NP.

Now, Do we have P = NP?There is evidence that P 6= NP basically because

I the existence of languages that are NP-Complete.

And actually, it is worseWe still cannot answer if L ∈ NP → L ∈ NP (closure undercomplement).

71 / 163

Page 177: 27 NP Completness

Observation of the class NP and co-NP

ExampleHAM-CYCLE is NP, thus NP class is not empty.Observation: L ∈ P → L ∈ NP or P ⊆ NP.

Now, Do we have P = NP?There is evidence that P 6= NP basically because

I the existence of languages that are NP-Complete.

And actually, it is worseWe still cannot answer if L ∈ NP → L ∈ NP (closure undercomplement).

71 / 163

Page 178: 27 NP Completness

Observation of the class NP and co-NP

ExampleHAM-CYCLE is NP, thus NP class is not empty.Observation: L ∈ P → L ∈ NP or P ⊆ NP.

Now, Do we have P = NP?There is evidence that P 6= NP basically because

I the existence of languages that are NP-Complete.

And actually, it is worseWe still cannot answer if L ∈ NP → L ∈ NP (closure undercomplement).

71 / 163

Page 179: 27 NP Completness

Observation of the class NP and co-NP

ExampleHAM-CYCLE is NP, thus NP class is not empty.Observation: L ∈ P → L ∈ NP or P ⊆ NP.

Now, Do we have P = NP?There is evidence that P 6= NP basically because

I the existence of languages that are NP-Complete.

And actually, it is worseWe still cannot answer if L ∈ NP → L ∈ NP (closure undercomplement).

71 / 163

Page 180: 27 NP Completness

Observation of the class NP and co-NP

ExampleHAM-CYCLE is NP, thus NP class is not empty.Observation: L ∈ P → L ∈ NP or P ⊆ NP.

Now, Do we have P = NP?There is evidence that P 6= NP basically because

I the existence of languages that are NP-Complete.

And actually, it is worseWe still cannot answer if L ∈ NP → L ∈ NP (closure undercomplement).

71 / 163

Page 181: 27 NP Completness

Another way to see this

The co − NP classThe class called co-NP is the set of languages L such that L ∈ NP

Something NotableWe can restate the question of whether NP is closed under complement aswhether NP = co −NP

In addition because P is closed under complementWe have P ⊆ NP ∩ co −NP, however no one knows whetherP = NP ∩ co −NP.

72 / 163

Page 182: 27 NP Completness

Another way to see this

The co − NP classThe class called co-NP is the set of languages L such that L ∈ NP

Something NotableWe can restate the question of whether NP is closed under complement aswhether NP = co −NP

In addition because P is closed under complementWe have P ⊆ NP ∩ co −NP, however no one knows whetherP = NP ∩ co −NP.

72 / 163

Page 183: 27 NP Completness

Another way to see this

The co − NP classThe class called co-NP is the set of languages L such that L ∈ NP

Something NotableWe can restate the question of whether NP is closed under complement aswhether NP = co −NP

In addition because P is closed under complementWe have P ⊆ NP ∩ co −NP, however no one knows whetherP = NP ∩ co −NP.

72 / 163

Page 184: 27 NP Completness

The four possibilities between the complexity classes

We have that

P=NP=co-NPNP=co-NP

P

Pco-NP NP co-NP NP

What we believe is the real relationship

73 / 163

Page 185: 27 NP Completness

Exercises

From Cormen’s book solve34.2-134.2-234.2-534.2-634.2-934.2-10

74 / 163

Page 186: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

75 / 163

Page 187: 27 NP Completness

Before entering reducibility

Why P 6= NP?Existence of NP-Complete problems.Problem!!! There is the following property:

I If any NP-Complete problem can be solved in polynomial time,then every problem in NP has a polynomial time solution.

Not only thatThe NP-Complete problems are the hardest in the NP class, and thisis related the concept of polynomial time reducibility.

76 / 163

Page 188: 27 NP Completness

Before entering reducibility

Why P 6= NP?Existence of NP-Complete problems.Problem!!! There is the following property:

I If any NP-Complete problem can be solved in polynomial time,then every problem in NP has a polynomial time solution.

Not only thatThe NP-Complete problems are the hardest in the NP class, and thisis related the concept of polynomial time reducibility.

76 / 163

Page 189: 27 NP Completness

Before entering reducibility

Why P 6= NP?Existence of NP-Complete problems.Problem!!! There is the following property:

I If any NP-Complete problem can be solved in polynomial time,then every problem in NP has a polynomial time solution.

Not only thatThe NP-Complete problems are the hardest in the NP class, and thisis related the concept of polynomial time reducibility.

76 / 163

Page 190: 27 NP Completness

Before entering reducibility

Why P 6= NP?Existence of NP-Complete problems.Problem!!! There is the following property:

I If any NP-Complete problem can be solved in polynomial time,then every problem in NP has a polynomial time solution.

Not only thatThe NP-Complete problems are the hardest in the NP class, and thisis related the concept of polynomial time reducibility.

76 / 163

Page 191: 27 NP Completness

Reducibility

Rough definitionA problem M can be reduced to M ′ if any instance of M can be easilyrephrased in terms of M ′.

Formal definitionA language L is polynomial time reducible to a language L′ writtenL ≤p L′ if there exist a polynomial time computable functionf : 0, 1∗ → 0, 1∗ such that for all x ∈ 0, 1∗

x ∈ L ⇐⇒ f (x) ∈ L′

77 / 163

Page 192: 27 NP Completness

Reducibility

Rough definitionA problem M can be reduced to M ′ if any instance of M can be easilyrephrased in terms of M ′.

Formal definitionA language L is polynomial time reducible to a language L′ writtenL ≤p L′ if there exist a polynomial time computable functionf : 0, 1∗ → 0, 1∗ such that for all x ∈ 0, 1∗

x ∈ L ⇐⇒ f (x) ∈ L′

77 / 163

Page 193: 27 NP Completness

Graphically

The Mapping

From the figureHere, f is called a reduction function, and the polynomial timealgorithm F that computes f is called reduction algorithm.

78 / 163

Page 194: 27 NP Completness

Graphically

The Mapping

From the figureHere, f is called a reduction function, and the polynomial timealgorithm F that computes f is called reduction algorithm.

78 / 163

Page 195: 27 NP Completness

Properties of f

Polynomial time reductionsPolynomial time reductions give us a powerful tool for proving that variouslanguages belong to P.

How?Lemma: If L1,L2 ⊆ 0, 1∗ are languages such that L1 ≤p L2, then

L2 ∈ P implies that L1 ∈ P.Proof

79 / 163

Page 196: 27 NP Completness

Properties of f

Polynomial time reductionsPolynomial time reductions give us a powerful tool for proving that variouslanguages belong to P.

How?Lemma: If L1,L2 ⊆ 0, 1∗ are languages such that L1 ≤p L2, then

L2 ∈ P implies that L1 ∈ P.Proof

79 / 163

Page 197: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

80 / 163

Page 198: 27 NP Completness

NP-Completeness

DefinitionA language L ⊆ 0, 1 ∗ is a NP-Complete problem (NPC) if:

1 L ∈ NP2 L′ ≤p L for every L′ ∈ NP

NoteIf a language L satisfies property 2, but not necessarily property 1, we saythat L is NP-Hard (NPH).

81 / 163

Page 199: 27 NP Completness

NP-Completeness

DefinitionA language L ⊆ 0, 1 ∗ is a NP-Complete problem (NPC) if:

1 L ∈ NP2 L′ ≤p L for every L′ ∈ NP

NoteIf a language L satisfies property 2, but not necessarily property 1, we saythat L is NP-Hard (NPH).

81 / 163

Page 200: 27 NP Completness

By The Way

NP can also be defined asThe set of decision problems that can be solved in polynomial time on anon-deterministic Turing machine.

Actually, it looks like a multi-threaded backtracking

82 / 163

Page 201: 27 NP Completness

By The WayNP can also be defined asThe set of decision problems that can be solved in polynomial time on anon-deterministic Turing machine.

Actually, it looks like a multi-threaded backtracking

Branching to all possibilitiesHeight

NDTM

For some

Branching to all possibilities Branching to all possibilities Branching to all possibilities

82 / 163

Page 202: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

83 / 163

Page 203: 27 NP Completness

Now, the infamous theorem

TheoremIf any NP-Complete problem is polynomial time solvable, thenP = NP. Equivalently, if any problem in NP is not polynomial timesolvable, then no NP-Complete problem is polynomial time solvable.

ProofSuppose that L ∈ P and also that L ∈ NPC . For any L′ ∈ NP, we haveL′ ≤p L by property 2 of the definition of NPC. Thus, by the previousLemma, we have that L’ ∈ P.

84 / 163

Page 204: 27 NP Completness

Now, the infamous theorem

TheoremIf any NP-Complete problem is polynomial time solvable, thenP = NP. Equivalently, if any problem in NP is not polynomial timesolvable, then no NP-Complete problem is polynomial time solvable.

ProofSuppose that L ∈ P and also that L ∈ NPC . For any L′ ∈ NP, we haveL′ ≤p L by property 2 of the definition of NPC. Thus, by the previousLemma, we have that L’ ∈ P.

84 / 163

Page 205: 27 NP Completness

However

Most Theoretical Computer Scientist have the following view

NPNPC

P

85 / 163

Page 206: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

86 / 163

Page 207: 27 NP Completness

Our first NPC - Circuit Satisfiability

We have basic boolean combinatorial elements.

87 / 163

Page 208: 27 NP Completness

Basic definition

DefinitionA boolean combinatorial circuit consist of one or more booleancombinatorial elements interconnected with wires.

88 / 163

Page 209: 27 NP Completness

Circuit satisfiability problem

ProblemGiven a boolean combinatorial circuit composed of AND, OR, and NOTgates, Is it satisfiable? Output is ONE!!!

FormallyCIRCUIT−SAT = 〈C 〉 |C is a satisfiable boolean combinatorial circuit

89 / 163

Page 210: 27 NP Completness

Circuit satisfiability problem

ProblemGiven a boolean combinatorial circuit composed of AND, OR, and NOTgates, Is it satisfiable? Output is ONE!!!

FormallyCIRCUIT−SAT = 〈C 〉 |C is a satisfiable boolean combinatorial circuit

89 / 163

Page 211: 27 NP Completness

Circuit satisfiability problem

Example: An assignment that outputs ONE

90 / 163

Page 212: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

91 / 163

Page 213: 27 NP Completness

First, It is NP-Problem

LemmaThe circuit-satisfiability belong to the class NP.

ProofWe need to give a polynomial-time algorithm A such that

1 One of the inputs to A is a boolean combinatorial circuit C .2 The other input is a certificate corresponding to an assignment of

boolean values to the wires in C .

92 / 163

Page 214: 27 NP Completness

First, It is NP-Problem

LemmaThe circuit-satisfiability belong to the class NP.

ProofWe need to give a polynomial-time algorithm A such that

1 One of the inputs to A is a boolean combinatorial circuit C .2 The other input is a certificate corresponding to an assignment of

boolean values to the wires in C .

92 / 163

Page 215: 27 NP Completness

First, It is NP-Problem

LemmaThe circuit-satisfiability belong to the class NP.

ProofWe need to give a polynomial-time algorithm A such that

1 One of the inputs to A is a boolean combinatorial circuit C .2 The other input is a certificate corresponding to an assignment of

boolean values to the wires in C .

92 / 163

Page 216: 27 NP Completness

First, It is NP-Problem

LemmaThe circuit-satisfiability belong to the class NP.

ProofWe need to give a polynomial-time algorithm A such that

1 One of the inputs to A is a boolean combinatorial circuit C .2 The other input is a certificate corresponding to an assignment of

boolean values to the wires in C .

92 / 163

Page 217: 27 NP Completness

Second, It is NP-Hard

The general idea for A is:For each circuit gate check that the output value is correctlycomputed and corresponds to the values provided by the certificate.

ThenThen if the output of the entire circuit is one, the algorithm Aoutputs 1, otherwise 0.Because the certificate is polynomial in size with respect to the circuitC =⇒ A runs in polynomial time.

I Actually, with a good implementation, linear time is enough.

FinallyA cannot be fooled by any certificate to believe that a unsatisfiablecircuit is accepted. Then CIRCUIT-SAT ∈ NP.

93 / 163

Page 218: 27 NP Completness

Second, It is NP-Hard

The general idea for A is:For each circuit gate check that the output value is correctlycomputed and corresponds to the values provided by the certificate.

ThenThen if the output of the entire circuit is one, the algorithm Aoutputs 1, otherwise 0.Because the certificate is polynomial in size with respect to the circuitC =⇒ A runs in polynomial time.

I Actually, with a good implementation, linear time is enough.

FinallyA cannot be fooled by any certificate to believe that a unsatisfiablecircuit is accepted. Then CIRCUIT-SAT ∈ NP.

93 / 163

Page 219: 27 NP Completness

Second, It is NP-Hard

The general idea for A is:For each circuit gate check that the output value is correctlycomputed and corresponds to the values provided by the certificate.

ThenThen if the output of the entire circuit is one, the algorithm Aoutputs 1, otherwise 0.Because the certificate is polynomial in size with respect to the circuitC =⇒ A runs in polynomial time.

I Actually, with a good implementation, linear time is enough.

FinallyA cannot be fooled by any certificate to believe that a unsatisfiablecircuit is accepted. Then CIRCUIT-SAT ∈ NP.

93 / 163

Page 220: 27 NP Completness

Second, It is NP-Hard

The general idea for A is:For each circuit gate check that the output value is correctlycomputed and corresponds to the values provided by the certificate.

ThenThen if the output of the entire circuit is one, the algorithm Aoutputs 1, otherwise 0.Because the certificate is polynomial in size with respect to the circuitC =⇒ A runs in polynomial time.

I Actually, with a good implementation, linear time is enough.

FinallyA cannot be fooled by any certificate to believe that a unsatisfiablecircuit is accepted. Then CIRCUIT-SAT ∈ NP.

93 / 163

Page 221: 27 NP Completness

Second, It is NP-Hard

The general idea for A is:For each circuit gate check that the output value is correctlycomputed and corresponds to the values provided by the certificate.

ThenThen if the output of the entire circuit is one, the algorithm Aoutputs 1, otherwise 0.Because the certificate is polynomial in size with respect to the circuitC =⇒ A runs in polynomial time.

I Actually, with a good implementation, linear time is enough.

FinallyA cannot be fooled by any certificate to believe that a unsatisfiablecircuit is accepted. Then CIRCUIT-SAT ∈ NP.

93 / 163

Page 222: 27 NP Completness

Proving CIRCUIT-SAT is NP-Hard

LemmaThe circuit sat problem is NP-hard.

Proof:Given a language L ∈ NP, we want a polynomial-time algorithm F thatcan compute a reduction map f such that:

It maps every binary string x to a circuit C = f (x) such that x ∈ L ifand only if C ∈CIRCUIT-SAT.

94 / 163

Page 223: 27 NP Completness

Proving CIRCUIT-SAT is NP-Hard

LemmaThe circuit sat problem is NP-hard.

Proof:Given a language L ∈ NP, we want a polynomial-time algorithm F thatcan compute a reduction map f such that:

It maps every binary string x to a circuit C = f (x) such that x ∈ L ifand only if C ∈CIRCUIT-SAT.

94 / 163

Page 224: 27 NP Completness

Proving CIRCUIT-SAT is NP-Hard

LemmaThe circuit sat problem is NP-hard.

Proof:Given a language L ∈ NP, we want a polynomial-time algorithm F thatcan compute a reduction map f such that:

It maps every binary string x to a circuit C = f (x) such that x ∈ L ifand only if C ∈CIRCUIT-SAT.

94 / 163

Page 225: 27 NP Completness

Now

FirstGiven a L ∈ NP, there exists an algorithm A that verifies L inpolynomial time.Now T (n) = O

(nk)denotes the worst case time of A, and the

length of the certificate is O(nk).

ThusThe algorithm F to be constructed will use the two input algorithm A tocompute the reduction function f .

95 / 163

Page 226: 27 NP Completness

Now

FirstGiven a L ∈ NP, there exists an algorithm A that verifies L inpolynomial time.Now T (n) = O

(nk)denotes the worst case time of A, and the

length of the certificate is O(nk).

ThusThe algorithm F to be constructed will use the two input algorithm A tocompute the reduction function f .

95 / 163

Page 227: 27 NP Completness

Now

FirstGiven a L ∈ NP, there exists an algorithm A that verifies L inpolynomial time.Now T (n) = O

(nk)denotes the worst case time of A, and the

length of the certificate is O(nk).

ThusThe algorithm F to be constructed will use the two input algorithm A tocompute the reduction function f .

95 / 163

Page 228: 27 NP Completness

Basic ideas: A Computer Program

A ProgramIt can be seen as a sequence of instructions!!!

Each instructionIt encodes an operation to be performed, addresses of operand in memory,and a final address to store the result.

Each program has a counter, PCThis counter keeps tracking of the instruction to be executed.It increments automatically upon fetching each instruction.It can be changed by an instruction, so it can be used to implementloops and branches.

96 / 163

Page 229: 27 NP Completness

Basic ideas: A Computer Program

A ProgramIt can be seen as a sequence of instructions!!!

Each instructionIt encodes an operation to be performed, addresses of operand in memory,and a final address to store the result.

Each program has a counter, PCThis counter keeps tracking of the instruction to be executed.It increments automatically upon fetching each instruction.It can be changed by an instruction, so it can be used to implementloops and branches.

96 / 163

Page 230: 27 NP Completness

Basic ideas: A Computer Program

A ProgramIt can be seen as a sequence of instructions!!!

Each instructionIt encodes an operation to be performed, addresses of operand in memory,and a final address to store the result.

Each program has a counter, PCThis counter keeps tracking of the instruction to be executed.It increments automatically upon fetching each instruction.It can be changed by an instruction, so it can be used to implementloops and branches.

96 / 163

Page 231: 27 NP Completness

Basic ideas: A Computer Program

A ProgramIt can be seen as a sequence of instructions!!!

Each instructionIt encodes an operation to be performed, addresses of operand in memory,and a final address to store the result.

Each program has a counter, PCThis counter keeps tracking of the instruction to be executed.It increments automatically upon fetching each instruction.It can be changed by an instruction, so it can be used to implementloops and branches.

96 / 163

Page 232: 27 NP Completness

Basic ideas: A Computer Program

A ProgramIt can be seen as a sequence of instructions!!!

Each instructionIt encodes an operation to be performed, addresses of operand in memory,and a final address to store the result.

Each program has a counter, PCThis counter keeps tracking of the instruction to be executed.It increments automatically upon fetching each instruction.It can be changed by an instruction, so it can be used to implementloops and branches.

96 / 163

Page 233: 27 NP Completness

Configuration

Something NotableAt any point during the execution of a program, the computer’s memoryholds the entire state of the computation.

ThusWe call any particular state of computer memory a configuration.

IMPORTANTWe can view the execution of an instruction as mapping one configurationto another.

97 / 163

Page 234: 27 NP Completness

Configuration

Something NotableAt any point during the execution of a program, the computer’s memoryholds the entire state of the computation.

ThusWe call any particular state of computer memory a configuration.

IMPORTANTWe can view the execution of an instruction as mapping one configurationto another.

97 / 163

Page 235: 27 NP Completness

Configuration

Something NotableAt any point during the execution of a program, the computer’s memoryholds the entire state of the computation.

ThusWe call any particular state of computer memory a configuration.

IMPORTANTWe can view the execution of an instruction as mapping one configurationto another.

97 / 163

Page 236: 27 NP Completness

Thus

We have thatThe computer hardware that accomplishes this mapping can beimplemented as a boolean combinational circuit.

ThenWe denote this boolean circuit as M .

98 / 163

Page 237: 27 NP Completness

Thus

We have thatThe computer hardware that accomplishes this mapping can beimplemented as a boolean combinational circuit.

ThenWe denote this boolean circuit as M .

98 / 163

Page 238: 27 NP Completness

What we wantLet L be any language in NPThere must exist an algorithm A that verifies L in polynomial time

ThusThe algorithm F that we shall construct uses the two-input algorithm A tocompute the reduction function f .

NowLet T (n) = O

(nk) denote the worst-case running time of algorithm A on a

n-length input for some k ≥ 1.Remember:

I The running time of A is actually a polynomial in the total input size,which includes both an input string and a certificate.

I The certificate is polynomial in the length n of the input.F Thus the running time is polynomial in n.

99 / 163

Page 239: 27 NP Completness

What we wantLet L be any language in NPThere must exist an algorithm A that verifies L in polynomial time

ThusThe algorithm F that we shall construct uses the two-input algorithm A tocompute the reduction function f .

NowLet T (n) = O

(nk) denote the worst-case running time of algorithm A on a

n-length input for some k ≥ 1.Remember:

I The running time of A is actually a polynomial in the total input size,which includes both an input string and a certificate.

I The certificate is polynomial in the length n of the input.F Thus the running time is polynomial in n.

99 / 163

Page 240: 27 NP Completness

What we wantLet L be any language in NPThere must exist an algorithm A that verifies L in polynomial time

ThusThe algorithm F that we shall construct uses the two-input algorithm A tocompute the reduction function f .

NowLet T (n) = O

(nk) denote the worst-case running time of algorithm A on a

n-length input for some k ≥ 1.Remember:

I The running time of A is actually a polynomial in the total input size,which includes both an input string and a certificate.

I The certificate is polynomial in the length n of the input.F Thus the running time is polynomial in n.

99 / 163

Page 241: 27 NP Completness

What we wantLet L be any language in NPThere must exist an algorithm A that verifies L in polynomial time

ThusThe algorithm F that we shall construct uses the two-input algorithm A tocompute the reduction function f .

NowLet T (n) = O

(nk) denote the worst-case running time of algorithm A on a

n-length input for some k ≥ 1.Remember:

I The running time of A is actually a polynomial in the total input size,which includes both an input string and a certificate.

I The certificate is polynomial in the length n of the input.F Thus the running time is polynomial in n.

99 / 163

Page 242: 27 NP Completness

What we wantLet L be any language in NPThere must exist an algorithm A that verifies L in polynomial time

ThusThe algorithm F that we shall construct uses the two-input algorithm A tocompute the reduction function f .

NowLet T (n) = O

(nk) denote the worst-case running time of algorithm A on a

n-length input for some k ≥ 1.Remember:

I The running time of A is actually a polynomial in the total input size,which includes both an input string and a certificate.

I The certificate is polynomial in the length n of the input.F Thus the running time is polynomial in n.

99 / 163

Page 243: 27 NP Completness

What we wantLet L be any language in NPThere must exist an algorithm A that verifies L in polynomial time

ThusThe algorithm F that we shall construct uses the two-input algorithm A tocompute the reduction function f .

NowLet T (n) = O

(nk) denote the worst-case running time of algorithm A on a

n-length input for some k ≥ 1.Remember:

I The running time of A is actually a polynomial in the total input size,which includes both an input string and a certificate.

I The certificate is polynomial in the length n of the input.F Thus the running time is polynomial in n.

99 / 163

Page 244: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

100 / 163

Page 245: 27 NP Completness

Basic ideas: Algorithm A representation

We can represent the computation of A as a sequence ofconfigurations.

Start with configuration c0, then finish with configuration cT(n).

101 / 163

Page 246: 27 NP Completness

ThenThe idea

The Combinatorial Circuit

PC

PC

PC

PC

Auxiliary MachineState

Auxiliary MachineState

Auxiliary MachineState

Auxiliary MachineState

WORKING STORAGE

WORKING STORAGE

WORKING STORAGE

WORKING STORAGE

0/1 OUTPUT102 / 163

Page 247: 27 NP Completness

Basic ideas: Algorithm A representation

Then, we need C = f (x)For this, we do:

I n = |x|

NextThen, we constructs a combinatorial circuit C ′ consisting of T (n) copiesof M

The output of the ci circuit finish as input in ci+1.

RemarkThe configuration finishes as values on the wires connecting copies.

103 / 163

Page 248: 27 NP Completness

Basic ideas: Algorithm A representation

Then, we need C = f (x)For this, we do:

I n = |x|

NextThen, we constructs a combinatorial circuit C ′ consisting of T (n) copiesof M

The output of the ci circuit finish as input in ci+1.

RemarkThe configuration finishes as values on the wires connecting copies.

103 / 163

Page 249: 27 NP Completness

Basic ideas: Algorithm A representation

Then, we need C = f (x)For this, we do:

I n = |x|

NextThen, we constructs a combinatorial circuit C ′ consisting of T (n) copiesof M

The output of the ci circuit finish as input in ci+1.

RemarkThe configuration finishes as values on the wires connecting copies.

103 / 163

Page 250: 27 NP Completness

Basic ideas: Algorithm A representation

Then, we need C = f (x)For this, we do:

I n = |x|

NextThen, we constructs a combinatorial circuit C ′ consisting of T (n) copiesof M

The output of the ci circuit finish as input in ci+1.

RemarkThe configuration finishes as values on the wires connecting copies.

103 / 163

Page 251: 27 NP Completness

The polynomial time algorithm

What F must do:1 Given x it needs to compute circuit C (x) = f (x).2 Satisfiable ⇐⇒ there exists a certificate y such that A (x, y) = 1.

104 / 163

Page 252: 27 NP Completness

The polynomial time algorithm

What F must do:1 Given x it needs to compute circuit C (x) = f (x).2 Satisfiable ⇐⇒ there exists a certificate y such that A (x, y) = 1.

104 / 163

Page 253: 27 NP Completness

The F process

Given x:It first computes n = |x|.

NextThen it computes C ′ (a combinatorial circuit) by using T (n) copiesof M .

ThenThen, the initial configuration of C ′ consists in the input A (x, y), theoutput is configuration CT(n)

105 / 163

Page 254: 27 NP Completness

The F process

Given x:It first computes n = |x|.

NextThen it computes C ′ (a combinatorial circuit) by using T (n) copiesof M .

ThenThen, the initial configuration of C ′ consists in the input A (x, y), theoutput is configuration CT(n)

105 / 163

Page 255: 27 NP Completness

The F process

Given x:It first computes n = |x|.

NextThen it computes C ′ (a combinatorial circuit) by using T (n) copiesof M .

ThenThen, the initial configuration of C ′ consists in the input A (x, y), theoutput is configuration CT(n)

105 / 163

Page 256: 27 NP Completness

Finally C

We then use C ′ to construct CFirst, F modifies circuit C ′ in the following way:

I It hardwires the inputs to C ′ corresponding to the programfor A:

F The initial program counterF The input xF The initial state of memory

106 / 163

Page 257: 27 NP Completness

Finally C

We then use C ′ to construct CFirst, F modifies circuit C ′ in the following way:

I It hardwires the inputs to C ′ corresponding to the programfor A:

F The initial program counterF The input xF The initial state of memory

106 / 163

Page 258: 27 NP Completness

Finally C

We then use C ′ to construct CFirst, F modifies circuit C ′ in the following way:

I It hardwires the inputs to C ′ corresponding to the programfor A:

F The initial program counterF The input xF The initial state of memory

106 / 163

Page 259: 27 NP Completness

Finally C

We then use C ′ to construct CFirst, F modifies circuit C ′ in the following way:

I It hardwires the inputs to C ′ corresponding to the programfor A:

F The initial program counterF The input xF The initial state of memory

106 / 163

Page 260: 27 NP Completness

Finally C

We then use C ′ to construct CFirst, F modifies circuit C ′ in the following way:

I It hardwires the inputs to C ′ corresponding to the programfor A:

F The initial program counterF The input xF The initial state of memory

106 / 163

Page 261: 27 NP Completness

Further

Something NotableThe only remaining inputs to the circuit correspond to the certificate y.

ThenAll outputs to the circuit are ignored, except the one bit of cT(n)corresponding to a computation on A(x, y).

Because the only free input is the certificate yAh!! We have that C (y) = A (x, y)!!!

107 / 163

Page 262: 27 NP Completness

Further

Something NotableThe only remaining inputs to the circuit correspond to the certificate y.

ThenAll outputs to the circuit are ignored, except the one bit of cT(n)corresponding to a computation on A(x, y).

Because the only free input is the certificate yAh!! We have that C (y) = A (x, y)!!!

107 / 163

Page 263: 27 NP Completness

Further

Something NotableThe only remaining inputs to the circuit correspond to the certificate y.

ThenAll outputs to the circuit are ignored, except the one bit of cT(n)corresponding to a computation on A(x, y).

Because the only free input is the certificate yAh!! We have that C (y) = A (x, y)!!!

107 / 163

Page 264: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

108 / 163

Page 265: 27 NP Completness

What we need to prove

FirstF correctly computes a reduction function f .

I C is satisfiable if and only if there is a certificate y such thatA(x, y) = 1.

SecondWe need to show that F runs in polynomial time.

109 / 163

Page 266: 27 NP Completness

What we need to prove

FirstF correctly computes a reduction function f .

I C is satisfiable if and only if there is a certificate y such thatA(x, y) = 1.

SecondWe need to show that F runs in polynomial time.

109 / 163

Page 267: 27 NP Completness

First, F correctly computes a reduction function f

We do the followingTo show that F correctly computes a reduction function, let us supposethat there exists a certificate y of length O(nk) such that A(x, y) = 1.

⇐=If we apply the bits of y to the inputs of C , the output of C isC (y) = A (x, y) = 1. Thus, if a certificate exists, then C issatisfiable.

=⇒Now, suppose that C is satisfiable. Hence, there exists an input y toC such that C (y) = 1, from which we conclude that A (x, y) = 1.

110 / 163

Page 268: 27 NP Completness

First, F correctly computes a reduction function f

We do the followingTo show that F correctly computes a reduction function, let us supposethat there exists a certificate y of length O(nk) such that A(x, y) = 1.

⇐=If we apply the bits of y to the inputs of C , the output of C isC (y) = A (x, y) = 1. Thus, if a certificate exists, then C issatisfiable.

=⇒Now, suppose that C is satisfiable. Hence, there exists an input y toC such that C (y) = 1, from which we conclude that A (x, y) = 1.

110 / 163

Page 269: 27 NP Completness

First, F correctly computes a reduction function f

We do the followingTo show that F correctly computes a reduction function, let us supposethat there exists a certificate y of length O(nk) such that A(x, y) = 1.

⇐=If we apply the bits of y to the inputs of C , the output of C isC (y) = A (x, y) = 1. Thus, if a certificate exists, then C issatisfiable.

=⇒Now, suppose that C is satisfiable. Hence, there exists an input y toC such that C (y) = 1, from which we conclude that A (x, y) = 1.

110 / 163

Page 270: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

111 / 163

Page 271: 27 NP Completness

Next, we need to show that F runs in polynomial time

With respect to the polynomial reductionThe length of the input x is n, and the certificate y is O(nk).

NextCircuit M implementing the computer hardware has polynomial size.

PropertiesThe circuit C consists of at most t = O

(nk)copies of M .

112 / 163

Page 272: 27 NP Completness

Next, we need to show that F runs in polynomial time

With respect to the polynomial reductionThe length of the input x is n, and the certificate y is O(nk).

NextCircuit M implementing the computer hardware has polynomial size.

PropertiesThe circuit C consists of at most t = O

(nk)copies of M .

112 / 163

Page 273: 27 NP Completness

Next, we need to show that F runs in polynomial time

With respect to the polynomial reductionThe length of the input x is n, and the certificate y is O(nk).

NextCircuit M implementing the computer hardware has polynomial size.

PropertiesThe circuit C consists of at most t = O

(nk)copies of M .

112 / 163

Page 274: 27 NP Completness

Finally!!!

In conclusionThe language CIRCUIT-SAT is therefore at least as hard as anylanguage in NP, and since it belongs to NP, it is NP-complete.

TheoremThe circuit satisfiability problem is NP-Complete.

113 / 163

Page 275: 27 NP Completness

Finally!!!

In conclusionThe language CIRCUIT-SAT is therefore at least as hard as anylanguage in NP, and since it belongs to NP, it is NP-complete.

TheoremThe circuit satisfiability problem is NP-Complete.

113 / 163

Page 276: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

114 / 163

Page 277: 27 NP Completness

Proving NP-Complete

Several theorems exist to make our life easierWe have the following

LemmaIf L is a Language such that L′ ≤P L for some L′ ∈ NPC , Then L isNP-Hard. Moreover, if L ∈ NP, then L ∈ NPC .

115 / 163

Page 278: 27 NP Completness

Proving NP-Complete

Several theorems exist to make our life easierWe have the following

LemmaIf L is a Language such that L′ ≤P L for some L′ ∈ NPC , Then L isNP-Hard. Moreover, if L ∈ NP, then L ∈ NPC .

115 / 163

Page 279: 27 NP Completness

So, we have the following strategy

Proceed as follows for proving that something is NP-Complete1 Prove L ∈ NP.2 Select a known NP-Complete language L′.3 Describe an algorithm that computes function f mapping every

instance x ∈ 0, 1∗ of L′ to an instance f (x) of L.4 Prove that the function f satisfies: x ∈ L′ if and only if f (x) ∈ L L

for all x ∈ 0, 1∗.5 Prove the polynomial time of the algorithm.

116 / 163

Page 280: 27 NP Completness

So, we have the following strategy

Proceed as follows for proving that something is NP-Complete1 Prove L ∈ NP.2 Select a known NP-Complete language L′.3 Describe an algorithm that computes function f mapping every

instance x ∈ 0, 1∗ of L′ to an instance f (x) of L.4 Prove that the function f satisfies: x ∈ L′ if and only if f (x) ∈ L L

for all x ∈ 0, 1∗.5 Prove the polynomial time of the algorithm.

116 / 163

Page 281: 27 NP Completness

So, we have the following strategy

Proceed as follows for proving that something is NP-Complete1 Prove L ∈ NP.2 Select a known NP-Complete language L′.3 Describe an algorithm that computes function f mapping every

instance x ∈ 0, 1∗ of L′ to an instance f (x) of L.4 Prove that the function f satisfies: x ∈ L′ if and only if f (x) ∈ L L

for all x ∈ 0, 1∗.5 Prove the polynomial time of the algorithm.

116 / 163

Page 282: 27 NP Completness

So, we have the following strategy

Proceed as follows for proving that something is NP-Complete1 Prove L ∈ NP.2 Select a known NP-Complete language L′.3 Describe an algorithm that computes function f mapping every

instance x ∈ 0, 1∗ of L′ to an instance f (x) of L.4 Prove that the function f satisfies: x ∈ L′ if and only if f (x) ∈ L L

for all x ∈ 0, 1∗.5 Prove the polynomial time of the algorithm.

116 / 163

Page 283: 27 NP Completness

So, we have the following strategy

Proceed as follows for proving that something is NP-Complete1 Prove L ∈ NP.2 Select a known NP-Complete language L′.3 Describe an algorithm that computes function f mapping every

instance x ∈ 0, 1∗ of L′ to an instance f (x) of L.4 Prove that the function f satisfies: x ∈ L′ if and only if f (x) ∈ L L

for all x ∈ 0, 1∗.5 Prove the polynomial time of the algorithm.

116 / 163

Page 284: 27 NP Completness

Exercises

From Cormen’s book solve34.3-134.3-234.3-534.3-634.3-734.3-8

117 / 163

Page 285: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

118 / 163

Page 286: 27 NP Completness

Formula Satisfiability (SAT)

An instance of SAT is a boolean formula φ composed of1 n boolean variables x1, x2, ..., xn .2 m boolean connectives (∧ ,∨, ¬, →, ⇐⇒ ).3 Parentheses.

A small exampleφ = ((x1 → x2) ∨ ¬ ((¬x1 ↔ x3) ∨ x4)) ∧ ¬x2

119 / 163

Page 287: 27 NP Completness

Formula Satisfiability (SAT)

An instance of SAT is a boolean formula φ composed of1 n boolean variables x1, x2, ..., xn .2 m boolean connectives (∧ ,∨, ¬, →, ⇐⇒ ).3 Parentheses.

A small exampleφ = ((x1 → x2) ∨ ¬ ((¬x1 ↔ x3) ∨ x4)) ∧ ¬x2

119 / 163

Page 288: 27 NP Completness

Formula Satisfiability (SAT)

An instance of SAT is a boolean formula φ composed of1 n boolean variables x1, x2, ..., xn .2 m boolean connectives (∧ ,∨, ¬, →, ⇐⇒ ).3 Parentheses.

A small exampleφ = ((x1 → x2) ∨ ¬ ((¬x1 ↔ x3) ∨ x4)) ∧ ¬x2

119 / 163

Page 289: 27 NP Completness

Formula Satisfiability (SAT)

An instance of SAT is a boolean formula φ composed of1 n boolean variables x1, x2, ..., xn .2 m boolean connectives (∧ ,∨, ¬, →, ⇐⇒ ).3 Parentheses.

A small exampleφ = ((x1 → x2) ∨ ¬ ((¬x1 ↔ x3) ∨ x4)) ∧ ¬x2

119 / 163

Page 290: 27 NP Completness

The satisfiability problem asks whether a given booleanformula is satisfiable

In formal-language terms

SAT = 〈φ〉 |φ is a satisfiable boolean formula

Example: Given 〈x1 = 0, x2 = 0, x3 = 1, x4 = 1〉

φ = ((0→ 0) ∨ ¬((¬0↔ 1) ∨ 1)) ∧ ¬0= (1 ∨ ¬ (1 ∨ 1)) ∧ 1= (1 ∨ 0) ∧ 1= 1

120 / 163

Page 291: 27 NP Completness

The satisfiability problem asks whether a given booleanformula is satisfiable

In formal-language terms

SAT = 〈φ〉 |φ is a satisfiable boolean formula

Example: Given 〈x1 = 0, x2 = 0, x3 = 1, x4 = 1〉

φ = ((0→ 0) ∨ ¬((¬0↔ 1) ∨ 1)) ∧ ¬0= (1 ∨ ¬ (1 ∨ 1)) ∧ 1= (1 ∨ 0) ∧ 1= 1

120 / 163

Page 292: 27 NP Completness

The satisfiability problem asks whether a given booleanformula is satisfiable

In formal-language terms

SAT = 〈φ〉 |φ is a satisfiable boolean formula

Example: Given 〈x1 = 0, x2 = 0, x3 = 1, x4 = 1〉

φ = ((0→ 0) ∨ ¬((¬0↔ 1) ∨ 1)) ∧ ¬0= (1 ∨ ¬ (1 ∨ 1)) ∧ 1= (1 ∨ 0) ∧ 1= 1

120 / 163

Page 293: 27 NP Completness

The satisfiability problem asks whether a given booleanformula is satisfiable

In formal-language terms

SAT = 〈φ〉 |φ is a satisfiable boolean formula

Example: Given 〈x1 = 0, x2 = 0, x3 = 1, x4 = 1〉

φ = ((0→ 0) ∨ ¬((¬0↔ 1) ∨ 1)) ∧ ¬0= (1 ∨ ¬ (1 ∨ 1)) ∧ 1= (1 ∨ 0) ∧ 1= 1

120 / 163

Page 294: 27 NP Completness

The satisfiability problem asks whether a given booleanformula is satisfiable

In formal-language terms

SAT = 〈φ〉 |φ is a satisfiable boolean formula

Example: Given 〈x1 = 0, x2 = 0, x3 = 1, x4 = 1〉

φ = ((0→ 0) ∨ ¬((¬0↔ 1) ∨ 1)) ∧ ¬0= (1 ∨ ¬ (1 ∨ 1)) ∧ 1= (1 ∨ 0) ∧ 1= 1

120 / 163

Page 295: 27 NP Completness

Formula Satisfiability

TheoremSatisfiability of boolean formulas is NP-Complete.

Proof1 The NP part is easy.2 Now, the mapping from a NPC.

121 / 163

Page 296: 27 NP Completness

Formula Satisfiability

TheoremSatisfiability of boolean formulas is NP-Complete.

Proof1 The NP part is easy.2 Now, the mapping from a NPC.

121 / 163

Page 297: 27 NP Completness

Formula Satisfiability

TheoremSatisfiability of boolean formulas is NP-Complete.

Proof1 The NP part is easy.2 Now, the mapping from a NPC.

121 / 163

Page 298: 27 NP Completness

Showing that SAT belongs to NP

CertificateIt consists of a satisfying assignment for an input formula φ.

Then A does the followingThe verifying algorithm simply replaces each variable in the formula withits responding value and then evaluates the expression.

PropertiesThis task is easy to do in polynomial time.If the expression evaluates to 1, then the algorithm has verified thatthe formula is satisfiable.

122 / 163

Page 299: 27 NP Completness

Showing that SAT belongs to NP

CertificateIt consists of a satisfying assignment for an input formula φ.

Then A does the followingThe verifying algorithm simply replaces each variable in the formula withits responding value and then evaluates the expression.

PropertiesThis task is easy to do in polynomial time.If the expression evaluates to 1, then the algorithm has verified thatthe formula is satisfiable.

122 / 163

Page 300: 27 NP Completness

Showing that SAT belongs to NP

CertificateIt consists of a satisfying assignment for an input formula φ.

Then A does the followingThe verifying algorithm simply replaces each variable in the formula withits responding value and then evaluates the expression.

PropertiesThis task is easy to do in polynomial time.If the expression evaluates to 1, then the algorithm has verified thatthe formula is satisfiable.

122 / 163

Page 301: 27 NP Completness

Now, we try the mapping from CIRCUIT-SAT to SAT

Naïve algorithmWe can use induction to express any boolean combinational circuit asa boolean formula.

ThenWe simply look at the gate that produces the circuit output andinductively express each of the gate’s inputs as formulas.

NaivelyWe then obtain the formula for the circuit by writing an expressionthat applies the gate’s function to its inputs’ formulas.

123 / 163

Page 302: 27 NP Completness

Now, we try the mapping from CIRCUIT-SAT to SAT

Naïve algorithmWe can use induction to express any boolean combinational circuit asa boolean formula.

ThenWe simply look at the gate that produces the circuit output andinductively express each of the gate’s inputs as formulas.

NaivelyWe then obtain the formula for the circuit by writing an expressionthat applies the gate’s function to its inputs’ formulas.

123 / 163

Page 303: 27 NP Completness

Now, we try the mapping from CIRCUIT-SAT to SAT

Naïve algorithmWe can use induction to express any boolean combinational circuit asa boolean formula.

ThenWe simply look at the gate that produces the circuit output andinductively express each of the gate’s inputs as formulas.

NaivelyWe then obtain the formula for the circuit by writing an expressionthat applies the gate’s function to its inputs’ formulas.

123 / 163

Page 304: 27 NP Completness

Problem

PROBLEMWhat happens if the circuit fan out? I.e. shared sub-formulas can makethe expression to grow exponentially!!!

1

3

N-1

N

2

Driving Gate

FAN-OUT=N

124 / 163

Page 305: 27 NP Completness

Instead, we use the following strategy

FirstFor each wire xi in the circuit C , the formula has a variable xi

Remember you need the last wire to be true!!!

ThenWe can now express how each gate operates as a small formula involvingthe variables of its incident wires.

Actually, we build a sequence of tautologiesx10 ←→ (x7 ∧ x8 ∧ x9)

We call each of these small formulas a clause.

125 / 163

Page 306: 27 NP Completness

Instead, we use the following strategy

FirstFor each wire xi in the circuit C , the formula has a variable xi

Remember you need the last wire to be true!!!

ThenWe can now express how each gate operates as a small formula involvingthe variables of its incident wires.

Actually, we build a sequence of tautologiesx10 ←→ (x7 ∧ x8 ∧ x9)

We call each of these small formulas a clause.

125 / 163

Page 307: 27 NP Completness

Instead, we use the following strategy

FirstFor each wire xi in the circuit C , the formula has a variable xi

Remember you need the last wire to be true!!!

ThenWe can now express how each gate operates as a small formula involvingthe variables of its incident wires.

Actually, we build a sequence of tautologiesx10 ←→ (x7 ∧ x8 ∧ x9)

We call each of these small formulas a clause.

125 / 163

Page 308: 27 NP Completness

Instead, we use the following strategy

FirstFor each wire xi in the circuit C , the formula has a variable xi

Remember you need the last wire to be true!!!

ThenWe can now express how each gate operates as a small formula involvingthe variables of its incident wires.

Actually, we build a sequence of tautologiesx10 ←→ (x7 ∧ x8 ∧ x9)

We call each of these small formulas a clause.

125 / 163

Page 309: 27 NP Completness

Use CIRCUIT-SAT

We a circuit C ∈CIRCUIT-SAT

126 / 163

Page 310: 27 NP Completness

Thus, we have the following clauses

The new boolean formula

φ = x10 ∧ (x4 ↔ ¬x3)∧ (x5 ↔ (x1 ∨ x2))∧ (x6 ↔ ¬x4)∧ (x7 ↔ (x1 ∧ x2 ∧ x4))∧ (x8 ↔ (x5 ∨ x6))∧ (x9 ↔ (x6 ∨ x7))∧ (x10 ↔ (x7 ∧ x8 ∧ x9))

127 / 163

Page 311: 27 NP Completness

Thus, we have the following clauses

The new boolean formula

φ = x10 ∧ (x4 ↔ ¬x3)∧ (x5 ↔ (x1 ∨ x2))∧ (x6 ↔ ¬x4)∧ (x7 ↔ (x1 ∧ x2 ∧ x4))∧ (x8 ↔ (x5 ∨ x6))∧ (x9 ↔ (x6 ∨ x7))∧ (x10 ↔ (x7 ∧ x8 ∧ x9))

127 / 163

Page 312: 27 NP Completness

Thus, we have the following clauses

The new boolean formula

φ = x10 ∧ (x4 ↔ ¬x3)∧ (x5 ↔ (x1 ∨ x2))∧ (x6 ↔ ¬x4)∧ (x7 ↔ (x1 ∧ x2 ∧ x4))∧ (x8 ↔ (x5 ∨ x6))∧ (x9 ↔ (x6 ∨ x7))∧ (x10 ↔ (x7 ∧ x8 ∧ x9))

127 / 163

Page 313: 27 NP Completness

Thus, we have the following clauses

The new boolean formula

φ = x10 ∧ (x4 ↔ ¬x3)∧ (x5 ↔ (x1 ∨ x2))∧ (x6 ↔ ¬x4)∧ (x7 ↔ (x1 ∧ x2 ∧ x4))∧ (x8 ↔ (x5 ∨ x6))∧ (x9 ↔ (x6 ∨ x7))∧ (x10 ↔ (x7 ∧ x8 ∧ x9))

127 / 163

Page 314: 27 NP Completness

Thus, we have the following clauses

The new boolean formula

φ = x10 ∧ (x4 ↔ ¬x3)∧ (x5 ↔ (x1 ∨ x2))∧ (x6 ↔ ¬x4)∧ (x7 ↔ (x1 ∧ x2 ∧ x4))∧ (x8 ↔ (x5 ∨ x6))∧ (x9 ↔ (x6 ∨ x7))∧ (x10 ↔ (x7 ∧ x8 ∧ x9))

127 / 163

Page 315: 27 NP Completness

Thus, we have the following clauses

The new boolean formula

φ = x10 ∧ (x4 ↔ ¬x3)∧ (x5 ↔ (x1 ∨ x2))∧ (x6 ↔ ¬x4)∧ (x7 ↔ (x1 ∧ x2 ∧ x4))∧ (x8 ↔ (x5 ∨ x6))∧ (x9 ↔ (x6 ∨ x7))∧ (x10 ↔ (x7 ∧ x8 ∧ x9))

127 / 163

Page 316: 27 NP Completness

Thus, we have the following clauses

The new boolean formula

φ = x10 ∧ (x4 ↔ ¬x3)∧ (x5 ↔ (x1 ∨ x2))∧ (x6 ↔ ¬x4)∧ (x7 ↔ (x1 ∧ x2 ∧ x4))∧ (x8 ↔ (x5 ∨ x6))∧ (x9 ↔ (x6 ∨ x7))∧ (x10 ↔ (x7 ∧ x8 ∧ x9))

127 / 163

Page 317: 27 NP Completness

Furthermore

Something NotableGiven that the circuit C is polynomial in size:

it is straightforward to produce such a formula φ in polynomial time.

128 / 163

Page 318: 27 NP Completness

What do we want to prove?

ThenWe want the following

=⇒If C has a satisfying assignment then φ is satisfiable.

⇐=If some assignment causes φ to evaluate to 1 then C is satisfiable.

129 / 163

Page 319: 27 NP Completness

What do we want to prove?

ThenWe want the following

=⇒If C has a satisfying assignment then φ is satisfiable.

⇐=If some assignment causes φ to evaluate to 1 then C is satisfiable.

129 / 163

Page 320: 27 NP Completness

What do we want to prove?

ThenWe want the following

=⇒If C has a satisfying assignment then φ is satisfiable.

⇐=If some assignment causes φ to evaluate to 1 then C is satisfiable.

129 / 163

Page 321: 27 NP Completness

Then

SatisfiableIf C has a satisfying assignment, then each wire of the circuit has awell-defined value, and the output of the circuit is 1.

MeaningTherefore, when we assign wire values to variables in φ, each clause of φevaluates to 1, and thus the conjunction of all evaluates to 1.

ConverselyConversely, if some assignment causes φ to evaluate to 1, the circuit C issatisfiable by an analogous argument.

130 / 163

Page 322: 27 NP Completness

Then

SatisfiableIf C has a satisfying assignment, then each wire of the circuit has awell-defined value, and the output of the circuit is 1.

MeaningTherefore, when we assign wire values to variables in φ, each clause of φevaluates to 1, and thus the conjunction of all evaluates to 1.

ConverselyConversely, if some assignment causes φ to evaluate to 1, the circuit C issatisfiable by an analogous argument.

130 / 163

Page 323: 27 NP Completness

Then

SatisfiableIf C has a satisfying assignment, then each wire of the circuit has awell-defined value, and the output of the circuit is 1.

MeaningTherefore, when we assign wire values to variables in φ, each clause of φevaluates to 1, and thus the conjunction of all evaluates to 1.

ConverselyConversely, if some assignment causes φ to evaluate to 1, the circuit C issatisfiable by an analogous argument.

130 / 163

Page 324: 27 NP Completness

Then

We have proved thatCIRCUIT − SAT ≤p SAT

131 / 163

Page 325: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

132 / 163

Page 326: 27 NP Completness

However!

However!Problem: SAT is still too complex.Solution: Use 3-CNF

133 / 163

Page 327: 27 NP Completness

However!

However!Problem: SAT is still too complex.Solution: Use 3-CNF

133 / 163

Page 328: 27 NP Completness

Definition

FirstA literal in a boolean formula is an occurrence of a variable or itsnegation.

SecondA boolean formula is in conjunctive normal form, or CNF, if it isexpressed as an AND of clauses, each of which is the OR of one ormore literals.

ThirdA boolean formula is in 3-Conjunctive normal form, or 3-CNF, if eachclause has exactly three distinct literals.

(x1 ∨ ¬ ∨ ¬x2) ∧ (x3 ∨ x2 ∨ x4) ∧ (¬x1 ∨ ¬x3 ∨ ¬x4)

134 / 163

Page 329: 27 NP Completness

Definition

FirstA literal in a boolean formula is an occurrence of a variable or itsnegation.

SecondA boolean formula is in conjunctive normal form, or CNF, if it isexpressed as an AND of clauses, each of which is the OR of one ormore literals.

ThirdA boolean formula is in 3-Conjunctive normal form, or 3-CNF, if eachclause has exactly three distinct literals.

(x1 ∨ ¬ ∨ ¬x2) ∧ (x3 ∨ x2 ∨ x4) ∧ (¬x1 ∨ ¬x3 ∨ ¬x4)

134 / 163

Page 330: 27 NP Completness

Definition

FirstA literal in a boolean formula is an occurrence of a variable or itsnegation.

SecondA boolean formula is in conjunctive normal form, or CNF, if it isexpressed as an AND of clauses, each of which is the OR of one ormore literals.

ThirdA boolean formula is in 3-Conjunctive normal form, or 3-CNF, if eachclause has exactly three distinct literals.

(x1 ∨ ¬ ∨ ¬x2) ∧ (x3 ∨ x2 ∨ x4) ∧ (¬x1 ∨ ¬x3 ∨ ¬x4)

134 / 163

Page 331: 27 NP Completness

3-CNF is NP-Complete

TheoremSatisfiability of boolean formulas in 3-Conjunctive normal form isNP-Complete.

ProofThe NP part is similar to the previous theorem.The interesting part is proving that SAT≤p 3-CNF

135 / 163

Page 332: 27 NP Completness

3-CNF is NP-Complete

TheoremSatisfiability of boolean formulas in 3-Conjunctive normal form isNP-Complete.

ProofThe NP part is similar to the previous theorem.The interesting part is proving that SAT≤p 3-CNF

135 / 163

Page 333: 27 NP Completness

3-CNF is NP-Complete

TheoremSatisfiability of boolean formulas in 3-Conjunctive normal form isNP-Complete.

ProofThe NP part is similar to the previous theorem.The interesting part is proving that SAT≤p 3-CNF

135 / 163

Page 334: 27 NP Completness

Proof NP-Complete of 3-CNF

Parse the formulaExample: φ = ((x1 → x2) ∨ ¬ ((¬x1 ↔ x3) ∨ x4)) ∧ ¬x2

We can use ideas from parsing to create a syntax tree

136 / 163

Page 335: 27 NP Completness

Proof NP-Complete of 3-CNF

Parse the formulaExample: φ = ((x1 → x2) ∨ ¬ ((¬x1 ↔ x3) ∨ x4)) ∧ ¬x2

We can use ideas from parsing to create a syntax tree

136 / 163

Page 336: 27 NP Completness

Parsing allows us to parse the formula into φ′

This can be done by naming the nodes in the tree

φ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2))∧ (y2 ↔ (y3 ∨ y4))∧ (y3 ↔ (x1 → x2))∧ (y4 ↔ ¬y5)∧ (y5 ↔ (y6 ∨ x4))∧ (y6 ↔ (¬x1 ↔ x3))

ProblemWe still not have the disjunctive parts... What can we do?

137 / 163

Page 337: 27 NP Completness

Parsing allows us to parse the formula into φ′

This can be done by naming the nodes in the tree

φ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2))∧ (y2 ↔ (y3 ∨ y4))∧ (y3 ↔ (x1 → x2))∧ (y4 ↔ ¬y5)∧ (y5 ↔ (y6 ∨ x4))∧ (y6 ↔ (¬x1 ↔ x3))

ProblemWe still not have the disjunctive parts... What can we do?

137 / 163

Page 338: 27 NP Completness

Parsing allows us to parse the formula into φ′

This can be done by naming the nodes in the tree

φ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2))∧ (y2 ↔ (y3 ∨ y4))∧ (y3 ↔ (x1 → x2))∧ (y4 ↔ ¬y5)∧ (y5 ↔ (y6 ∨ x4))∧ (y6 ↔ (¬x1 ↔ x3))

ProblemWe still not have the disjunctive parts... What can we do?

137 / 163

Page 339: 27 NP Completness

Parsing allows us to parse the formula into φ′

This can be done by naming the nodes in the tree

φ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2))∧ (y2 ↔ (y3 ∨ y4))∧ (y3 ↔ (x1 → x2))∧ (y4 ↔ ¬y5)∧ (y5 ↔ (y6 ∨ x4))∧ (y6 ↔ (¬x1 ↔ x3))

ProblemWe still not have the disjunctive parts... What can we do?

137 / 163

Page 340: 27 NP Completness

Parsing allows us to parse the formula into φ′

This can be done by naming the nodes in the tree

φ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2))∧ (y2 ↔ (y3 ∨ y4))∧ (y3 ↔ (x1 → x2))∧ (y4 ↔ ¬y5)∧ (y5 ↔ (y6 ∨ x4))∧ (y6 ↔ (¬x1 ↔ x3))

ProblemWe still not have the disjunctive parts... What can we do?

137 / 163

Page 341: 27 NP Completness

Parsing allows us to parse the formula into φ′

This can be done by naming the nodes in the tree

φ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2))∧ (y2 ↔ (y3 ∨ y4))∧ (y3 ↔ (x1 → x2))∧ (y4 ↔ ¬y5)∧ (y5 ↔ (y6 ∨ x4))∧ (y6 ↔ (¬x1 ↔ x3))

ProblemWe still not have the disjunctive parts... What can we do?

137 / 163

Page 342: 27 NP Completness

Parsing allows us to parse the formula into φ′

This can be done by naming the nodes in the tree

φ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2))∧ (y2 ↔ (y3 ∨ y4))∧ (y3 ↔ (x1 → x2))∧ (y4 ↔ ¬y5)∧ (y5 ↔ (y6 ∨ x4))∧ (y6 ↔ (¬x1 ↔ x3))

ProblemWe still not have the disjunctive parts... What can we do?

137 / 163

Page 343: 27 NP Completness

Proof

We can do the followingWe can build the truth table of each clause φ′i !

For example, the truth table of φ′1 = y1 ↔ (y2 ∧ ¬x2)y1 y2 x3

1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0

y1 ↔ (y2 ∧ ¬x2)01001011

138 / 163

Page 344: 27 NP Completness

Proof

We can do the followingWe can build the truth table of each clause φ′i !

For example, the truth table of φ′1 = y1 ↔ (y2 ∧ ¬x2)y1 y2 x3

1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0

y1 ↔ (y2 ∧ ¬x2)01001011

138 / 163

Page 345: 27 NP Completness

From this, we have

Disjunctive normal form (or DNF)In each of the zeros we put a conjunction that evaluate to ONE

y1 y2 x3

1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0

y1 ↔ (y2 ∧ ¬x2)0 y1 ∧ y2 ∧ x31 · · ·0 y1 ∧ ¬y2 ∧ x30 y1 ∧ ¬y2 ∧ ¬x31 · · ·0 ¬y1 ∧ y2 ∧ ¬x31 · · ·1 · · ·

139 / 163

Page 346: 27 NP Completness

Then, we use disjunctions to put all them togetherWe have then an OR of AND’s

I = (y1 ∧ y2 ∧ x3) ∨ (y1 ∧ ¬y2 ∧ x3) ∨ (y1 ∧ ¬y2 ∧ ¬x3) ∨ (¬y1 ∧ y2 ∧ ¬x3)

Thus, we have that ¬I ≡ φ′1

y1 y2 x3

1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0

y1 ↔ (y2 ∧ ¬x2) I ¬I0 1 01 0 10 1 00 1 01 0 10 1 01 0 11 0 1

140 / 163

Page 347: 27 NP Completness

Then, we use disjunctions to put all them togetherWe have then an OR of AND’s

I = (y1 ∧ y2 ∧ x3) ∨ (y1 ∧ ¬y2 ∧ x3) ∨ (y1 ∧ ¬y2 ∧ ¬x3) ∨ (¬y1 ∧ y2 ∧ ¬x3)

Thus, we have that ¬I ≡ φ′1

y1 y2 x3

1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0

y1 ↔ (y2 ∧ ¬x2) I ¬I0 1 01 0 10 1 00 1 01 0 10 1 01 0 11 0 1

140 / 163

Page 348: 27 NP Completness

Using DeMorgan’s laws

We obtainφ′′1 = (¬y1∨¬y2∨¬x2)∧ (¬y1∨y2∨¬x2)∧ (¬y1∨y2∨x2)∧ (y1∨¬y2∨x2)

141 / 163

Page 349: 27 NP Completness

Now, we need to include more literals as necessary

Given Ci as a disjunctive part of the previous formula.If Ci has 3 distinct literals, then simply include Ci as a clause of φ.

If Ci has 2 distinct literalsif Ci = (Ii ∨ I2), where I1 and I2 are literals, then include

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p)

as clauses of φ.Why?

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p) = (I1 ∨ I2) ∨ (p ∧ ¬p) =(I1 ∨ I2) ∨ (F) = I1 ∨ I2

142 / 163

Page 350: 27 NP Completness

Now, we need to include more literals as necessary

Given Ci as a disjunctive part of the previous formula.If Ci has 3 distinct literals, then simply include Ci as a clause of φ.

If Ci has 2 distinct literalsif Ci = (Ii ∨ I2), where I1 and I2 are literals, then include

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p)

as clauses of φ.Why?

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p) = (I1 ∨ I2) ∨ (p ∧ ¬p) =(I1 ∨ I2) ∨ (F) = I1 ∨ I2

142 / 163

Page 351: 27 NP Completness

Now, we need to include more literals as necessary

Given Ci as a disjunctive part of the previous formula.If Ci has 3 distinct literals, then simply include Ci as a clause of φ.

If Ci has 2 distinct literalsif Ci = (Ii ∨ I2), where I1 and I2 are literals, then include

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p)

as clauses of φ.Why?

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p) = (I1 ∨ I2) ∨ (p ∧ ¬p) =(I1 ∨ I2) ∨ (F) = I1 ∨ I2

142 / 163

Page 352: 27 NP Completness

Now, we need to include more literals as necessary

Given Ci as a disjunctive part of the previous formula.If Ci has 3 distinct literals, then simply include Ci as a clause of φ.

If Ci has 2 distinct literalsif Ci = (Ii ∨ I2), where I1 and I2 are literals, then include

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p)

as clauses of φ.Why?

(I1 ∨ I2 ∨ p) ∧ (I1 ∨ I2 ∨ ¬p) = (I1 ∨ I2) ∨ (p ∧ ¬p) =(I1 ∨ I2) ∨ (F) = I1 ∨ I2

142 / 163

Page 353: 27 NP Completness

Now, we need to include more literals as necessary

If Ci has just 1 distinct literal IThen include (I ∨ p ∨ q)∧ (I ∨ p ∨¬q)∧ (I ∨¬p ∨ q)∧ (I ∨¬p ∨¬q)as clauses of φ.Why?

(I ∨ p ∨ q) ∧ (I ∨ p ∨ ¬q)∧...(I ∨ ¬p ∨ q) ∧ (I ∨ ¬p ∨ ¬q) = I ∨ [(p ∨ q) ∧ (p ∨ ¬q) ∧ . . .

(¬p ∨ q) ∧ (¬p ∨ ¬q)]= I ∨ [p ∨ (q ∧ ¬q) ∧ . . .(¬p ∨ (q ∧ ¬q))]

= I ∨ [(p ∨ F) ∧ (¬p ∨ F)]= I ∨ [p ∧ ¬p]= I ∨ F = I

143 / 163

Page 354: 27 NP Completness

Now, we need to include more literals as necessary

If Ci has just 1 distinct literal IThen include (I ∨ p ∨ q)∧ (I ∨ p ∨¬q)∧ (I ∨¬p ∨ q)∧ (I ∨¬p ∨¬q)as clauses of φ.Why?

(I ∨ p ∨ q) ∧ (I ∨ p ∨ ¬q)∧...(I ∨ ¬p ∨ q) ∧ (I ∨ ¬p ∨ ¬q) = I ∨ [(p ∨ q) ∧ (p ∨ ¬q) ∧ . . .

(¬p ∨ q) ∧ (¬p ∨ ¬q)]= I ∨ [p ∨ (q ∧ ¬q) ∧ . . .(¬p ∨ (q ∧ ¬q))]

= I ∨ [(p ∨ F) ∧ (¬p ∨ F)]= I ∨ [p ∧ ¬p]= I ∨ F = I

143 / 163

Page 355: 27 NP Completness

Now, we need to include more literals as necessary

If Ci has just 1 distinct literal IThen include (I ∨ p ∨ q)∧ (I ∨ p ∨¬q)∧ (I ∨¬p ∨ q)∧ (I ∨¬p ∨¬q)as clauses of φ.Why?

(I ∨ p ∨ q) ∧ (I ∨ p ∨ ¬q)∧...(I ∨ ¬p ∨ q) ∧ (I ∨ ¬p ∨ ¬q) = I ∨ [(p ∨ q) ∧ (p ∨ ¬q) ∧ . . .

(¬p ∨ q) ∧ (¬p ∨ ¬q)]= I ∨ [p ∨ (q ∧ ¬q) ∧ . . .(¬p ∨ (q ∧ ¬q))]

= I ∨ [(p ∨ F) ∧ (¬p ∨ F)]= I ∨ [p ∧ ¬p]= I ∨ F = I

143 / 163

Page 356: 27 NP Completness

Now, we need to include more literals as necessary

If Ci has just 1 distinct literal IThen include (I ∨ p ∨ q)∧ (I ∨ p ∨¬q)∧ (I ∨¬p ∨ q)∧ (I ∨¬p ∨¬q)as clauses of φ.Why?

(I ∨ p ∨ q) ∧ (I ∨ p ∨ ¬q)∧...(I ∨ ¬p ∨ q) ∧ (I ∨ ¬p ∨ ¬q) = I ∨ [(p ∨ q) ∧ (p ∨ ¬q) ∧ . . .

(¬p ∨ q) ∧ (¬p ∨ ¬q)]= I ∨ [p ∨ (q ∧ ¬q) ∧ . . .(¬p ∨ (q ∧ ¬q))]

= I ∨ [(p ∨ F) ∧ (¬p ∨ F)]= I ∨ [p ∧ ¬p]= I ∨ F = I

143 / 163

Page 357: 27 NP Completness

Now, we need to include more literals as necessary

If Ci has just 1 distinct literal IThen include (I ∨ p ∨ q)∧ (I ∨ p ∨¬q)∧ (I ∨¬p ∨ q)∧ (I ∨¬p ∨¬q)as clauses of φ.Why?

(I ∨ p ∨ q) ∧ (I ∨ p ∨ ¬q)∧...(I ∨ ¬p ∨ q) ∧ (I ∨ ¬p ∨ ¬q) = I ∨ [(p ∨ q) ∧ (p ∨ ¬q) ∧ . . .

(¬p ∨ q) ∧ (¬p ∨ ¬q)]= I ∨ [p ∨ (q ∧ ¬q) ∧ . . .(¬p ∨ (q ∧ ¬q))]

= I ∨ [(p ∨ F) ∧ (¬p ∨ F)]= I ∨ [p ∧ ¬p]= I ∨ F = I

143 / 163

Page 358: 27 NP Completness

Now, we need to include more literals as necessary

If Ci has just 1 distinct literal IThen include (I ∨ p ∨ q)∧ (I ∨ p ∨¬q)∧ (I ∨¬p ∨ q)∧ (I ∨¬p ∨¬q)as clauses of φ.Why?

(I ∨ p ∨ q) ∧ (I ∨ p ∨ ¬q)∧...(I ∨ ¬p ∨ q) ∧ (I ∨ ¬p ∨ ¬q) = I ∨ [(p ∨ q) ∧ (p ∨ ¬q) ∧ . . .

(¬p ∨ q) ∧ (¬p ∨ ¬q)]= I ∨ [p ∨ (q ∧ ¬q) ∧ . . .(¬p ∨ (q ∧ ¬q))]

= I ∨ [(p ∨ F) ∧ (¬p ∨ F)]= I ∨ [p ∧ ¬p]= I ∨ F = I

143 / 163

Page 359: 27 NP Completness

Finally, we need to prove the polynomial reduction

FirstConstructing φ′ from φ introduces at most 1 variable and 1 clause perconnective in φ.

SecondConstructing φ′′ from φ′ can introduce at most 8 clauses into φ′′ foreach clause from φ′, since each clause of φ′′ has at most 3 variables,and the truth table for each clause has at most 23 = 8 rows.

ThirdThe construction of φ′′′ from φ′ introduces at most 4 clauses into φ′′′for each clause of φ′′.

144 / 163

Page 360: 27 NP Completness

Finally, we need to prove the polynomial reduction

FirstConstructing φ′ from φ introduces at most 1 variable and 1 clause perconnective in φ.

SecondConstructing φ′′ from φ′ can introduce at most 8 clauses into φ′′ foreach clause from φ′, since each clause of φ′′ has at most 3 variables,and the truth table for each clause has at most 23 = 8 rows.

ThirdThe construction of φ′′′ from φ′ introduces at most 4 clauses into φ′′′for each clause of φ′′.

144 / 163

Page 361: 27 NP Completness

Finally, we need to prove the polynomial reduction

FirstConstructing φ′ from φ introduces at most 1 variable and 1 clause perconnective in φ.

SecondConstructing φ′′ from φ′ can introduce at most 8 clauses into φ′′ foreach clause from φ′, since each clause of φ′′ has at most 3 variables,and the truth table for each clause has at most 23 = 8 rows.

ThirdThe construction of φ′′′ from φ′ introduces at most 4 clauses into φ′′′for each clause of φ′′.

144 / 163

Page 362: 27 NP Completness

Finally

Thus

SAT ≤p 3− CNF

Theorem 34.10Satisfiability of boolean formulas in 3-conjunctive normal form isNP-complete.

Now the next problemThe Clique Problem.

145 / 163

Page 363: 27 NP Completness

Finally

Thus

SAT ≤p 3− CNF

Theorem 34.10Satisfiability of boolean formulas in 3-conjunctive normal form isNP-complete.

Now the next problemThe Clique Problem.

145 / 163

Page 364: 27 NP Completness

Finally

Thus

SAT ≤p 3− CNF

Theorem 34.10Satisfiability of boolean formulas in 3-conjunctive normal form isNP-complete.

Now the next problemThe Clique Problem.

145 / 163

Page 365: 27 NP Completness

Excercises

From Cormen’s book solve34.4-134.4-234.4-534.4-634.4-7

146 / 163

Page 366: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

147 / 163

Page 367: 27 NP Completness

The Clique Problem

DefinitionA clique in an undirected graph G = (V ,E) is a subset V ′ ⊆ V ofvertices, each pair of which is connected by an edge in E .

As a decision problemCLIQUE = < G, k > | Gis a graph with a clique of size k

148 / 163

Page 368: 27 NP Completness

The Clique Problem

DefinitionA clique in an undirected graph G = (V ,E) is a subset V ′ ⊆ V ofvertices, each pair of which is connected by an edge in E .

As a decision problemCLIQUE = < G, k > | Gis a graph with a clique of size k

148 / 163

Page 369: 27 NP Completness

Example

A Clique of size k = 4

4

3 2

1

5

6

7

8 9

149 / 163

Page 370: 27 NP Completness

The clique problem is NP-Complete

Theorem 34.11The clique problem is NP-Complete.

Proof1 To show that CLIQUE ∈ NP, for a given graph G = (V ,E) we use

the set V ′ ∈ V of vertices in the clique as certificate for G.

ThusThis is can be done in polynomial time because we only need to check allpossibles pairs of u, v ∈ V ′, which takes |V ′| (|V ′| − 1).

150 / 163

Page 371: 27 NP Completness

The clique problem is NP-Complete

Theorem 34.11The clique problem is NP-Complete.

Proof1 To show that CLIQUE ∈ NP, for a given graph G = (V ,E) we use

the set V ′ ∈ V of vertices in the clique as certificate for G.

ThusThis is can be done in polynomial time because we only need to check allpossibles pairs of u, v ∈ V ′, which takes |V ′| (|V ′| − 1).

150 / 163

Page 372: 27 NP Completness

The clique problem is NP-Complete

Theorem 34.11The clique problem is NP-Complete.

Proof1 To show that CLIQUE ∈ NP, for a given graph G = (V ,E) we use

the set V ′ ∈ V of vertices in the clique as certificate for G.

ThusThis is can be done in polynomial time because we only need to check allpossibles pairs of u, v ∈ V ′, which takes |V ′| (|V ′| − 1).

150 / 163

Page 373: 27 NP Completness

Proof

Now, we only need to prove that the problem is NP-HardWhich is surprising, after all we are going from logic to graph problems!!!

NowWe start with an instance of 3-CNF-SAT

C1 ∧ C2 ∧ ... ∧ Ck a boolean 3-CNF formula with k clauses.

We know for each 1 ≤ r ≤ k

Cr = lr1 ∨ lr

2 ∨ lr3

151 / 163

Page 374: 27 NP Completness

Proof

Now, we only need to prove that the problem is NP-HardWhich is surprising, after all we are going from logic to graph problems!!!

NowWe start with an instance of 3-CNF-SAT

C1 ∧ C2 ∧ ... ∧ Ck a boolean 3-CNF formula with k clauses.

We know for each 1 ≤ r ≤ k

Cr = lr1 ∨ lr

2 ∨ lr3

151 / 163

Page 375: 27 NP Completness

Proof

Now, we only need to prove that the problem is NP-HardWhich is surprising, after all we are going from logic to graph problems!!!

NowWe start with an instance of 3-CNF-SAT

C1 ∧ C2 ∧ ... ∧ Ck a boolean 3-CNF formula with k clauses.

We know for each 1 ≤ r ≤ k

Cr = lr1 ∨ lr

2 ∨ lr3

151 / 163

Page 376: 27 NP Completness

Then

Now, we construct the following graph G = (V ,E)We place a triple of vertices vr

1 , vr2 , vr

3 for each Cr = lr1 ∨ lr2 ∨ lr3 .

We put an edge between two vertices vri and vs

j , ifvr

i and vsj are in different triples i.e. r 6= s.

Their corresponding literals are consistent i.e. lri is not the negationof lsj

152 / 163

Page 377: 27 NP Completness

Then

Now, we construct the following graph G = (V ,E)We place a triple of vertices vr

1 , vr2 , vr

3 for each Cr = lr1 ∨ lr2 ∨ lr3 .

We put an edge between two vertices vri and vs

j , ifvr

i and vsj are in different triples i.e. r 6= s.

Their corresponding literals are consistent i.e. lri is not the negationof lsj

152 / 163

Page 378: 27 NP Completness

Then

Now, we construct the following graph G = (V ,E)We place a triple of vertices vr

1 , vr2 , vr

3 for each Cr = lr1 ∨ lr2 ∨ lr3 .

We put an edge between two vertices vri and vs

j , ifvr

i and vsj are in different triples i.e. r 6= s.

Their corresponding literals are consistent i.e. lri is not the negationof lsj

152 / 163

Page 379: 27 NP Completness

Example

For φ = (x1 ∨ ¬x2 ∨ ¬x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)

153 / 163

Page 380: 27 NP Completness

Now, we show that the transformation φ into G is areduction

We start with the =⇒Suppose φ has a satisfying assignment.Thus each clause Cr contains at least one literal lri mapping to 1,which corresponds to a vertex vr

i .

Now, we pick each of those literalsWe finish with a set V ′ of such literals.

V ′ is a clique, how?Given two vertices vr

i and vsj ∈ V ′, with r 6= s, such that the

corresponding literals lri and lsj map to 1 by the satisfying assignment.

154 / 163

Page 381: 27 NP Completness

Now, we show that the transformation φ into G is areduction

We start with the =⇒Suppose φ has a satisfying assignment.Thus each clause Cr contains at least one literal lri mapping to 1,which corresponds to a vertex vr

i .

Now, we pick each of those literalsWe finish with a set V ′ of such literals.

V ′ is a clique, how?Given two vertices vr

i and vsj ∈ V ′, with r 6= s, such that the

corresponding literals lri and lsj map to 1 by the satisfying assignment.

154 / 163

Page 382: 27 NP Completness

Now, we show that the transformation φ into G is areduction

We start with the =⇒Suppose φ has a satisfying assignment.Thus each clause Cr contains at least one literal lri mapping to 1,which corresponds to a vertex vr

i .

Now, we pick each of those literalsWe finish with a set V ′ of such literals.

V ′ is a clique, how?Given two vertices vr

i and vsj ∈ V ′, with r 6= s, such that the

corresponding literals lri and lsj map to 1 by the satisfying assignment.

154 / 163

Page 383: 27 NP Completness

Now, we show that the transformation φ into G is areduction

We start with the =⇒Suppose φ has a satisfying assignment.Thus each clause Cr contains at least one literal lri mapping to 1,which corresponds to a vertex vr

i .

Now, we pick each of those literalsWe finish with a set V ′ of such literals.

V ′ is a clique, how?Given two vertices vr

i and vsj ∈ V ′, with r 6= s, such that the

corresponding literals lri and lsj map to 1 by the satisfying assignment.

154 / 163

Page 384: 27 NP Completness

Then

This two literalsThey cannot be complements.

FinallyBy construction of G, the edge

(vr

i , vsj

)belongs to E .

ThusWe have a clique of size k in the graph G = (V ,E).

155 / 163

Page 385: 27 NP Completness

Then

This two literalsThey cannot be complements.

FinallyBy construction of G, the edge

(vr

i , vsj

)belongs to E .

ThusWe have a clique of size k in the graph G = (V ,E).

155 / 163

Page 386: 27 NP Completness

Then

This two literalsThey cannot be complements.

FinallyBy construction of G, the edge

(vr

i , vsj

)belongs to E .

ThusWe have a clique of size k in the graph G = (V ,E).

155 / 163

Page 387: 27 NP Completness

We now prove⇐=

ConverselySuppose that G has a clique V ′ of size k.

Did you notice?No edges in G connect vertices in the same triple, thus V ′ contains onevertex per triple.

NowNow, we assign 1 to each literal lri such that vr

i ∈ V ′

Notice that we cannot assign 1 to both a literal and its complementby construction.

156 / 163

Page 388: 27 NP Completness

We now prove⇐=

ConverselySuppose that G has a clique V ′ of size k.

Did you notice?No edges in G connect vertices in the same triple, thus V ′ contains onevertex per triple.

NowNow, we assign 1 to each literal lri such that vr

i ∈ V ′

Notice that we cannot assign 1 to both a literal and its complementby construction.

156 / 163

Page 389: 27 NP Completness

We now prove⇐=

ConverselySuppose that G has a clique V ′ of size k.

Did you notice?No edges in G connect vertices in the same triple, thus V ′ contains onevertex per triple.

NowNow, we assign 1 to each literal lri such that vr

i ∈ V ′

Notice that we cannot assign 1 to both a literal and its complementby construction.

156 / 163

Page 390: 27 NP Completness

Finally

We have with that assignmentThat each clause Cr is satisfied, thus φ is satisfied!!!

NoteAny variables that do not correspond to a vertex in the clique may be setarbitrarily.

Then

3− CNF ≤p CLIQUE

157 / 163

Page 391: 27 NP Completness

Finally

We have with that assignmentThat each clause Cr is satisfied, thus φ is satisfied!!!

NoteAny variables that do not correspond to a vertex in the clique may be setarbitrarily.

Then

3− CNF ≤p CLIQUE

157 / 163

Page 392: 27 NP Completness

Finally

We have with that assignmentThat each clause Cr is satisfied, thus φ is satisfied!!!

NoteAny variables that do not correspond to a vertex in the clique may be setarbitrarily.

Then

3− CNF ≤p CLIQUE

157 / 163

Page 393: 27 NP Completness

Remarks

Something NotableWe have reduced an arbitrary instance of 3-CNF-SAT to an instance ofCLIQUE with a particular structure.

ThusIt is possible to think that we have shown only that CLIQUE is NP-hard ingraphs in which the vertices are restricted to occur in triples and in whichthere are no edges between vertices in the same triple.

Actually this is trueBut it is enough to prove that CLIQUE is NP-hard.Why? If we had a polynomial-time algorithm that solved CLIQUE inthe general sense, we will solve in polynomial time the restrictedversion.

158 / 163

Page 394: 27 NP Completness

Remarks

Something NotableWe have reduced an arbitrary instance of 3-CNF-SAT to an instance ofCLIQUE with a particular structure.

ThusIt is possible to think that we have shown only that CLIQUE is NP-hard ingraphs in which the vertices are restricted to occur in triples and in whichthere are no edges between vertices in the same triple.

Actually this is trueBut it is enough to prove that CLIQUE is NP-hard.Why? If we had a polynomial-time algorithm that solved CLIQUE inthe general sense, we will solve in polynomial time the restrictedversion.

158 / 163

Page 395: 27 NP Completness

Remarks

Something NotableWe have reduced an arbitrary instance of 3-CNF-SAT to an instance ofCLIQUE with a particular structure.

ThusIt is possible to think that we have shown only that CLIQUE is NP-hard ingraphs in which the vertices are restricted to occur in triples and in whichthere are no edges between vertices in the same triple.

Actually this is trueBut it is enough to prove that CLIQUE is NP-hard.Why? If we had a polynomial-time algorithm that solved CLIQUE inthe general sense, we will solve in polynomial time the restrictedversion.

158 / 163

Page 396: 27 NP Completness

Remarks

In the opposite approachReducing instances of 3-CNF-SAT with a special structure to generalinstances of CLIQUE would not have sufficed.

Why not?Perhaps the instances of 3-CNF-SAT that we chose to reduce fromwere “easy,” not reducing an NP-Hard problem to CLIQUE.Observe also that the reduction used the instance of 3-CNF-SAT, butnot the solution.

159 / 163

Page 397: 27 NP Completness

Remarks

In the opposite approachReducing instances of 3-CNF-SAT with a special structure to generalinstances of CLIQUE would not have sufficed.

Why not?Perhaps the instances of 3-CNF-SAT that we chose to reduce fromwere “easy,” not reducing an NP-Hard problem to CLIQUE.Observe also that the reduction used the instance of 3-CNF-SAT, butnot the solution.

159 / 163

Page 398: 27 NP Completness

Thus

This would have been a serious errorRemember the mapping:

160 / 163

Page 399: 27 NP Completness

Outline1 Introduction

Polynomial TimeThe Intuition P vs NP

2 Structure of the Polynomial Time ProblemsIntroductionAbstract ProblemsEncodingFormal Language FrameworkDecision Problems in The Formal FrameworkComplexity Class

3 Polynomial Time VerificationIntroductionVerification Algorithms

4 Reducibility and NP-CompletnessIntroductionNP-CompletnessAn Infamous Theorem

5 NP-Complete ProblemsCircuit SatisfiabilityHow do we prove NP-Completness?Algorithm A representationThe Correct ReductionThe Polynomial Time

Making our life easier!!!Formula Satisfiability3-CNFThe Clique ProblemFamily of NP-Complete Problems

161 / 163

Page 400: 27 NP Completness

Now, we haveFamily of NP-Complete Problems

CIRCUIT-SAT

SAT

3-CNF-SAT

CLIQUE SUBSET-SUM

VERTEX-COVER

HAMILTONIAN-CYCLE

TRAVELING SALESMAN PROBLEM

162 / 163

Page 401: 27 NP Completness

Excercises

From Cormen’s book solve34.5-134.5-234.5-334.5-434.5-534.5-734.5-8

163 / 163


Recommended