Probleme NP-Dificile ș i NP-Complet

Concepte de bază

•Solu ț ionabilitatea algoritmilor

Există algoritmi pentru care nu există o solu ț ie cunoscută, de exemplu, Problema opririi lui Turing.
Problemă de decizie
∗ Dat un algoritm determinist arbitrar A ș i o intrare finită I
∗ Se va termina vreodată WillA cu inputI, sau va intra într-un ciclu infinit?
Alan Turing a demonstrat că un algoritm general pentru a rezolva problema opririi pentru toate perechile posibile program-entrada
nu poate exista
Problema opririi nu poate fi rezolvată de niciun computer, indiferent de cât timp este oferit.
În termeni algoritmici, nu există niciun algoritm de nicio complexitate pentru a rezolva această problemă.

Algoritmi eficien ț i
Eficien ț a măsurată în termeni de viteză
Pentru unele probleme, nu există o solu ț ie eficientă cunoscută.
–Distinc ț ia între problemele care pot fi rezolvate în timp polinomial ș i problemele pentru care nu există timp polinomial
algoritmul este cunoscut

• Problemele clasificate ca apar ț inând uneia dintre cele două grupe

1. Probleme cu timpul de solu ț ionare limitat de un polinom de grad mic

–Cele mai multe algoritmi de căutare ș i sortare
–Numite ș i algoritmi tractabili
–De exemplu, căutare ordonată(O(lgn)), evaluare polinomială(O(n)), sortare(O(nlogn))
2. Probleme cu cele mai cunoscute algoritmi care nu sunt limita ț i de un polinom
–Probleme dificile sau nerecunoscute
–Vânzător mobil (O(n 2 2n )), rucsac (O(2n/2 ))
Niciuna dintre problemele din acest grup nu a fost rezolvată de nicio algoritm de timp polinomial.
Probleme NP-complete
∗ Niciun algoritm eficient pentru o problemă NP-completă nu a fost găsit vreodată; dar nimeni nu a reu ș it să
demonstrează că un astfel de algoritm nu există
–P=NP
Problema celebră deschisă în Ș tiinț a Calculatoarelor din 1971

Teoria NP-completitudinii
–Arată că multe dintre problemele fără algoritmi de timp polinomial sunt legate computa ț ional.
Grupul de probleme este împăr ț it în continuare în două clase
NP-complet. O problemă care este NP-completă poate fi rezolvată în timp polinomial dacă ș i numai dacă toate celelalte NP-complete
problemele pot fi, de asemenea, rezolvate într-un timp polinomial

Dacă o problemă NP-dificilă poate fi rezolvată în timp polinomial, atunci toate problemele NP-complete pot fi de asemenea rezolvate.
rezolvat în timp polinomial
Toate problemele NP-complete sunt NP-grele, dar unele probleme NP-grele sunt cunoscute că nu sunt NP-complete.

NP-complet⊂NP-dificil
• Probleme P vs NP
–Problemele din clasa P pot fi rezolvate în O(N k )timp, pentru un k constant (timp polinomial)
Probleme NP-Dificile ș i NP-Complet 2

Problemele din clasa NP nu pot fi verificate în timp polinomial.

Dacă ni se oferă un certificat al unei solu ț ii, putem verifica că certificatul este corect într-un timp polinomial în
dimensiunea inputului pentru problemă
–Unele probleme rezolvabile în timp polinomial arată foarte asemănător cu problemele NP-complete
Cea mai scurtă vs cea mai lungă cale simplă între vârfuri
Cel mai scurt drum de la o sursă unică într-un graf orientat G= (V, E) poate fi găsit în O(V E) timp
Găsirea celui mai lung drum între două vârfuri este NP-completă, chiar dacă greutatea fiecărei muchii este 1
–Turul lui Euler vs Ciclu Hamiltonian
Turul Euler al unui graf orientat conectat G = (V, E) este un ciclu care parcurge fiecare muchie a lui G exact o dată.
deș i poate vizita un vârf de mai multe ori; se poate determina în O(E) timp
Un ciclu Hamiltonian al unui graf orientat G = (V, E) este un ciclu simplu care con ț ine fiecare vârf din V.
Determinarea dacă un graf orientat are un ciclu hamiltonian este NP-complet.
Solutia este data de secven ț a hv1 , v2 , . . . , v astfel încât|V|pentru fiecare 1≤i <|V|,(v i , veu+1)∈E
Certificatul ar fi secven ț a de vârfuri de mai sus.
Este u ș or să verifici în timp polinomial că muchiile formate de secven ț a de mai sus sunt în E, ș i a ș a este ș i
marginev, v1 .
|V|
-2-Satisfiabilitatea CNF vs. satisfiabilitatea 3-CNF
O formulă Boolean are variabile care pot lua valori adevărat sau fals
Variabilele sunt conectate prin operatorii ∧ , ∨ ș i ¬
O formulă booleană este satisfiabilă dacă există o asignare de valori pentru variabilele sale care o face adevărată.
evaluarează-l ca adevărat
∗ O formulă booleană este în formă normală conjunctivă de tip ink (k-CNF) dacă esteANDul clauzelor deORuri de exact k
variabile sau negările lor
*2-CNF: (x1∨ ¬x2 )∧(¬x1∨x3 )∧(¬x2∨ ¬x3 )
Satisfăcut de1=adevărat,x2false,x3=adevărat
∗ Putem determina în timp polinomial dacă un 2-Formula CNF este satisfiabilă, dar satisfiabilitatea unei 3-CNF
formula este NP-completă
–P ⊆ NP
∗ Orice problemă în P poate fi rezolvată într-un timp polinomial chiar ș i fără certificat
Întrebarea deschisă este dacă P ⊂ NP sau nu
•Arătând că problemele sunt NP-complete
O problemă este NP-completă dacă este în NP ș i este la fel de „dificilă” ca orice problemă din NP.

