CS计算机代考程序代写 CSE 565

CSE 565
,

lecture 16
. 10/20/2021

Framework to prove a decision problem ✗ is NPC .

i. show that ✗ c-Np .

2. pick one existing NPC problem Y , , and then
show that yep X .

proof : let X’ be an arbitrary problem in NP .

YENPC, ⇒ ✗

spy

yep ✗ ⇒ ☒ Ep X . ☒ .

1¥ If ✗spy and Yep Z , then ✗ =p 21 transitive of Ep)

Satisfiability problem CSAT) –

Def : binary variable : ✗ i. Xz . . . Xm . Xi c- {on ] .
literati Xi or Ii

dause-idisj-g.in of literals
X , VXTV X4 , XIV Xz , XJ , ✗5

CNI I conjunction normal form) :
(“and”)

( xivxiv ✗4) A# vxz) ✗ (XJ) #-)
Inpu a CNF ( m variables . and n clauses)

outpu if there exists anassignmentforallvariabb-s.to
the CNF is true .

ZSAT : each clause contains exactly a literals .

(Xi V52 )NXz V54) ✗ (VTV ✗4) .
Fatin 2sAT C- P . lhomiwork

¥ : each clause contains exactly 3 literals .

claim : 3 SAT C- Npc .

proof:_ circuit satisfiability =p 3 SAT .

Independent set 17-5) problem .

Det 11s) : let G- = IV, E) be an undirected graph . We say
Vi EV is an IS if u.VE V1 , then in, v3 4- E.

☒ V1 = { B. F. G-} ian IS


V14 is a vc .

⑧ ⑧
optimization :(G) : to find an IS V1 , sit . 1h1 is maximized
decision I :G,k) : to decide . if 7- IS V1 . sit . 141 > K .

Fait : V1 is a IS if and only if V1 Vi is a VC .

FAI Vi
is a maximum IS iff VIVE is a minimum VC –

Inta ISCG is true iff VCCG.lu
– K) is true .

IS [ G , K) =p VCCG , K)
Ilp Ilp
IS (G) =p VC (G)

=p

to represent

mutually poly – time reducible

claim : ISCG , K) is NPC .

proof-ii.IS CG , K ) C- NP

z . pick 3. SAT . then show 3517T Ep ISCG, K) .
model ” Inflict

G : ④ VXTVXS ☒-④④-☒
Cai XTVXJV

↳ : xzvxctv

Cq : ④ VXJ V45
( m=5 variables

, n=4 clauses) . K=w

Fonti a CNF is true Iff we can pick a literal in every
clause , sit . these picked literals donltion-ti.tl Xi andIi
cannot be picked at the same time .) .

Fae ( Gin) is true iff the CNF is true .

Algo – for – 3 SATKNF)
construct Ct .

efnd
.

return solver- for-ISIG, n) ☒

input : X , Y, Z , E C- X✗Y×Z 0÷÷÷÷÷÷:.*÷÷⇐⇐” “don’t share vertices . and that
IMI is maximized .

perfected matching problem
input : 1×1=141–121 en .

output if a matching M sit.IM/–n.claiin-:perfect 3D matching problem is NPC .
proof : 1 . it is in Np .

2. pick 3 SAT , and then show 3SAT =p P3DM_

G : ④ VXTVXS
Cai XTVXJV

↳ : ④ VÑVX4
( m=4 variables , n=3 clauses) .

Xi X2 ✗3 X4


°

⑤ ‘+ 3- at o+ 3- at
3-1 2- 3-1 2- 3-1 2- 3-1 2-

G : ④VÑ V43 #red = Mnt n=(m+DW
Gi XT ✓ XJ ✓④

# blue = (mt) – n

# green = 2hm
↳ : ④ V52 V44
( m=4 variables , n=3 clauses) .

Xi X2 ✗3 X4

i%¥☒,

+

I
\ 3-1 2-¥;÷¥**¥¥.:-#be

00 . . . . – ← 00 : 2hm -1Mt)n = (M -D n pairs .
Hear-uppai

Note there are only 2 possibilities to pick triples in each unit :
either 11-1,2-1.3+1 are picked ⇐ Xi = false
or 11 – , 2-, 3-) are picked ⇐ Xi = true .

Fats the CNF is true if and only if the constructed
3D perfect matching instance is true .

Algo – for – 3 SAT CCNF)
construct the instance × , Y, Z , E showed above

efnd return solver – for – 3D-matching IX. Y, Z , E) 1¥