Budeme se zabývat třídou problémů, které se nazývají NP-úplné. Jsou to problémy třídy NP, přičemž jsou tak těžké jako jakýkoliv problém v NP. Zatím bez důkazu si řekněme, že může-li být jakýkoliv NP-úplný problém vyřešen v polynomiálním čase, potom P = NP. V současnosti pro žádný z asi 1000 známých NP-úplných problémů nikdo nenašel polynomiální algoritmus, čehož důsledkem by bylo P = NP. Na druhé straně nikdo nedokázal neexistenci časově polynomiálního algoritmu pro řešení některého z nich, což by znamenalo P ≠ NP.
Nejenom, že pro NP-úplné problémy můžeme správnost poskytnutého řešení ověřit v polynomiálním čase, ale je udivující, že často jsou formulovány velice podobně jako problémy mající časově polynomiální algoritmus. Jako příklad si uveďme rozhodovací problémy pro eulerovský a hamiltonovský graf.
Eulerovský graf. Určete, jestli v neorientovaném grafu G(V, H) existuje uzavřený tah (hrany se neopakují) obsahující všechny hrany, tj. mající délku │H│.
Hamiltonovský graf. Určete, jestli v neorientovaném grafu G(V, H) existuje uzavřená cesta (vrcholy se neopakují, kromě prvního a posledního) - kružnice délky │V│, tj. procházející všemi vrcholy.
Pro první z uvedených problémů umíme takový tah najít, pokud existuje, v čase O(H). Umíme tedy i rozhodovací problém řešit v polynomiálním (lineárním) čase. Patří tedy do třídy P.
Druhý problém patří do třídy NP. Certifikátem je permutace vrcholů tvořících hamiltonovskou kružnici. Řekne-li někdo, že graf je hamiltonovský a jako certifikát nám poskytne posloupnost vrcholů v1, v2, ..., v│V│, potom ověříme, je-li permutací vrcholů grafu a je-li (vi , vi+1)Î H , pro i = 1,2, ..., │V│-1 a také (v│V│, v1)Î H . To je určitě možné v polynomiálním čase a tedy tento problém patří do třídy NP. Nalézt řešení a tím také rozhodnout uvedený problém by bylo možno prověřováním všech permutací. Je-li problém zakódován například maticí sousednosti, potom počet vrcholů m je Ω(√n), kde n =│G│ je velikost zakódování grafu G. Protože je m! permutací, čas výpočtu bude Ω(m!) = Ω(√n!), což není O(nk), pro žádnou konstantu k. Tento problém je ve skutečnosti NP - úplný.
Uvažujme dva rozhodovací problémy S a T. Umíme-li každou instanci x problému S převést na instanci f(x) problému T tak, že řešení problému S pro x je stejné jako řešení problému T pro f(x) říkáme, že problém S je převeditelný na problém T. Znamená to, že problém S není těžší než T. Metoda převedení problému S na problém T je znázorněna na obr.
. AT je algoritmus řešení problému T, F je algoritmus výpočtu funkce f a AS je vytvořený algoritmus řešení problému S. Šipkami jsou vyznačeny vstupy a výstupy algoritmů. Obecně podobně jako v článku 11.2 můžeme libovolný vstup, instanci problému jakož i výstup, řešení problému vyjádřit z jejich kódu jako přirozené číslo, tedy f: N ® N.
Například problém výpočtu objemu válce je převeditelný na problém výpočtu objemu trubice. Objem trubice s vnějším poloměrem r1, vnitřním poloměrem r2 a výškou v je pv(r12 - r22). Objem válce o poloměru r a výšce h potom převedeme na problém výpočtu objemu trubice pro r1=r, r2=0, v =h.
Vraťme se k rozhodovacím problémům. Říkáme, že problém S je polynomiálně převeditelný na problém T, psáno S ≤ P T, existuje-li polynomiální algoritmus F pro výpočet funkce f: N ® N takové, že pro každé xÎ N je S(x) = 1 právě tehdy, když T(f(x)) = 1.
Polynomiální převeditelnost problémů nám umožňuje dokázat, že problémy patří do P.
Tvrzení 1
Jsou-li S a T problémy takové, že S ≤ P T, potom TÎ P implikuje SÎ P.
Konstrukce časově polynomiálního algoritmu pro problém S pomocí polynomiálního algoritmu F a algoritmu AT plyne z obr., protože čas výpočtu algoritmu AS je dán součtem časů výpočtu algoritmů F a AT, které jsou oba polynomiální.
NP-úplné problémy jsou nejtěžší problémy v NP.
Problém T je NP-úplný, když
1. TÎNP a
2. Pro každý problém S Î NP je S ≤ P T.
Jestliže problém splňuje vlastnost 2, ale ne nevyhnutně vlastnost 1, říkáme, že je NP-těžký.
NP-úplnost je klíčová pro rozhodnutí zda je P = NP.
Tvrzení 2
Je-li T NP-úplný a TÎ P, potom P = NP.
Pro každý problém S ÎNP, podle druhé vlastnosti NP-úplných problémů, máme S ≤ P T. Protože T Î P, z tvrzení 1 plyne, že každý S Î P a tedy P = NP .
Tvrzení 2 můžeme ekvivalentně vyjádřit následovně.
Existuje-li v NP problém, který není řešitelný časově polynomiálně, potom žádný NP-úplný problém není řešitelný v čase polynomiálně.
Tvrzení 2 můžeme verbálně přeformulovat takto:
Existuje-li NP-úplný problém, který je časově polynomiálně řešitelný, potom každý NP problém je časově polynomiálně řešitelný.
Použitím tautologie
na přeformulované tvrzení 2 dostáváme přímo jeho ekvivalentní vyjádření.
Vzhledem k úsilí, jenž je věnováno řešení stovek NP-úplných problémů, aniž by pro některý z nich byla dokázána existence časově polynomiálního algoritmu, převládá názor, že P ∩ NP-úplné = f a
P ≠ NP jak znázorňuje obr.
.