Dacă orice problemă NP-completă poate fi rezolvată în timp polinomial, atunci fiecare problemă NP-completă are un polinom.
algoritm de timp
–Analiza ț i un algoritm pentru a arăta cât de greu este (în loc de cât de u ș or este)
–Arată că este pu ț in probabil să existe un algoritm eficient pentru problemă
Ca designer, dacă po ț i arăta că o problemă este NP-completă, oferi dovada pentru imposibilitatea rezolvării acesteia.
Po ț i să- ț i petreci timpul dezvoltând un algoritm de aproxima ț ie în loc să cau ț i un algoritm rapid care
poate rezolva problema exact
–Dovada în termeni de Ω(n)

•Probleme de decizie vs probleme de optimizare

Definiț ia 1 Orice problemă pentru care răspunsul este fie zero, fie unul se numeș te problemă de decizie. Un algoritm pentru o
O problemă de decizie este denumită algoritm de decizie.

Definiț ia 2 Orice problemă care implică identificarea unei valori optime (fie minime, fie maxime) a unui dat
Funcț ia de cost este cunoscută sub numele de problemă de optimizare. Un algoritm de optimizare este utilizat pentru a rezolva o problemă de optimizare.
Probleme NP-Dificile ș i NP-Complete 3

Probleme de optimizare
Fiecare solu ț ie fezabilă are o valoare asociată; scopul este de a găsi o solu ț ie fezabilă cu cea mai bună valoare.
∗ Problemaceluimaiscurtdrum
·Având un graf neorientat G ș i vârfurile u ș i v
Găse ș te un drum de la utov care folose ș te cele mai pu ț ine muchii
Problema drumului cel mai scurt între două noduri într-un graf neorientat, neponderat
–Probleme de decizie
∗ Problema oferă un răspuns ca „da” sau „nu”
Problema decizională este presupusă a fi mai u ș or (sau nu mai greu) de rezolvat comparativ cu problema de optimizare.
Problema decizională poate fi rezolvată în timp polinomial dacă ș i numai dacă problema de optimizare corespunzătoare poate.
Dacă problema de decizie nu poate fi rezolvată în timp polinomial, problema de optimizare nu poate fi rezolvată.
în timp polinomial fie
- Probleme NP-complete restrânse la domeniul problemelor de decizie
Transforma ț i oproblemă de optimizare într-o problemă decizională similară impunând o limită asupra valorii care trebuie optimizată.
∗ Problema PATH în raport cu problema CEL MAI SCURT DRUM
Dat fiind un graf orientat G, vârfurile u ș i v ș i un întreg k, există o cale de la u la v cu cel mult k
margini?
Rela ț ia între o problemă de optimizare ș i problema sa de decizie asociată
Încerca ț i să arăta ț i că problema de optimizare este „dificilă”
·Sau că problema decizională este „mai u ș oară” sau „nu este mai dificilă”
Putea să rezolvămPARCURSO prin rezolvarea CELUI MAI SCURT DRUM ș i apoi comparând numărul de muchii cuk
Dacă o problemă de optimizare este u ș oară, atunci problema decizională este, de asemenea, u ș oară.

