CSE 565 , lecture 15 , 10/18/2021
Deft polynomial-time reduction) : Let ✗ and Y be two problems .
If one can design an algorithm for X, such that this algorithm uses
polynomial number of calls to a solver for Y, plus polynomial
number of additional instructions , then we say ✗ is
polynomial – time reducible to Y, denoted as ✗ =p Y .
Fact : If ✗ =p Y and Y can be soluedinpolytme ,
then X can be solved in poly – trine .
Deft decision problem) : output is
”
Yes
”
or
”
No
”
.
decision – version of optimization problem
E×ampk_ : decision versionotvertex-wnerprobkm-7-m-wt.G-lv.FI
. integer K > 0 .
output : if I VC , V, c- V. sit. IV. Is K
,
then ” Yes ”
otherwise “No ” .
decision version us. optimization version
VCCG , K) VCIG)
=at VCCG , K ) Ep VCCG)
proof : Algo – for – VC CG , K)
v7← solver – for – Vc (G)
| if Witek : return
”
Yes
”
end
else return
”
No
”
. ☒ .
Fat VCCG) Ep VCCG, K) .
Proof : Algo – for – VC – size (G) * to find IVFI *I
f
for k= 0 to 14
B ← solver – for – VCCG , K)
end .
eld it Bikes ” return K
now we know K’
+ =/ Vil
.
☒¥q↳ a–A
Fat: A EVP ⇐ G-A can be covered by 1kt – 1) vertices .
Algo – for – Vc (G) n= WI
k’t ← Algo – for – VC – size (G)
for v E V
B← solver – for – V1 CG.ve KED\ / ” “”E.¥:S” :#may . -t.rcca.nu ”
end
end
Running-hmi-i.tn/–n.scdecision1tn(OlnJ-sldecision))tTln-D
⇒ 1- (a) = ri .SCdecision) + D- lad) ☒ .
Note : optimization -version and Eisner are equivalent .
P : the set of decision problems that are polynomial – tinie solvabte .
NP : the set of decision problems that are polynomial – tinie verifiable .
Det CP) : Let ✗ be a decision problem . We say ✗ c- P if
there exists a polynomial – time procedure A C solver) , sit .
i. input of A is an instance ✗ of ✗
2. For any instance × of ✗
if ✗ is a
”
true
”
– instance
,
then A 1×1 =
”
Yes
”
if ✗ is a ” false
”
– instance
,
then AIX) =
”
NO”
Det INP) : Let ✗ be a decision problem . We say ✗ c- NP if
there exists a polynomial – time procedure A verifier , sit .
–
i. input of A is an instance ✗ of ✗ plus a certificate c.
1solution
2. For any instance × of ✗
if ✗ is a
”
true
”
– instance
,
then 7- C , sit . Alx . =
”
Yes
”
.
if ✗ is a ” false
”
– instance
,
then V-c.s.t-AIX.cl = “NO”.
Example: V1 C G , K) c- NP
‘
proof . verifier 1 G , K , c) a-
= IV. E)
y
it c is not a subset of V: return
”
no
”
it ICI > K : return
”
No
”
if c covers all edges : return
”
yes
”
end else
return ” no
”
i. It IG , K) is
”
true
”
– instance
⇐ 7- VC
,
V , EV , sit . Wil Ek
⇒ let c- V1 ⇒ Verifier / G. K . c) returns
”
Yes
”
2 . If CG , K) is
”
false
”
– instance
⇐ # VC , Vi EV sit . Wil a- K .
⇒ verifier will return
”
no
”
no matter which C is provided .
☒ ( NP-complete) : Let ✗ be a decision problem . We say
✗ is NP-complete, if .
” X c- Np
2. For X
‘
c- NP . X’ =p X .
theorem ( CL . 1971) : circuit satisfiability problem is NPC .