A když se mě na to u státnic zeptají, tak jim to tak řeknu, protože já se omáčku kolem toho, co nedává smysl, šrotit nehodlám
Uff, šíleně to motáš. Tvé "definice" založené na tom, zda musíme projít všechny možnosti, jsou spíše zavádějící. Docela by mne zajímalo, zda má ten předmět někde slidy, abychom se mohli podívat, co je důvodem tvého zmatení. Být tebou, držel bych se toho, co ti tu napsali lidé přede mnou.
Můžeme to zkusit vzít postupně, soustřeďme se nyní pouze na
rozhodovací problémy - tedy takové, pro které existuje odpověď ano/ne.
Máme dva výpočetní modely:
1. (Deterministický) Turingův stroj (TS) - ten má svůj stav, vstupní pásku a nějaké pracovní pásky (nad kterými se pohybují hlavy). Přechodová funkce na základě stavu stroje a symbolů pod hlavami definuje
pokračování, tj. nový stav stroje, co se má zapsat na pracovní pásky a kam se mají pohnout hlavy (doleva, doprava, nikam). Výsledek je
ano, pokud stroj skončí v přijímacím stavu. Pokud skončí v jiném stavu (anebo se zacyklí) výsledek je
ne.
2. Nedeterministický Turingův stroj (NTS) - Ten je stejný jako TS, ale přechodová funkce vrací množinu možných pokračování (a ne jen jedno jako u TS). Jak psal JSH, představ si to pro zjednodušení klidně tak, že NTS má navíc orákulum, které NTS řekne, které z těchto možných pokračování vybrat (aby se nejrychleji dostal k výsledku).
Problémy P jsou pak takové, které TS vyřeší v polynomiálním čase (TS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.
Problémy NP jsou pak takové, které NTS vyřeší v polynomiálním čase (NTS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.
Z toho plyne, že problém, který je P, je zároveň NP, protože na TS se klidně můžeš dívat jako na takový degenerovaný NTS, ve kterém přechodová funkce všude vrací jednoprvkové (či prázdné) množiny možných pokračování.
To, zda každý problém, který je v NP, je také v P, se neví. Předpokládá se (a doufá se), že tomu tak není, tj. že existují problémy, které jsou NP, ale nejsou P.
Tak a teď co to je NP-těžký problém: Problém X je NP-těžký, pokud
každý problém Y, který je NP, lze (v polynomiálním čase) převést na řešení problému X.
Možná ti může dělat trochu problém, že v definici je psáno, že na něj musí být převoditelný
každý NP problém. V praxi se využívá toho, že pokud o problému Z víš, že je NP-těžký, a pokud umíš problém Z (v polynomiálním čase) převést na řešení problému W, pak W je také NP-těžký. To je dáno tím, že pokud ti někdo dá libovolný problém Y (z NP), tak ten lze (protože o Z víš, že je NP-těžký) převést na Z, který už umíš převést na W - tedy celkově umíš každý problém Y (z NP) převést na W.
Pozor na to, že problémy, které jsou NP-těžké, nemusí být řešitelné v polynomiálním čase na NTS. Tedy NP-těžké problémy nemusí být NP!
Kvůli tomu je zde závěrečná definici: NP-úplné jsou takové problémy, které jsou NP-těžké a zároveň jsou NP. Jak zde už někdo psal, NP-úplné problémy jsou z ty
nejtěžší z NP, protože každý problém z NP lze na ně (v polynomiálním čase) převést.
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.