ÎnNP-completitudinea, dacă putem oferi dovezi că o problemă de decizie este dificilă, putem de asemenea oferi
dovezi că problema de optimizare asociată este dificilă
Reduceri
∗ Arătând că o problemă nu este mai greu sau mai u ș or decât alta se aplică, de asemenea, atunci când ambele probleme sunt
probleme de decizie
∗ Demonstrarea NP-completitudinii – pa ș i generali
·Considera ț i o problemă de decizie A; ne-ar plăcea să o rezolvăm în timp polinomial
·Instan ț ă: input pentru o anumită problemă; de exemplu, înPATH, o instanț ă este un grafic particularG, doi
variabile particulare ș i un întreg particular k
Să presupunem că ș tim cum să rezolvăm o problemă de decizie diferită în timp polynomial.
·Presupunem că avem o procedură care transformă orice instan ț ă α a lui A într-o anumită instan ț ă β a lui B cu
următoarele caracteristici:
Transformarea durează timp polinomial
Ambele răspunsuri sunt aceleaș i; răspunsul pentru α este un "da" dacă ș i numai dacă răspunsul pentru β este un "da"

Procedura de mai sus se nume ș te algoritm de reducere a timpului polinomial ș i ne oferă o modalitate de a rezolva problema.
Ain timp polinomial
1. Dat fiind o instanț ă α a lui A, foloseș te un algoritm de reducere în timp polinomial pentru a o transforma într-o instanț ă β a lui B.
2. Rulează algoritmul de decizie în timp polinomial pentru instan ț a β
3. Folose ș te răspunsul pentru β ca răspuns pentru α

∗ Folosind reduceri de timp polinomial pentru a arăta că nu poate exista un algoritm de timp polinomial pentru o problemă particulară
B
Să presupunem că avem o problemă de decizie A pentru care ș tim deja că nu există un algoritm de timp polinomial care să
există
Să presupunem că avem o reducere în timp polinomial care transformă instan ț e ale A în instan ț e ale B
Dovadă simplă că nu poate exista un algoritm în timp polinomial pentru B
Probleme NP-dificile ș i NP-complete 4

Algoritmi nedeterministi
Algoritmi deterministici
Algoritmi cu rezultate definite univoc
∗ Previzibil în termenii rezultatului pentru un anumit input
Algoritmii non-deterministici sunt permisi să con ț ină opera ț ii al căror rezultat este limitat la un set dat de posibilită ț i.
abilităț ile în loc să fie definite în mod unic
–Specificat cu ajutorul a trei noi func ț ii O(1)
1. alegere (S)
Alege în mod arbitrar unul dintre elementele mul ț imii S
∗ x = choice(1,n) poate rezulta înxfi asignat oricărui dintre întregii din intervalul[1, n], într-un mod complet
mod aleatoriu
∗ Nicio regulă care să specifice cum trebuie făcută această alegere
2.e ș ec()
∗ Semnalează finalizarea nereu ș ită a unui calcul
∗ Nu poate fi folosit ca valoare de returnare
[Link] ș it()
∗ Semnalează finalizarea cu succes a unei calcule
∗ Nu poate fi utilizat ca o valoare de retur
Dacă există un set de alegeri care duc la o finalizare reu ș ită, atunci trebuie să se facă o alegere din acest set.
- Un algoritm nedeterministic se încheie fără succes dacă ș i numai dacă nu există niciun set de alegeri care să conducă la un semnal de succes.
O ma ș ină capabilă să execute un algoritm nedeterminist, a ș a cum s-a men ț ionat mai sus, se nume ș te ma ș ină nedeterministă.
Căutare nedeterministă a x într-un array neordonat A cu n≥1 elemente
∗ Determinaț i un index j astfel încât A[j] = xor j=−1 dacă x ∈ A

algoritm nd_search ( A, n, x )
{
Căutare non-deterministă
A: Array care trebuie căutat
n: Numărul de elemente din A
Element de căutat
Returnează -1 dacă elementul nu există, altfel returnează indexul elementului.

int j = alegere ( 0, n-1 );

dacă ( A[j] == x )
{
cout << j;
success();
}
cout << -1;
eşec();
}
Conform defini ț iei algoritmului non-determinist, ie ș irea este -1 dacă ș i numai dacă nu există un j astfel încât A[j] = x
∗ Pentru că A nu este ordonat, fiecare algoritm de căutare determinist este de complexitate Ω(n), în timp ce căutarea non-deterministă
Algoritmul istoric are complexitatea O(1)
Algoritm de sortare non-determinist
// Sortează n numere întregi pozitive în ordine non-descrescătoare

