Důkaz NP-úplnosti problému splnitelnosti logického obvodu vycházel z polynomiálního převedení každého NP problému na tento problém. Ukážeme, jak můžeme dokázat NP-úplnost problému bez explicitního převedení každého NP problému.
Tvrzení 1
Je-li problém T takový, že pro některý NP-úplný problém S je S ≤ P T, potom problém T je NP-těžký. Je-li k tomu T Î NP, potom T je NP-úplný.
Pro každý S’ Î NP je S’ ≤ P S. Z předpokladu S ≤ P T tedy je i S’ ≤ P T a T je NP-těžký. Jinými slovy, převedením známého NP-úplného problému S na T Î NP, jsme implicitně převedli každý NP-problém na T.
Metoda důkazu, že problém T je NP-úplný má potom následující kroky.
1. Dokažte, že T Î NP.
2. Vyberte známý NP-úplný problém S.
3. Opište algoritmus pro výpočet funkce f zobrazující, každou instanci
x problému S na instanci f(x) problému T.
4. Dokažte, že S(x) = 1 právě tehdy, když T(f(x)) = 1.
5. Dokažte, že algoritmus počítající f je časově polynomiální.
Uvedené kroky si ilustrujeme na důkazu, že problém obchodního cestujícího (TSP) je NP-úplný, je-li známo, že problém existence hamiltonovské kružnice (HK) je NP-úplný.
Problém obchodního cestujícího v jeho rozhodovací verzi má následující tvar.
Nechť G = (V, H) je úplný graf a náklady na cestu z vrcholu i do vrcholu j jsou dány funkcí c:VxV →R. Existuje v G cesta obchodního cestujícího, který navštíví každý vrchol právě jednou, skončí ve výchozím vrcholu a náklady jsou nejvíce kÎR? Instance problému obchodního cestujícího je tedy trojice (G, c ,k).
Napřed ukážeme, že TSP patří do NP. Je-li zadána instance problému a certifikát, verifikační algoritmus ověří, že certifikát obsahuje každý vrchol právě jednou, sečte náklady a ověří jsou-li nejvíce k, což může být jistě vykonáno v polynomiálním čase.
Dále ukážeme, že HK ≤ P TSP. Nechť G = (V, H) je instance HK. Instanci TSP sestrojíme následovně. Vytvoříme úplný graf G´ = (V, H´), H´={ (i,j):i,jÎH a i≠ j } a definujeme nákladovou funkci
c(i,j) = 0 je-li (i,j ) Î H
= 1 není-li (i,j ) Î H
Instance TSP pak je (G´,c, 0), kterou lehce vytvoříme v polynomiálním čase. Ukážeme, že graf G má hamiltonovskou kružnici právě tehdy má-li graf G´cestu s náklady nejvíce 0.
Nechť G má hamiltonovský cyklus h. Každá hrana v h je prvkem H, má tedy v G´ náklady 0 a h je cesta v G´s náklady 0. Opačně, nechť graf G´ má cestu h´ s náklady nejvíce 0. Potom každá hrana v h´ má náklady 0 a h´ obsahuje pouze hrany z H, tedy h´ je hamiltonovským cyklem v grafu G.
Zjistíme-li, že řešený problém je NP-úplný, je hledání časově polynomiálního algoritmu pravděpodobně mrháním času.
Je možno sáhnout k jiným přístupům:
aproximační
pravděpodobnostní
řešení speciálních případů
heuristické
Jedním z NP-úplných problémů je tzv. 15 rébus.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
Nalezení nejkratší posloupnosti tahů, pomocí kterých ze zadané permutace (pokud je to možné), získáme uvedené uspořádání je NP-úplný problém. Heuristické řešení se snaží z možných tahů vybrat nejslibnější. Může tak udělat ohodnocením „vzdálenosti“ nové konfigurace vzniklé tahem od cílové.
Označme souřadnice každého políčka i = 1, 2, …, 15 v cílové konfiguraci cxi a cyi. Například cx7 = 3 a cy7 = 2. Pokud v nějaké konfiguraci má i souřadnice xi a yi, potom její vzdálenost od pozice v cílovém stavu můžeme vyjádřit vztahem
(cxi - xi )2 + (cyi - yi )2
Vzdálenost konfigurace od cílové potom můžeme vyjádřit jejich součtem pro všechna i. Cílového stavu dosáhneme, bude-li tento součet nulový. Heuristický algoritmus potom principiálně pracuje tak, že pro možné tahy na prázdné políčko (2 až 4 možnosti) vybere tu novou konfiguraci, pro kterou je uvedený součet nejmenší.