# 程序代写代做代考 algorithm Microsoft PowerPoint – lecture13 [Compatibility Mode]

Microsoft PowerPoint – lecture13 [Compatibility Mode]

COMS4236: Introduction to

Computational Complexity

Spring 2018

Mihalis Yannakakis

Lecture 13, 2/27/18

Proving a problem B is NP-complete

• Show the problem B is in NP

• Show B is NP-hard

1. Pick a problem A that you know is NP-hard, preferably a

problem close to B

2. Find an algorithm f that maps instances of A to instances

of B

3. Prove that if x is a Yes instance of A then f(x) is a Yes

instance of B

4. Conversely, prove that if f(x) is a Yes instance of B then x

is a Yes instance of A (equivalently, if x is a No instance of

A then f(x) is a No instance of B )

5. Prove that f runs in polynomial time (or log-space)

* If B is not a decision problem, formulate the corresponding

decision problem (NP is a class of decision problems)

Boolean Formula Satisfiability

• Special case of Circuit-SAT

• Boolean Formula with operators , , equivalent to

circuit that is a tree, the parse tree of the formula

x y z

( ( x y) (y) ) (x z) ( (y z) )

zyy x

CNF Satisfiability

• Boolean formula is in Conjunctive Normal Form (CNF) if

it is the AND of clauses where a clause is the OR of

literals. A literal is a variable or its negation.

( x y) (x y z) (x y z) ( y z )

Clauses

Disjunctive Normal Form (DNF): OR of ANDs of literals

Every Boolean function has an equivalent CNF (and DNF)

formula, but the conversion from a circuit or formula to a CNF

or DNF formula may incur an exponential blowup in size.

– Not a polynomial time reduction

CNF formula satisfiable truth assignment to the

variables that satisfies all the clauses

3SAT is NP-complete (Cook’s Theorem)

• 3SAT = Satisfiability of a CNF Boolean formula with 3

literals in each clause (a 3CNF formula).

• 3SAT in NP: “guess” a satisfying truth assignment (the

certificate) and check that it satisfies all the clauses

• 3SAT is NP-hard:

• Reduction from Fan-in 2 CIRCUIT-SAT.

Given circuit C with fan-in 2, will construct in polynomial

time a 3CNF formula such that C is satisfiable iff is

satisfiable.

From CIRCUIT-SAT to 3SAT ctd.

1. Introduce a variable for every input and gate of the circuit.

2. Include a set of clauses for each gate stating that the truth

value of the corresponding gate variable is the

NOT/AND/OR of the values of its input variables

a

b

a= b conjunction of clauses (ab), (ab)

a

b c

a=bc clauses (ab), (ac), (abc)

a

b c

a=bc clauses (ab), (ac), (abc)

3. Let ’ = conjunction of all the gate clauses and an

additional unit clause z, where z is the variable

corresponding to the output gate.

’ is a CNF formula with at most 3 literals per clause, and

’ is satisfiable iff the circuit C’ is satisfiable.

From CIRCUIT-SAT to 3SAT ctd.

Example

x y z Inputs

Output

Gates

Example

x y z

a c

d e

b

g

f

h

Example

x y z

a c

d e

b

g

f

h ( )

( ) ( ) ( )

( ) ( ) ( )

( ) ( )

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

( ) ( )

( ) ( ) ( )

h

h g h f h g f

g d g e g d e

f z f z

e b e c e b c

d a d b d a b

c y c z c y z

b y b y

a x a y a x y

’ is a CNF formula with at most 3 literals per clause, and

’ is satisfiable iff the circuit C’ is satisfiable.

4. Transform ’ to a 3CNF formula with exactly 3 literals

per clause:

– Replace each 2-literal clause (r1r2) by two clauses

(r1r2 p), (r1r2 p), where p is a new variable (or any

other variable of ’)

– Replace the 1-literal clause z by 4 clauses (zpq),

(zpq), (zpq), (zpq)

• The resulting 3CNF formula is satisfiable iff the circuit

C is satisfiable.

• can be constructed from C in log space (and

polynomial time)

From CIRCUIT-SAT to 3SAT ctd.

Not-All-Equal 3SAT (NAE3SAT)

• NAE clause: Set of literals. Clause is satisfied by a truth

assignment iff not all literals have the same truth value.

• NAE3SAT

• Input: Set of NAE clauses with 3 literals in each clause

• Question: assignment that satisfies all the clauses?

• NAE3SAT is NP-complete

• in NP: Guess a satisfying assignment

• NP-hard: Reduction from 3SAT

3SAT ≤log NAE3SAT

• 3SAT clause Ci=(abc) NAE clauses (a,b,yi), (yi,c,0)

where yi is a new variable corresponding to Ci

• If a truth assignment sets a=b=c=0, then the NAE clauses

become (0,0,yi), (yi,0,0) and cannot be satisfied no matter

what we set yi

• Conversely, if at least one of a,b,c is 1, then we can set yi

to satisfy both clauses (if a or b =1 then set yi=0, else 1).

The given set of 3SAT clauses has a satisfying truth

assignment iff the constructed set of NAE3SAT clauses

has a satisfying truth assignment

3SAT ≤log NAE3SAT ctd.

• The constructed NAE3SAT clauses contain the constant 0

• NAE3SAT is NP-complete even if we disallow constants

• Replace all occurrences of 0 by a new variable z.

• Since no constants, a truth assignment satisfies all

NAE3SAT clauses iff the complementary assignment (flip

all truth values) satisfies the clauses.

The new set of NAE3SAT clauses has a satisfying

assignment iff it has one that sets z=0, which is the case iff

the given set of 3SAT clauses has a satisfying assignment.

• 2SAT and NAE2SAT are in P