algoritm nd_sort ( A, n )
{
Probleme NP-Dure ș i NP-Complet 5

// Ini ț ializaț i B[]; B este folosit pentru comoditate

// Este ini ț ializat la 0, de ș i orice valoare care nu se află în A[] va fi suficientă

pentru ( i = 0; i < n; B[i++] = 0; );

pentru ( i = 0; i < n; i++ )
{
j = alegere ( 0, n - 1 );

// Asigura ț i-vă că B[j] nu a fost folosit deja

dacă ( B[j] != 0 ) e ș uează();

B[j] = A[i];
}

// Verifica ț i comanda

pentru ( i = 0; i < n-1; i++ )

dacă ( B[i] > B[i+1] ) e ș ec();

scrie ( B );
succes();
}
–Complexitatea nd_sort este Θ(n)

Cel mai cunoscut algoritm de sortare deterministă are o complexitate de Ω(nlgn)

–Interpretarea deterministă a algoritmului nedeterminist
∗ Posibil prin permiterea paralelismului nelimitat în calcul
Imaginează- ț i să faci copii ale instan ț ei de căutare de mai sus, toate rulând în paralel ș i căutând în indici diferi ț i.
valori pentru x
Prima copie care ajunge la success() terminează toate celelalte copii
Dacă o copie ajunge la failure(), doar acea copie este întreruptă
În termeni abstracti, o ma ș ină nedeterministă are capacitatea de a recunoa ș te solu ț ia corectă dintr-un set de
alegeri permise, fără a face copii ale programului

•Posibilitatea de a construi algoritmi nedeterministici pentru multe secven ț e diferite de alegeri care duc la finalizări de succes
(sortare_seend)

Dacă numerele din A nu sunt unice, multe permutări diferite vor duce la o secven ț ă sortată.
Ne vom limita la probleme care rezultă într-o ie ș ire unică sau algoritmi de decizie
Un algoritm de decizie va returna 0 sau 1
∗ Implicit în signalssuccess() ș i failure()
–Ie ș irea dintr-un algoritm de decizie este definită unic prin parametrii de intrare ș i specifica ț ia algoritmului

O problemă de optimizare poate avea multe solu ț ii viabile

Problema este să găsim solu ț ia fezabilă cu cea mai bună valoare asociată.
NP-completitudinea se aplică direct nu problemelor de optimizare, ci problemelor de decizie

•Exemplu: Cliqă maximală

Un clic este un subgrafic complet maximal al unui graf G = (V, E)
Dimensiunea unei clique este numărul de vârfuri din ea
Problema clikelor maxime este o problemă de optimizare care trebuie să determine dimensiunea celei mai mari clici în G
Probleme NP-Dificile ș i NP-Complet 6

Problema decizională corespunzătoare este de a determina dacă G are o cli ș eu de dimensiune de cel pu ț in k pentru un anumit k.

Să denotăm algoritmul decizional determinist pentru problema decizională a clique-ului ca dclique(G, k)

Dacă |V|=n, dimensiunea unei clique maxime poate fi găsită prin

pentru ( k = n; dclique ( G, k ) != 1; k-- );

–Dacă complexitatea temporală a dclique este f(n), dimensiunea cluqei maxime poate fi găsită în timp g(n)≤nf(n)

Problema de decizie poate fi rezolvată în timp g(n)

Problema cliqei maxime poate fi rezolvată în timp polinomial dacă ș i numai dacă problema decizională a cliqei poate fi rezolvată în timp polinomial
timpul meu

Exemplu: rucsac 0/1

Există o atribu ț ie de valori 0/1 pentru x?eu ,1≤i≤n, astfel încât peu xPeu≥randweu xi≤m,Ppentru datm ș i r,
şi nonnegativeuandweu
Dacă problema decizională a rucsacului nu poate fi rezolvată în timp polinomial determinist, atunci problema de optimizare
nu poate nici
•Comentariu cu privire la parametrul uniform pentru a măsura complexitatea

-n ∈ N este lungimea inputului pentru algoritm sau dimensiunea inputului

∗ Toate intrările sunt considerate a fi întregi

∗ Intrările ra ț ionale pot fi specificate prin perechi de întregi
–nis exprimat în reprezentare binară
*n = 1010este exprimat ca n= 10102cu lungimea 4
∗ Lungimea unui număr întreg pozitiv k10este dat de blog2kc+ 1biti
∗ Lungime de 02este 1
Lungimea datelor de intrare pentru un algoritm este suma lungimilor numerelor individuale introduse.
∗ Lungimea inputului în radixrfork10este dat de blogrkc+ 1
∗ Lungimea de 10010islog10100 + 1 = 3
∗ Găsirea lungimii oricărui input folosind radixr >1
·jurnalrk = log2k/log2r

