NP problemă completă

Problemă NP-completă - în teoria algoritmilor , o problemă cu răspunsul „da” sau „nu” din clasa NP , la care orice altă problemă din această clasă poate fi redusă în timp polinomial (adică folosind operații al căror număr nu depășește un polinom în funcție de dimensiunea datelor originale). Astfel, problemele NP-complete formează, într-un anumit sens, un subset de probleme „tipice” din clasa NP: dacă pentru unele dintre ele se găsește un algoritm de rezolvare „polinomial rapid”, atunci orice altă problemă din clasa NP poate fi rezolvată. la fel de „repede””.

Definiție formală

Un alfabet este orice set finit de caractere (de exemplu, {} sau {}). Setul tuturor cuvintelor posibile ( șiruri finalecompuse din caracterele acestui alfabet) peste un anumit alfabeteste notat. O limbă peste un alfabeteste orice subset al setului, adică. ${0,1}$ ${a,b,c}$ $\Sigma$ $\Sigma ^{*}$ $L$ $\Sigma$ $\Sigma ^{*}$ $L\subset \Sigma ^{*}$

Sarcina recunoașterii unei limbi este de a determina dacă un anumit cuvânt aparține limbii . $L$ $L$

Să fie și două limbi peste alfabet . Se spune că un limbaj este reductibil (după Karp) la o limbă dacă există o funcție , , care este calculabilă în timp polinomial și are următoarea proprietate: $L_{1}$ $L_{2}$ $\Sigma$ $L_{1}$ $L_{2}$ $f\colon \Sigma ^{*}\to \Sigma ^{*}$

$x\în L_{1}$ dacă și numai dacă . Reductibilitatea Karp este notată ca sau . $f(x)\în L_{2}$ $L_{1}{\leq }_{p}L_{2}$ $L_{1}\varpropto L_{2}$

Se spune că o limbă este NP-hard dacă orice limbă din clasa NP este reductibilă la ea. Se spune că un limbaj este NP-complet dacă este NP-hard și este el însuși în clasa NP. $L_{2}$

Informal vorbind, faptul că problema se reduce la problemă înseamnă că problema „nu este mai dificilă” decât problema (pentru că dacă putem rezolva , atunci putem rezolva și ). Astfel, clasa de probleme NP-hard include probleme NP-complete și probleme care sunt „mai grele” decât ele (adică acele probleme la care pot fi reduse problemele NP-complete). Clasa NP include probleme NP-complete și probleme care sunt „mai ușoare” decât acestea (adică acele probleme care sunt reduse la probleme NP-complete). $A$ $B$ $A$ $B$ $B$ $A$

Din definiție rezultă că dacă se găsește un algoritm care rezolvă o (orice) problemă NP-completă în timp polinomial, atunci toate NP-problemele vor fi în clasa P , adică vor fi rezolvate în timp polinomial.

NP-complet în sens tare

O sarcină se numește NP-completă în sensul puternic dacă are o sarcină secundară care:

nu este o problemă cu parametrii numerici (adică valoarea maximă a cantităților întâlnite în această problemă este mărginită de sus de un polinom în lungimea intrării)
este NP-complet.

Clasa de astfel de probleme se numește NPCS . Dacă ipoteza P ≠ NP este adevărată, atunci nu există un algoritm pseudopolinom pentru problema NPCS .

Ipoteza P ≠ NP

Problema coincidenței claselor P și NP a fost una dintre problemele centrale deschise de mai bine de treizeci de ani . Comunitatea științifică tinde să dea un răspuns negativ la această întrebare [1] — în acest caz, nu va fi posibilă rezolvarea problemelor NP-complete în timp polinomial.

Exemple de probleme NP-complete

Vezi și

Egalitatea claselor P și NP

Note

↑ William I. Gasarch. Sondajul P=?NP. (neopr.) // Stiri SIGACT. - 2002. - T. 33 , nr 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris este greu, chiar de aproximativ . imprimare.

Literatură

Gary M., Johnson D. Computing machines and hard problems Arhivat 4 noiembrie 2019 la Wayback Machine . M.: Mir, 1982.
Thomas H. Kormen et al., Capitolul 34. NP-Completeness // Algoritmi: Construcție și Analiză = Introducere în algoritmi. - Ed. a II-a. - M . : „Williams” , 2006. - 1296 p. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M . : „Williams” , 2002. - 528 p. - ISBN 0-201-44124-1 .

Link -uri

Completitudinea NP
Computational Complexity of Games and Puzzles Arhivat 6 decembrie 2006 la Wayback Machine
Un compendiu de probleme de optimizare NP. Editori - Pierluigi Crescenzi, Viggo Kann Arhivat 5 decembrie 2006 la Wayback Machine

Clasele de complexitate ale algoritmilor
Considerată ușoară	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-complet ZPP RP BPP BQP EQP APX
Ar trebui să fie dificil	U.P. NP NP complet co-NP co-NP-complet AM M.A._ QMA PH ⊕P PP #P #P IP PSPACE PSPACE-complete
Considerat dificil	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTAR R PR RE RE-completare Co-RE Co-RE-complete TOATE

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă