Udowodnienie, że DOUBLE-SAT jest NP-zakończone

13

Dobrze znany problem SAT został tu zdefiniowany dla odniesienia.

Problem DOUBLE-SAT jest zdefiniowany jako

DOUBLE-SAT={ϕϕ has at least two satisfying assignments}

Jak udowodnimy, że jest kompletny NP?

Doceniony zostanie więcej niż jeden sposób udowodnienia.

pnp
źródło

Odpowiedzi:

27

Oto jedno rozwiązanie:

NPϕ(x1,,xn)ϕ

NP

ϕ(x1,,xn)

  1. y
  2. ϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯)

ϕ(x1,,xn)ϕϕ(x1,,xn,y)yy¯y=1y=0yϕx1xny

ϕ(x1,,xn)SATϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯)ϕ(x1,,xn,y)Double-SAT

SATpDouble-SATNP

pnp
źródło
To milsze niż moja propozycja.
Raphael
10

SATSATDOUBLE-SAT

φφf(φ)φf

Raphael
źródło