·Lungimea este dată de c(r)n unde n este lungimea folosind reprezentarea binară ș i c(r) este un număr fixat pentru r
–Intrarea în radix 1 este în formă unară

∗ 510= 111111
∗ Lungimea unui număr întreg pozitiv kisk
Lungimea unui input unar este în mod exponen ț ial legată de lungimea inputului corespunzător r-ar, pentru radix r, r > 1

•Cliqua maximă, din nou

Inputul poate fi furnizat ca o secven ț ă de muchii ș i un număr întreg k
Fiecare muchie din E(G) este o pereche de vârfuri, reprezentată prin numere (i, j)
Dimensiunea intrării pentru fiecare muchie (i, j) în reprezentare binară este blog2ic+blog2jc+ 2
Dimensiunea de intrare a oricărei instan ț e este

n= X (blog2ic+blog2jc+ 2) +blog 2kc+ 1

(i, j)∈E(G)
i<j
kis este numărul care indică dimensiunea clique-ului

Dacă G are doar o componentă conexă, atunci n ≥ |V|

Probleme NP-Dificile ș i NP-Complete 7

Dacă această problemă decizională nu poate fi rezolvată de un algoritm de complexitate p(n) pentru un anumit polinom p(), atunci ea
nu poate fi rezolvat printr-un algoritm de complexitate p(|V|)

rucsacul 0/1
Dimensiunea de intrare q (q > n) pentru problema decizională a rucsacului este

q= X (blog2peu c+blog2weu c) + 2n+blog2mc+blog2rc+ 2

1≤i≤n

Dacă inputul este dat în nota ț ie unară, atunci dimensiunile inputuluipeu

= +weu+m+r
P P
Problemele de decizie ș i optimizare ale rucsacului pot fi rezolvate în timp p(s) pentru un anumit polinomial p() (dinamic pro-
algoritm de programare
–Cu toate acestea, nu există niciun algoritm cunoscut cu complexitate O(p(n)) pentru un anumit polinomial p()

Definiț ia 3 Timpul necesar unui algoritm nedeterminist care funcț ionează pe un anumit input este numărul minim
de paș i necesari pentru a ajunge la o finalizare de succes dacă există o succesiune de alegeri care duce la o astfel de finalizare. În
în cazul în care finalizarea cu succes nu este posibilă, atunci timpul necesar este O(1). Un algoritm nedeterminist este de complexitate
O(f(n)) dacă pentru toate intrările de dimensiune n, n ≥ n0 , care rezultă într-o finalizare cu succes, timpul necesar este de cel mult cf(n) pentru
câteva constante0 .

Defini ț ia de mai sus presupune că fiecare pas de calcul are un cost fix.
∗ Garantat de finitul fiecărui cuvânt în calculatoarele orientate pe cuvinte
Dacă un pas nu este de cost fix, este necesar să se ia în considerare costul instruc ț iunilor individuale

Adunarea numerelor de m bi ț i durează O(m) timp

Înmul ț irea numerelor cu două bi ț i durează O(m)2 )timp
–Considera ț i algoritmul de decizie determinist pentru a ob ț ine suma submul ț imilor

algoritm suma_submul ț imilor ( A, n, m )

{
A este un array de întregi
n este dimensiunea array-ului
m oferă indexul celor mai mari bi ț i din cuvânt

1 // s este un cuvânt de m+1 bi ț i

// bitul 0 este întotdeauna 1
pentru i = 1 până la n
s |= ( s << A[i] ) // muta ț i s la stânga cu A[i] bi ț i

dacă bitul m în s este 1

Un subset se adună la m
altfel
Niciun subset nu se adună la m
}
∗ Biț ii sunt numerota ț i de la 0 la m de la dreapta la stânga
∗ Biti va fi 0 dacă ș i numai dacă nu există subseturi aleA[j],1≤j≤nsuma la i
∗ Bit 0 este întotdeauna 1 iar bi ț ii sunt numerota ț i 0,1,2, . . . , m de la dreapta la stânga

Numărul de pa ș i pentru acest algoritm este O(n)

Fiecare pas mută m + 1 bi ț i de date ș i ar dura O(m) timp pe un computer conven ț ional
Presupunând o unitate de timp pentru fiecare opera ț ie de bază pentru o dimensiune fixă a cuvântului, complexitatea deterministă
algoritmul este O(nm)

Problema decizională a rucsacului

Probleme NP-Dificile ș i NP-Complet 8

Algoritm non-deterministic de timp polinomial pentru problema rucsacului

