CS计算机代考程序代写 algorithm CSE 565 , lecture 15 , 10/18/2021

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 .