[11] np complete

56
Proiectarea algoritmilor: Probleme NP-complete Dorel Lucanu Faculty of Computer Science Alexandru Ioan Cuza University, Ia¸ si, Romania [email protected] PA 2014/2015 D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 1 / 56

Upload: eirdnocotim

Post on 17-Dec-2015

93 views

Category:

Documents


1 download

DESCRIPTION

[11] Np Complete

TRANSCRIPT

  • Proiectarea algoritmilor: Probleme NP-complete

    Dorel Lucanu

    Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

    [email protected]

    PA 2014/2015

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 1 / 56

  • Outline

    1 Clasele P si NP

    2 Rolul reducerii problemelor n analiza acestora

    3 Cateva probleme NP-complete importante

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 2 / 56

  • Clasele P si NP

    Plan

    1 Clasele P si NP

    2 Rolul reducerii problemelor n analiza acestora

    3 Cateva probleme NP-complete importante

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 3 / 56

  • Clasele P si NP

    Reamintire: probleme de decizie

    O problema de decizie este o problema P la care raspunsul este de formaDA sau NU (echivalent, true sau false). Mai precis, pentru oriceinstanta p P, P(p) {DA, NU} (P(p) {true, false}).

    O problema de decizie este reprezentata n general printr-o pereche(instance, question) (sau (instanta, ntrebare)).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 4 / 56

  • Clasele P si NP

    Exemplu de problema de decizie: SAT

    SATInstance O formula propozitionala F cu variabile din X = {x1, . . . , xn}.Question Exista o atribuire a : X {0, 1} (sau a : X {false, true})

    care satisface F?

    Exemplu de instanta:

    X = {x , y , z}F = ((x y) (x z)) ((y z) (x y z))

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 5 / 56

  • Clasele P si NP

    Exemplu de problema de decizie: CSAT

    CSATInstance O formula propozitionala F cu variabile din X = {x1, . . . , xn}

    si n forma normala conjunctiva.Question Exista o atribuire a : X {0, 1} (sau a : X {false, true})

    care satisface F?

    Exemplu de instanta:

    X = {x , y , z}F = (x y z) (x z) (x y z x)

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 6 / 56

  • Clasele P si NP

    Exemplu de problema de decizie: DSAT

    DSATInstance O formula propozitionala F cu variabile din X = {x1, . . . , xn}

    si n forma normala disjunctiva.Question Exista o atribuire a : X {0, 1} (sau a : X {false, true})

    care satisface F?

    Exemplu de instanta:

    X = {x , y , z}F = (x y z) (x z) (x y y z)

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 7 / 56

  • Clasele P si NP

    Exemplu de problema de decizie: k-CSAT

    k-SATInstance O formula propozitionala F cu variabile din X = {x1, . . . , xn},

    n forma normala conjunctiva si fiecare clauza (disjunctie) areexact k literali.

    Question Exista o atribuire a : X {0, 1} (sau a : X {false, true})care satisface F?

    Cazuri de interes: k = 3 (3-CSAT), k = 2 (2-CSAT).

    Exemplu de instanta 3-CSAT:

    X = {x , y , z}F = (x y z) (x y z) (y z x)Exemplu de instanta 2-CSAT:

    X = {x , y , z}F = (x y) (y z) (x z) (y z)

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 8 / 56

  • Clasele P si NP

    Exemplu de problema de decizie: CIRCUIT-SAT

    CIRCUIT-SATInstance Un circuit boolean construit cu portile logice AND, OR, NOT,

    si care are o singura iesire.Question Exista o atribuire de valori {0, 1} pentru intrarile circuitului

    astfel ncat valoarea de la iesire sa fie 1?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 9 / 56

  • Clasele P si NP

    Exemplu de circuit boolean

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 10 / 56

  • Clasele P si NP

    Reprezentarea problemelor de decizie ca limbaje

    Un limbaj L este o multime de siruri (cuvinte) peste un alfabet dat (L ).Putem presupune ca o instanta (intrare) a unei probleme este codificata deun sir w peste un alfabet dat A. Putem presupune ca = {0, 1} (w esteun sir de biti).

    Limbajul definit de o problema de decizie P este LP este multimeacodificarilor w ale instantelor pentru care raspunsul este DA (true).

    O problema de decizie P poate fi reprezentata acum ca o problema deapartenenta la un limbaj:

    Instance , L , w .Question w L?

    Daca A este un algoritm care rezolva P, atunci spunem ca L este acceptatde A (sau ca A accepta L).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 11 / 56

  • Clasele P si NP

    Reamintire: algoritmi nedeterministi

    Activitatea unui algoritm nedeterminist se desfasoara n doua etape: ntr-o primaetapa se ghiceste o anumita structura S si n etapa a doua se verifica daca Ssatisface o conditia de rezolvare a problemei. Putem adauga puteri magice deghicire unui limbaj de programare adaugandu-i o functie de forma:

    random(N) care ntoarce un numar aleatoriu din multimea{0, 1, . . . , n 1}.

    Observatie. Alternativ se poate considera un operator de alegere nedeterminista:S1 | S2 | | Sn cu semanticaS1 | S2 | | Sn Si , i = 1, . . . , nPentru a sti daca verificarea s-a terminat cu succes sau nu adauga si douainstructiuni de terminare:

    success care semnaleaza terminarea verificarii (si a algoritmului) cusucces, si

    failure care semnaleaza terminarea verificarii (si a algoritmului) farasucces.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 12 / 56

  • Clasele P si NP

    Probleme de decizie rezolvate de algoritmi nedeterministi

    Intuitiv, un algoritm nedeterminist A rezolva o problema P daca pentruorice instanta p P exista un calcul al lui A care pleaca dintr-oconfiguratie initiala ce codifica p, se termina cu succes si ofera raspunsulP(p) codificat n configuratia finala.

    Un caz aparte l constituie problemele de decizie:

    Definitie

    Un algoritm nedeterminist rezolva o problema de decizie daca se terminacu succes atunci si numai atunci cand raspunsul este DA (true).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 13 / 56

  • Clasele P si NP

    Clasele P si NP

    P = clasa problemelor P pentru care exista un algoritm determinist carerezolva P n timp polinomial

    NP = clasa problemelor P pentru care exista un algoritm nedeterministcare rezolva P n timp polinomial.

    Deoarece orice algoritm determinist este un caz particular de algoritmnedeterminist, are loc incluziunea:

    P NP

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 14 / 56

  • Clasele P si NP

    O definitie alternativa pentru NP

    Definitia alternativa este bazata pe o verificare determinista si din acestmotiv este poate mai intuitiva.

    Consideram problemele reprezentate ca limbaje.

    Un limbaj L este verificat de un algorithm A daca pentru orice sir x L,exista un sir y astfel ncat A raspunde DA pentru intrarea x + y (+desemneaza concatenarea de siruri). Sirul y este un certificat pentruapartenenta lui x la L. De notat ca nu se verifica daca x L.Clasa NP este definita ca fiind clasa limbajelor, definind probleme dedecizie, ce pot fi verificate n timp polinomial. Adica exista un algoritm A,care pentru orice x din L verifica daca intr-adevar x L utilizand uncertificat y . Dimensiunea unei instante este lungimea n a lui x . Daca Aface verificarea n timpul p(n) (p un polinom), atunci lungimeacertificatului y va fi p(n).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 15 / 56

  • Clasele P si NP

    Echivalenta celor doua definitii

    Exercitiu. Sa se arate ca cele doua definitii sunt echivalente.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 16 / 56

  • Clasele P si NP

    P NP sau P = NP?

    Algoritmii nedeterministi constituie un instrument mult mai puternic decatcei deterministi si pana acum nu s-a putut gasi o metoda prin carealgoritmi nedeterministi sa poata fi convertiti n algoritmi deterministi ntimp polinomial.

    Aceste argumente conduc la ideea ca raspunsul este P NP, dardemonstratia pare a tine de fenomene pe care nu le stapanim deocamdata.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 17 / 56

  • Rolul reducerii problemelor n analiza acestora

    Plan

    1 Clasele P si NP

    2 Rolul reducerii problemelor n analiza acestora

    3 Cateva probleme NP-complete importante

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 18 / 56

  • Rolul reducerii problemelor n analiza acestora

    Reamintire: Reducerea Turing/Cook)

    Problema P se reduce polinomial la problema (rezolvabila) Q, notamP Q, daca se poate construi un algoritm care rezolva P dupaurmatoarea schema:

    1 se considera la intrare o instanta p a lui P;

    2 preproceseaza n timp polinomial intrarea p

    3 se apeleaza algoritmul pentru Q, posibil de mai multe ori (un numarpolinomial)

    4 se postproceseaza rezultatul dat de Q n timp polinomial

    Daca pasii de preprocesare si postprocesare necesita O(g(n)) timp, atunciscriem P g(n) Q. Daca g(n) este un polinom dar nu intereseaza, scriemdoar P Q.Reducerea Turing/Cook se mai numeste si reducerea many-many.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 19 / 56

  • Rolul reducerii problemelor n analiza acestora

    Reducerea relativ la un oracol

    Atunci cand este definita n modelul de calcul al masinilor Turing,algoritmul pentru Q este abstractizat prntr-un oracol (pentru a prinde sicazul cand nu se stie dca exista un algoritm pentru Q; de exemplu cand Qeste problema opririi).

    Rolul oracolului este de a furniza un model de calcul care sa poata rapundela ntrebari de forma Daca stiu sa rezolv Q, atunci ce altceva mai potrezolva? (complexitate relativa)

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 20 / 56

  • Rolul reducerii problemelor n analiza acestora

    Reamintire: Reducerea Karp

    Se considera P si Q probleme de decizie.Problema P se reduce polinomial la problema (rezolvabila) Q, notamP Q, daca se poate construi un algoritm care rezolva P dupaurmatoarea schema

    1 se considera la intrare o instanta p a lui P;

    2 preproceseaza n timp polinomial intrarea p

    3 se apeleaza (o singura data) algoritmul pentru Q

    4 raspunsul pentru Q este acelasi cu cel al lui P (fara postprocesare)

    Daca pasul de preprocesare necesita O(g(n)) timp, atunci scriemP g(n) Q. Daca g(n) este un polinom dar nu intereseaza, scriem doarP Q.Reducerea Karp se mai numeste si reducerea many-one.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 21 / 56

  • Rolul reducerii problemelor n analiza acestora

    Relatia dintre cele doua reduceri

    Reducerea Karp implica reducere Turing/Cook.

    Exista perechi de probleme pentru care se cunoaste reducere Turing/Cookdar nu se stie daca exista reducere Karp.

    Reducerea Karp permite analize mai fine. De exemplu daca vom consideraproblema 3-SAT, care decide daca o formula n forma 3-CNF estenesatisfiabila, atunci avem 3-SAT 3-SAT cu reducerea Turing/Cook(este suficient sa negam raspunsul dat de oracol). Vom vedea mai tarziuca aceasta influenteaza direct relatia dintre clasele NP si co-NP.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 22 / 56

  • Rolul reducerii problemelor n analiza acestora

    Echivalenta

    Problemele P si Q sunt echivalente (Karp sau Turing/Cook) daca P Qsi Q P.

    Este surprinzator de observat ca numarul claselor de echivalenta esteextrem de mic n raport cu ntreaga clasa de probleme. Complexitatea uneiprobleme se poate determina aratand ca problema este echivalenta(computational) cu una dintr-o lista relativ scurta.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 23 / 56

  • Rolul reducerii problemelor n analiza acestora

    Proprietati ale reducerii

    Definitie

    O clasa C de probleme este nchisa la o reducere (Karp sau Turing/Cook)daca ori de cate ori P Q si Q C, rezulta P C.

    Teorema

    P este nchisa la ambele reduceri, Karp s Turing/Cook.

    Exercitiu. Sa se demonstreze teorema.

    Teorema

    Ambele reduceri, Karp si Turing/Cook, sunt tranzitive.

    Exercitiu. Sa se demonstreze teorema.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 24 / 56

  • Rolul reducerii problemelor n analiza acestora

    Reducerea problemelor de optim la problema de decizie

    RUCSAC II OPTIMInput wi Z+, pi Z, i = 1, . . . , n

    M ZOutput xi {0, 1}, i = 1, . . . , n cu proprietatea maximizeaza functia

    obiectiv si obiectele alese ncap n rucsac:

    maxni=1

    xi pini=1

    xi wi M

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 25 / 56

  • Rolul reducerii problemelor n analiza acestora

    Reducerea problemelor de optim la problema de decizie

    RUCSAC II DECIZIEInstance wi Z+, pi Z, i = 1, . . . , n

    M Z+K Z+ (scop)

    Question Exista xi {0, 1}, i = 1, . . . , n cu proprietatea ca scopul esteatins si obiectele alese ncap n rucsac:ni=1

    xi pi Kni=1

    xi wi M?

    Theorem

    RUCSAC II OPTIM RUCSAC II DECIZIE (reducere Turing/Cook).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 26 / 56

  • Rolul reducerii problemelor n analiza acestora

    Ipoteza de lucru

    De acum consideram numai probleme de decizie si reducere Karp.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 27 / 56

  • Rolul reducerii problemelor n analiza acestora

    Completitudine

    Fie C o clasa de probleme.Definitie

    O problema P este C-dificila (hard) daca Q P pentru orice Q C.

    De remarcat ca nu trebuie sa avem P C.Definitie

    O problema P este C-completa daca este C-dificila s P C.C = P: probleme P-completeC = NP: probleme NP-completeS-a sperat ca se poate arata ca problemele NP-complete sunt n NP \ P.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 28 / 56

  • Rolul reducerii problemelor n analiza acestora

    Teorema lui Cook

    Teorema

    CSAT este NP-completa.

    CSAT a fost prima problema pentru care s-a demonstratNP-completitudinea (1971), utilizandu-se alta demonstratie.

    Vom demonstra teorema lui Cook dupa ce vom arata NP-completitudineaunei probleme mai simple, dar foarte apropiata de SAT.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 29 / 56

  • Rolul reducerii problemelor n analiza acestora

    Exemplu de circuit boolean

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 30 / 56

  • Rolul reducerii problemelor n analiza acestora

    CIRCUIT-SAT este NP-completa

    Teorema

    CIRCUIT-SAT este NP-completa.

    Demonstratie (schita).1. CIRCUIT-SAT este n NP. Exercitiu.2. Vom arata ca CIRCUIT-SAT este NP-dificila.Fie P o problema din NP. Exista un algoritm determinist A astfel ncat Peste verificat de A. Rezulta ca pentru orice instanta x P cu P(x) =DA exista un certificat y cu proprietatea ca se termina cu succes pentruintrarea x + y n timp polinomial. Fie n = |x | si p(n) timpul pentru cazulcel mai nefavorabil al lui A.Presupunem ca memoria peste care lucreaza A este o secventa de biti si catoate operatiile care se numara sunt la nivel de bit. Deoarece numarul debiti vizitati de A este cel mult p(n), rezulta ca activitatea unui pas al lui Apoate fi descrisa de un CPU S , format din portile logice AND, OR, NOT.Mai mult, numarul portilor este cel mult O(p(n)2).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 31 / 56

  • Rolul reducerii problemelor n analiza acestora

    CIRCUIT-SAT este NP-completa

    x" w" A"y"

    S"

    x" w" A"y"

    p(n)

    x este instanta lui P,y este certificatul,W este memoria de lucru (e.g., valorile variabilelor din program si contorulde program),A este algoritmul A reprezentat ca sir de biti.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 32 / 56

  • Rolul reducerii problemelor n analiza acestora

    CIRCUIT-SAT este NP-completa

    Executia algorimului A pentru o intrare x de dimensiune n poate fisimultaa de un circuit boolean C compus din p(n) copii ale lui S (cate unapentru fiecare pas) asezate astfelncat iesirea de la unul este intrare pentruurmatorul.

    Se dauga la ultima copie o iesire care va avea valoarea 1 daca si numaidaca A se termina cu succes (certifica pe x).

    Pentrun x dat, intrarile circuitului C depind doar de y .

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 33 / 56

  • Rolul reducerii problemelor n analiza acestora

    CIRCUIT-SAT este NP-completa

    p(n)

    x" w" A"y"

    S"

    x" w" A"y"

    S"

    x" w" A"y"

    S"

    S"

    x" w" A"y"

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 34 / 56

  • Rolul reducerii problemelor n analiza acestora

    CIRCUIT-SAT este NP-completa

    Trebuie sa aratam ca exista o atribuire de valori la intrare astfel ncatcircuitul C are la iesire 1 daca si numai daca A se termina cu succespentru un certicat y .

    Daca exista o atribuire de valori la intrare astfel ncat iesirea lui C este 1,atunci certificatul y este dat de valorilor intrarilor corespunzatoare lui y .Algoritmul A se termina cu succes pentru ca C simuleaza activitatea sa siare iesirea numai n cazul cand A certifica apartenenta lui x la P.

    Reciproc, daca a lgoritmul A se termina cu succes pentru x cu certificatuly , atunci atribuirea intrarilor va fi cea data de acest certificat.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 35 / 56

  • Rolul reducerii problemelor n analiza acestora

    Demonstrarea NP-completitudinii prin reducere

    Theorem

    Daca Q este NP-completa, P este n NP si Q P, atunci P esteNP-completa.

    Se utilizeaza faptul ca este tranzitiva.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 36 / 56

  • Rolul reducerii problemelor n analiza acestora

    Teorema lui Cook (continuare)

    Teorema

    CSAT este NP-completa.

    Demonstratie (schita).1. CSAT este n NP. Exrecitiu.2. Vom arata ca CIRCUIT-SAT CSAT.Fiecare poarta logica g poate fi descrisa cu o formula Fg astfel ncat Fgeste satisfiabila daca si numai daca valoarea de la iesire corespundeoperatiei efectuate peste intrari. Exemple

    NOTPresupunem ca intrarea este modelata de variabila u si iesirea de variabilav . FNOT este (u v) (u v). )ANDPresupunem ca intrarea este modelata de variabilele u, v si iesirea devariabila w . FAND este (u w) (v w) (w u v).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 37 / 56

  • Rolul reducerii problemelor n analiza acestora

    3-CSAT este NP-completa

    Teorema

    3-CSAT este NP-completa.

    Clauzele obtinute din portile booleene au lungimea 2 sau 3. Orice clauzade lungime 2 u v este eqchivalenta cu conjuntia a doua clauze delungime 3: (u v w) (u v w).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 38 / 56

  • Rolul reducerii problemelor n analiza acestora

    Demonstrarea NP-completitudinii prin caz particular

    Theorem

    Daca Q este NP-completa, P este n NP si Q este un caz particular al luiP, atunci P este NP-completa.

    Corolar

    SAT este NP-completa.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 39 / 56

  • Rolul reducerii problemelor n analiza acestora

    Atentie la reducrea SAT g(n) CSATOrice formula booleana poate fi transformata n una echivalenta n formanormala conjunctiva:

    negatia este mpinsa n interior cu legile lui De Morgan:(u v) u v(u v) u vdisjunctia de la ra dacina este eliminata prin distributivitate:u (v w) (u v) (u w)dubla negatie: u u

    Rezulta SAT g(n) CSAT.Reducerea nu este polinomiala (g(n) nu este polinom): lungimea formuleitransformate poate fi exponentiala comparativ cu lungimea formuleiinitiale:(x y) (u v) (x u) (y u) (x v) (y v)Din acest motiv aceasta reducere nu poate fi utilizata pentru a arataNP-completitudinea lui SAT.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 40 / 56

  • Rolul reducerii problemelor n analiza acestora

    DSAT este n P

    Analog obtinem SAT g(n) DSAT, dar, din nou, nu putem deduce caDSAT este NP-completa.

    Mai mult, DSAT este n P:Exemplu: F = (x y z) (x z) (x y y z)

    o formula DNF F este satisfiabila exista o clauza satisfiabiao clauza este satisfiabila nu include x si x pentru o variabila xoarecare

    Observatie. In [LC08] exista o afirmatie gresita despre DSAT.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 41 / 56

  • Rolul reducerii problemelor n analiza acestora

    2-CSAT este n P

    se alege o variabila x si i se atribuie o valoare care satisface cel putino clauza

    apoi se calculeaza (prin propagare) valorilor variabilelor care apar naceeasi clauza cu x

    daca procesul se oprete si au mai ramas clauze, atunci acestea suntindependente de atribuirea de valori pentru cele eliminate; procedeulcontinua pentru clauzele ramase.

    Exemplu:(x1 x2) (x2 x3) (x1 x2) (x3 x4) (x3 x5) (x4 x5) (x3 x4)

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 42 / 56

  • Rolul reducerii problemelor n analiza acestora

    INDEPENDENT-SET

    Domeniul problemei:Fie G = (V ,E ) un graf. O submultime U V se numeste independentadaca oricare doua varfuri din U nu sunt adiacente.

    INDEPENDENT-SETInstance Un graf G = (V ,E ), un numar ntreg k 0.Question Exista o submultime U V independenta cu cel putin k

    elemente? (|U| k).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 43 / 56

  • Rolul reducerii problemelor n analiza acestora

    INDEPENDENT-SET

    Lema

    3-SAT INDEPENDENT-SET.Fie F o formula 3CNF cu variabilele {x1, . . . , xn} si m clauze C1, . . . ,Cm.Construim GF astfel:

    exista 2n varfuri-treapta x1, . . . , xn, x1, . . . , xn (x i corespunde lui xi ) si cateo muchie [xix i ];

    pentru fiecare clauza Cj se construieste o componenta distincta care are cavarfuri sunt etichetate cu literalii din clauze si exista muchie ntre oricaredoua varfuri ale componentei;

    pentru fiecare nod etichetat cu un xi exista o muchie ce leaga componentacu opusul x i ;

    pentru fiecare nod etichetat cu un x i exista o muchie ce leaga componentacu opusul xi .

    Instanta F este transformata n (GF , k = n + m).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 44 / 56

  • Rolul reducerii problemelor n analiza acestora

    INDEPENDENT-SET: Exemplu

    F = (x1 x2 x3) (x1 x2 x3).x

    xx

    HHHH

    HHHH

    x

    xx

    HHHH

    HHHH

    x x

    x x

    x x

    HHHH

    AAAAAAAAAAAAAAA

    HHHHHHHH

    I

    I

    Ix1

    x2

    x1

    x2

    x3x3

    I

    I

    x2

    x3

    x2

    x1

    x1

    x3

    Figure 1: Construction in the proof of NP-completeness of Independent Set for the formula(x1 _ x2 _ x3) ^ (x1 _ x2 _ x3). The independent set of size 5 corresponding to the satisfyingassignment x1 = false, x2 = true, and x3 = true is shown by nodes marked I.

    14

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 45 / 56

  • Rolul reducerii problemelor n analiza acestora

    INDEPENDENT-SET: corectitudine

    Trebuie sa aratam ca F este satisfiabila daca si numai daca exista omultime independenta cu n + m elemente.U se construieste astfel: se alege cate un varf din fiecare componenta Cj sicate unul dintre varfurile-treapta xi sau x i astfel ncat:

    daca din Cj se alege un varf etichetat cu xi , atunci se va alege sivarful-treapta xi ;

    daca din Cj se alege un varf etichetat cu x i , atunci se va alege sivarful-treapta x i ;

    Atribuirea a care satisface F va fi data de a(xi ) = 1 daca xi U, a(xi ) = 0daca x i U.Teorema

    INDEPENDENT-SET este NP-completa.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 46 / 56

  • Rolul reducerii problemelor n analiza acestora

    VERTEX-COVER

    Domeniul problemei:Fie G = (V ,E ) un graf. O submultime W V se numeste V-acoperiredaca oricare muchie din E este incidenta ntr-un varf din W .

    VERTEX-COVERInstance Un graf G = (V ,E ), un numar ntreg k 0.Question Exista o submultime W V care este V-acoperire si are cel

    mult k elemente? (|W | k).

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 47 / 56

  • Rolul reducerii problemelor n analiza acestora

    VERTEX-COVER

    Lema

    INDEPENDENT-SET VERTEX-COVER.O instanta (G , k) este transformata ntr-o instanta (G , n k).Teorema

    VERTEX-COVER este NP-completa.

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 48 / 56

  • Cateva probleme NP-complete importante

    Plan

    1 Clasele P si NP

    2 Rolul reducerii problemelor n analiza acestora

    3 Cateva probleme NP-complete importante

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 49 / 56

  • Cateva probleme NP-complete importante

    Multimi

    SUBSET-SUMInstance O multime A, o marime s(a) Z+, pentru orice a A si

    K Z+.Question Exista o submultime A A pentru care suma marimilor

    elementelor din A sa fie exact K?

    SET-COVERInstance O coelctie de m multimi A1, . . . ,Am si k Z+.

    Question Exista o subcolectie de k multimi Ai1 , . . . ,Aik astfel ncat

    A1 Am = Ai1 Aik?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 50 / 56

  • Cateva probleme NP-complete importante

    Planificare

    MULTIPROCESSOR SCHEDULINGInstance O multime P de programe, un numar m de procesoare, un

    timp de executie t(p), pentru fiecare p P, si un termen D.Question Exista o planificare a procesoarelor pentru P astfel ncat

    orice program sa fie executat nainte de termenul D?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 51 / 56

  • Cateva probleme NP-complete importante

    Algebra

    QUADRATIC RESIDUUInstance Intregii pozitivi a, b, c .

    Question Exista un ntreg pozitiv x < c astfel ncat x2 a (mod b)?QUADRATIC DIOPHANTIC EQUATIONS

    Instance Intregii pozitivi a, b, c .Question Exista x , y Z+ astfel ncat ax2 + by = c?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 52 / 56

  • Cateva probleme NP-complete importante

    Programare matematica

    INTEGER PROGRAMMING

    Instance O multime X de perechi (x , b), unde x = (x1, . . . , xm), xi , b Z, osecventa c = (c1, . . . , cm) si un ntreg K .

    Question Exista y = (y1, . . . , ym) astfel ncat:1

    i xiyi b pentru orice (x , b) X ;2

    i ciyi K?KNAPSACK 0/1

    Instance wi Z+, pi Z, i = 1, . . . , nM Z+K Z+ (scop)

    Question Exista xi {0, 1}, i = 1, . . . , n cu proprietatea ca scopul este atinssi obiectele alese ncap n rucsac:ni=1

    xi pi Kni=1

    xi wi M?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 53 / 56

  • Cateva probleme NP-complete importante

    Grafuri

    K -COLORINGInstance Un graf G = (V ,E ) si k Z+.

    Question Exista o colorare cu k culori a grafului G?

    HAMILTONIAN CIRCUIT DIGRAPHInstance Un digraf D = (V ,A).

    Question Contine D un circuit hamiltonian (circuit care trece printoate varfurile din V )?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 54 / 56

  • Cateva probleme NP-complete importante

    Grafuri

    HAMILTONIAN CIRCUIT GRAPHInstance Un graf G = (V ,E ).

    Question Contine G un circuit hamiltonian?

    TRAVELING SALESMAN PROBLEMInstance Un graf ponderat ((V ,E ), c) cu c(i , j) Z+ pentru orice

    muchie {i , j} E si K Z+.Question Exista un circuit hamiltonian de cost K?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 55 / 56

  • Cateva probleme NP-complete importante

    Grafuri

    LONGEST PATHInstance Un graf ponderat G = (V ,E ) cu ponderele ` : E Z+, un

    ntreg pozitiv K si doua varfuri distincte i si j .Question Exista n G un drum de la i la j de lungime K?

    D. Lucanu (FII - UAIC) Probleme NP-complete PA 2014/2015 56 / 56

    Clasele si NPRolul reducerii problemelor n analiza acestoraCteva probleme NP-complete importante