algoritm nd_knapsack ( p, w, n, m, r, x )
{
p: Tabără pentru a indica profitul pentru fiecare element
w: Array pentru a indica greutatea fiecărui articol
n: Numărul de articole
m: Capacitatea totală a rucsacului
r: Profitul a ș teptat din rucsac
x: Afi ș ează dacă elementul corespunzător este purtat sau nu

W = 0;
P = 0;
pentru ( i = 1; i <= n; i++ )
{
x[i] = alegere ( 0, 1 );
W += x[i] * w[i];
P += x[i] * p[i];
}

dacă ( ( W > m ) || ( P < r ) )

eș ec();
altfel
succes();
}
–Bucla for selectează sau respinge fiecare dintre cele then items

De asemenea, recalculează greutatea totală ș i profitul corespunzător selec ț iei.

Instruc ț iunea if verifică fezabilitatea atribuirii ș i dacă profitul este deasupra unei limite inferioare.
Complexitatea temporală a algoritmului este O(n)
Dacă lungimea de intrare este q în binar, complexitatea timpului este O(q)

Cliqa maximală
–Algoritm nedeterminist pentru problema decizională a clusterei
Începe prin a încerca să formezi un set de k vârfuri distincte
–Test pentru a vedea dacă formează un subgraf complet

Satisfiabilitate
–Lasă 1 , x2 , . . .denote un set de variabile boolean
eu x ̄ complementul lui xeu
Să notăm
O variabilă sau complementul său se nume ș te aliteral
O formulă în calculul propozi ț iilor este o expresie care este construită prin conectarea literelor folosind opera ț iile
și
–Exemple de formule în calculul propozi ț iilor
∗ (x1∧x2 )∨(x3∧x¯ ) 4

∗ (x3∨x¯ )∧(x
4
1∨x¯ )
2
–Forma normală conjunctivă ( CNF)
k
∗ O formulă este înCNFiff este reprezentat ca ∧eu=1ceueusunt clauze reprezentate ca ∨leuj ;lijsunt literale
Forma normală disjunctivăDNF)
k
O formulă este înDNFiff este reprezentat ca ∨eu=1ceu , undeeusunt clauze reprezentate ca ∧lij
Probleme NP-Dificile ș i NP-Complet 9

Problema satisfiabilită ț ii este de a determina dacă o formulă este adevărată pentru o anumită alocare de valori de adevăr variabilelor.

∗ Satisfiabilitatea CNF este problema satisfiabilităț ii pentru formulele CNF

–Algoritm nedeterminist de timp polinomial care se termină cu succes dacă ș i numai dacă o formulă propozi ț ională dată E(x) 1 , . . . , x n )
este satisfăcător

∗ Alege nedeterminist o unul dintre cele douănposibile atribuiri de valori de adevăr pentru (x1 , . . . , x n )
∗ Verificaț i că E(x1 , . . . , x n este adevărat pentru acea sarcină
algoritm eval ( E, n )
{
// Determină dacă formula propozi ț ională E este satisfăcătoare.
// Variabilele sunt x1, x2, ..., xn

Alege o atribuire a valorii de adevăr

pentru ( i = 1; i <= n; i++ )

alege ( adevărat, fals );

dacă ( E ( x1, ..., xn ) )

succes();
altfel
eș ec();
}
Timpul nedeterminist pentru a alege valoarea de adevăr este O(n)
Evaluarea determinantă a atribu ț iei este, de asemenea, realizată în timp O(n)

Clasele NP-difícile ș i NP-complete

-Complexitate polinomială
Un algoritm A are complexitate polinomială dacă există un polinom p() astfel încât timpul de calcul al
AisO(p(n))pentru fiecare intrare de dimensiune n

Definiț ia 4 P este setul tuturor problemelor de decizie care pot fi rezolvate de algoritmi deterministici în timp polinomial. NP este
mulț imea tuturor problemelor de decizie care pot fi rezolvate de algoritmi nedeterministici în timp polinomial.

–Deoarece algoritmii deterministici sunt un caz special al algoritmilor nedeterministici, P ⊆ NP

O problemă nerezolvată în ș tiinț a calculatoarelor este: Este P=NPe sau P=NP?

Cook a formulat următoarea întrebare: Există vreo problemă unică în NP astfel încât dacă am demonstra că este în P,
atunci ar implica că P=NP? Aceasta a dus la teorema lui Cook astfel:
Teorema 1: Satisfiabilitatea este în P dacă ș i numai dacă P = NP.

•Reducibilitate
–Arată că o problemă nu este mai greu de rezolvat sau mai u ș or de rezolvat decât alta, chiar ș i atunci când ambele probleme sunt probleme de decizie.

Definiț ia 5 Să fie A ș i B probleme. Problema A se reduce la B (scris ca A∝B) dacă ș i numai dacă există o modalitate de a
rezolvaAprintr-un algoritm determinist de timp polinomial folosind un algoritm determinist care rezolvăBin polinomial
timp.
Dacă avem un algoritm de timp polinomial pentru B, atunci putem rezolva A în timp polinomial
Reducibilitatea este tranziitivă
·A ∝B∧B∝C⇒A∝C
Definiț ia 6 Având două mulț imi A ș i B ∈ N ș i o mulț ime de funcț ii F: N → N, închisă sub compunere, A este
se numeș te reducibil la B (A∝B) dacă ș i numai dacă

∃f∈F| ∀x∈N, x∈A⇔f(x)∈B

Probleme NP-Dificile ș i NP-Complet 10

–Procedura se nume ș te algoritm de reducere polinomială ș i ne oferă o modalitate de a rezolva problema A în

timp polinomial
De asemenea cunoscut sub numele de reducere Turing

Dată o instan ț ă α a lui A, folose ș te un algoritm de reducere în timp polinomial pentru a o transforma într-o instan ț ă β a lui B
Rulează algoritmul de decizie în timp polinomial pe instan ț a β a B
∗ Foloseș te răspunsul lui β ca răspuns pentru α
Reducerea de la pătrundere la înmul ț ire
Tot ce ș tim este să adunăm, să scădem ș i să calculăm pătratele
Produsul a două numere este calculat prin

2×a×b= (a+b)2−a2−b2
·Reducerea în cealaltă direc ț ie: dacă putem înmul ț i două numere, putem ridica un număr la pătrat
∗ Calculând(x + 1)2de la2
Pentru eficien ț ă, dorim să evităm înmul ț irea
Reduc ț iile Turing calculează solu ț ia pentru o problemă, presupunând că cealaltă problemă este u ș or de rezolvat
Reducere polinomială de tip multe-unu
Transformă instan ț ele unei probleme de decizie A în instan ț e ale unei probleme de decizie B
∗ Scris caA≤mB;A este reducibil la B în mod unic.
∗ Dacă avem un algoritm N care rezolvă instan ț ele lui B, putem să-l folosim pentru a rezolva instan ț ele lui A în
Timpul necesar pentru N plus timpul necesar pentru reducere
·Spa ț iul maxim necesar pentru N ș i spa ț iul necesar pentru reducere
Formal, să presupunem că A ș i B sunt limbi formale peste alfabetele Σ ș i Γ
O reducere mul ț i-la-unu de la A la B este o func ț ie computabilă totală f: Σ ∗ →Γ∗ cu proprietatea

ω∈A⇔f(ω)∈B,∀ω∈Σ∗
Dacă există un astfel de A, acesta este reducibil la B printr-o mapare unu-la-mul ț i.

O clasă de limbi C este închisă sub reducerea unu-la-multe dacă nu există nicio reducere de la o limbă într-o altă limbă.
Cto o limbă din afaraC
Dacă o clasă este închisă sub reducerea multe-la-unu, atunci reducerea multe-la-unu poate fi folosită pentru a arăta că o
problema este înCprin reducerea unei probleme înCla aceasta

·Fie S ⊂P(N)(mulț imea puterilor numerelor naturale), iar ≤ să fie o reducere, atunci S se nume ș te închis sub ≤ dacă

∀s∈S∀A∈N A ≤S⇔A∈S
Cele mai bine studiate clase de complexitate sunt închise sub un anumit tip de reducere mul ț i-la-unu, inclusiv P.
ș iNP
∗ Pătratul pentru reducerea înmul ț irii, din nou
Adăuga ț i restric ț ia că putem folosi func ț ia pătrată o singură dată ș i doar la final.
Chiar dacă ni se permite să folosim toate opera ț iile aritmetice de bază, inclusiv înmul ț irea, fără reducere
√ 2 din numere raț ionale
exista în general, deoarece s-ar putea să fie nevoie să calculăm un număr iraț ional precum
Mergând în direc ț ia opusă, totu ș i, cu siguran ț ă putem ridica un număr la pătrat cu o singură înmul ț ire.
la sfârș it
Folosind această formă limitată de reducere, am arătat rezultatul nesurprinzător că multiplicarea este mai dificilă în
general decât pătratul
Reducerile multe-unei mapează instan ț ele unei probleme pe instan ț ele unei alte probleme
Reducerea mul ț i-la-unul este mai slabă decât reducerea Turing
Reduc ț iile mai slabe sunt mai eficiente în separarea problemelor, dar au mai pu ț ină putere, făcând reduc ț iile
mai greu de conceput
Foloseste reduceri în timp polinomial într-un mod opus pentru a arăta că o problemă este NP-completă
Probleme NP-Dificile ș i NP-Complete 11

∗ Folosiț i reducerea în timp polinomial pentru a demonstra că nu poate exista un algoritm în timp polinomial pentru problema B
∗ A⊂N se nume ș te greu pentru S dacă

∀s∈S s ≤A
A⊂N se numeș te complet pentru S dacă A este greu pentru S ș i A este în S

Dovadă prin contradic ț ie

Presupune ț i că o problemă cunoscută A este dificil de rezolvat

·Având o nouă problemă B, similară cu A

Presupune ț i că B este solu ț ionabil în timp polinomial
·Arată că fiecare instan ț ă a problemei A poate fi rezolvată în timp polinomial prin reducerea la problema B
Contradic ț ie
–Nu se poate presupune că nu există absolut niciun algoritm în timp polinomial pentru A

Definiț ie 7 O problemă A este NP-greu dacă ș i numai dacă satisfiabilitatea se reduce la A (satisfiabilitate ∝ A). O problemă A este

N P - c o m p l e t d a c ă ș i n u m a i d a c ă A e s t e N P - d i f i c i l ș i A ∈ N P.
Există probleme NP-dificile care nu sunt NP-complete.
Numai o problemă de decizie poate fi NP-completă
O problemă de optimizare poate fi NP-grea; nu poate fi NP-completă
Dacă A este o problemă de decizie ș i B este o problemă de optimizare, este destul de posibil ca A ∝B

Problema decizională a rucsacului poate fi redusă la problema de optimizare a rucsacului

Problema decizională a cli ș eului se reduce la problema de optimizare a cli ș eului
Există unele probleme de decizie NP-dure care nu sunt NP-complete.
Exemplu: Problema opririi pentru algoritmi deterministici
problemă de decizie NP-hard, dar nu NP-completă
∗ Determinaț i pentru un algoritm determinist arbitrar A ș i un input I, dacă A cu input I se termină vreodată.
Este bine cunoscut că problema opririi este indecidabilă; nu există niciun algoritm de nicio complexitate pentru a rezolva problema opririi.
problemă
Cu siguran ț ă nu poate fi în NP
∗ Pentru a arăta că "satisfiabilitatea ∝ problema opririi", construie ș te un algoritm A a cărui intrare este o formulă propozi ț ională.
X
Dacă X are n variabile, A încearcă toate cele 2natribuirile posibile de adevăr ș i verifică dacă X este satisfăcător
Dacă X este satisfiabil, se opre ș te; în caz contrar, A intră într-o buclă infinită
Prin urmare, Ahalts pe intrarea XiffX este satisfăcătoare.

Dacă am avea un algoritm de timp polinomial pentru problema opririi, atunci am putea rezolva problema satisfiabilită ț ii în
timp polinomial folosind A ș i X ca intrare pentru algoritmul pentru problema opritului
Astfel, problema opririi este o problemă NP-greu care nu face parte din NP

Definiț ia 8 Două probleme A ș i B sunt considerate echivalente polinomial dacă ș i numai dacă A ∝ B ș i B ∝ A.

- Pentru a arăta că o problemă B este NP-greu, este adecvat să se arate că A ∝ B, unde A este o problemă deja cunoscută.
a fi NP-dificil
–Deoarece ∝ este o rela ț ie tranzitivă, rezultă că dacă satisfac ț ia ∝ A ș i A ∝ B, atunci satisfac ț ia ∝ B
Pentru a arăta că o problemă de decizie NP-dificilă este NP-completă, trebuie doar să prezentăm un algoritm nondeterminist în timp polinomial.
algoritm minimistic pentru acesta

Timp polinomial

Problemele care pot fi rezolvate în timp polinomial sunt considerate probleme tratabile
Probleme NP-Difficile ș i NP-Complete 12

1. Considera ț i o problemă care este rezolvată în timp O(n)100

Este timp polinomial, dar pare a fi intractabil

În practică, există pu ț ine probleme care necesită un polinom de un grad atât de înalt.
2. Pentru multe modele rezonabile de calcul, o problemă care poate fi rezolvată în timp polinomial într-un model poate fi
rezolvat în timp polinomial în altă parte
3. Clasa problemelor rezolvabile în timp polinomial are proprietă ț i de închidere plăcute
Polinoamele sunt închise sub adunare, înmul ț ire ș i compunere
–Dacă ie ș irea unui algoritm de timp polinomial este folosită ca intrare pentru altul, algoritmul compus este
polinomial