21 de probleme ale NP-Karp complete
În teoria complexității de calcul , problemele Karp cu 21 NP-complete sunt un set de probleme de calcul care apar NP-complete . În 1972 lucrarea sa, reductibilitate Printre problemele combinatorie, [1] Richard Karp folosit Stephen Cook a lui 1971 teorema că problema satisfiabilitate booleană este NP-completă [2] ( de asemenea , numit teorema Gatiti-Levin ) , pentru a arăta că există o many- reducerea la unu a timpului polinomial de la problema de satisfacție booleană la fiecare dintre cele 21 de probleme de calcul din combinatorică și teoria graficelor , arătând astfel că toate sunt NP-complete . Aceasta a fost una dintre primele demonstrații că multe probleme de calcul naturale care apar în întreaga informatică sunt computerizate de neconceput . Această demonstrație a atras interesul pentru studiul completitudinii NP și pentru cercetările din jurul celebrei probleme P = NP .
Probleme
În timp ce apartenența SAT sau problema de satisfacție booleană la clasa problemelor NP-complete a fost dovedită folosind mecanisme particulare, apartenența următoarelor 21 de probleme a fost dovedită prin reduceri polinomiale . Astfel, problema SAT a fost redusă polinomial la problemele 0-1 INTEGER PROGRAMMING, CLIQUE și 3-SAT, iar acestea la rândul lor au fost reduse la altele diferite. Lista completă este cea prezentată mai jos. Indentele denotă faptul că NP-completitudinea problemei a fost dovedită prin reducerea sa polinomială la nivelul direct superior. Rețineți că numele problemelor sunt scrise cu majuscule și corespund abrevierilor numelui în limba engleză, ca de obicei; alături de ele, între paranteze, este scrisă traducerea numelui în italiană.
- SAT ( problemă de satisfacție booleană , pentru formule în formă normală conjunctivă )
- 0-1 PROGRAMARE INTEGRĂ ( Problemă de programare liniară întregi )
- CLIC ( Problema clicii, vezi și Problema setului independent )
- AMBALARE septembrie ( se rezolvă problema ambalării )
- VERTEX COVER (Vertex Coverage Problem )
- Acoperirea setului ( emisiunea de acoperire )
- FEEDBACK NODE SET (sau set de vârf de feedback) ( set Problemă de vârfuri de feedback )
- SET DE ARC DE FEEDBACK ( Problemă cu setul de arce în feedback )
- CIRCUIT Hamiltonian DIRECT ( problema circuitului Hamiltonian regizat )
- CIRCUIT Hamiltonian nedirectat ( problema circuitului hamiltonian nu este directă )
- 3-SAT ( problemă de satisfacție booleană cu 3 litere per clauză )
- NUMĂR CROMATIC ( Problemă de colorare a graficului )
- CLIQUE COVER ( Problemă de acoperire a fisurilor)
- EXACT COVER ( Exact Cover Problem )
- HITTING SET ( Problema setului de intersecție )
- STEINER TREE ( copac Steiner )
- MATCHING 3-DIMENSIONAL ( problemă de cuplare tridimensională )
- KNAPSACK ( problema rucsacului )
- SECVENȚAREA POSTULUI ( Problema secvențelor de lucru )
- PARTITION ( Problema partiției )
- MAX-CUT ( Problemă maximă de tăiere )
- NUMĂR CROMATIC ( Problemă de colorare a graficului )
De-a lungul timpului s-a descoperit că multe dintre aceste probleme ar putea fi rezolvate eficient dacă afirmația lor ar fi limitată la anumite cazuri particulare sau ar putea fi rezolvate aproximativ într-un anumit procent din rezultatul optim. Cu toate acestea, David Zuckerman a demonstrat în 1996 că fiecare dintre aceste 21 de probleme are o versiune limitată de optimizare care este imposibil de aproximat în cadrul oricărui factor constant, cu excepția cazului în care P = NP, arătând că abordarea de reducere, propusă de Karp, generalizează la o specificație de reducere de tip prin apropiere. [3] Rețineți că acest lucru poate fi diferit de versiunile normale de optimizare a problemelor, care pot avea algoritmi de aproximare (ca în cazul tăierii maxime).
Notă
Bibliografie
- Stephen Cook , The Complexity of Theorem Proving Procedures , în Proceedings of al treilea simpozion anual ACM on Theory of computing , 1971, pp. 151–158.
- Richard M. Karp , Reducibility Among Combinatorial Problems ( PDF ), în RE Miller și JW Thatcher (ed.), Complexity of Computer Computations , New York, Plenum, 1972, pp. 85-103.
- David Zuckerman, Despre versiuni neaproximabile ale problemelor NP-complete , în Jurnalul SIAM pe calcul , vol. 25, nr. 6, 1996, pp. 1293-1304, DOI : 10.1137 / S0097539794266407 .
