první věc, kterou musíte pochopit, je, že P a NP klasifikovat jazyky, ne problémy. Abychom pochopili, co to znamená, potřebujeme nejprve nějaké další definice.
abeceda je neprázdná konečná množina symbolů.
{01} je abeceda jako je znaková sada ASCII. {} není abeceda, protože je prázdná. N (celá čísla) není abeceda, protože není konečná.
Nechť Σ je abeceda. Uspořádaná zřetězení konečného počtu symbolů z Σ se nazývá slovo nad Σ.
string 101 je slovo nad abecedou {01}. Prázdné slovo (často psané jako ε) je slovo nad jakoukoli abecedou. Řetězec penguin je slovo nad abecedou obsahující znaky ASCII. Desetinné notace pro číslo π není slovo nad abecedou {.0123456789} protože to není konečný.
délka slova w, psaný jako |w|, je počet symbolů v ní.
například, |hello| = 5 a |ε| = 0. Pro jakékoli slovo w | / w / ∈ N a proto konečné.
Nechť Σ je abeceda. Množina Σ＊ obsahuje všechna slova nad Σ, včetně ε. Množina Σ + obsahuje všechna slova lomeno Σ, kromě ε. Pro n ∈ N, Σn je soubor slov délky n.
Pro každou abecedu Σ, Σ * v a Σ+ jsou nekonečné spočetné množiny. Pro znakové sady ASCII ΣASCII, regulární výrazy .*.+ označují ΣASCII 锛 a ΣASCII+, resp.
{01}7 je sada 7-bit ASCII kódy {00000000000001111111101} 32 je sada 32 bitových celočíselných hodnot.
Σ být abeceda a L ⊆ Σ 锛. L se nazývá jazyk nad Σ.
pro abecedu Σ jsou prázdné množiny a Σ＊ triviální jazyky nad Σ. První je často označován jako prázdný jazyk. Prázdný jazyk {} a jazyk obsahující pouze prázdné slovo {ε} se liší.
podmnožinu {01}32, která odpovídá non-NaN IEEE 754 floating point hodnot je konečný jazyk.
jazyky mohou mít nekonečný počet slov, ale každý jazyk je počítatelný. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Nekonečnou množinu řetězců {23571113, …}, které udává hlavní čísla v desítkové notaci je vlastní podmnožina této smlouvy. Jazyk, obsahující všechna slova odpovídající regulární výraz ?\d+\.\d*(?\d+)? je jazyk nad znakové sady ASCII (označující podskupinu platné plovoucí desetinnou čárkou výrazy definované programovací jazyk C).
Neexistuje žádný jazyk, obsahující všechna reálná čísla (v každém zápisu), protože množina reálných čísel není spočetná.
Σ být abeceda a L ⊆ Σ 锛. Stroj D se rozhodne, L, pokud pro každý vstup w &v; Σ * je vypočítá charakteristické funkce xL(w) v konečném čase. Charakteristická funkce je definována jako
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.Takový stroj se nazývá rozhodčí pro L. Budeme psát „D(w) = x“ pro „vzhledem k tomu, w, D výstupy x“.
existuje mnoho modelů strojů. Nejobecnější, který je dnes v praktickém použití, je model Turingova stroje. Turingův stroj má neomezené lineární úložiště seskupené do buněk. Každá buňka může obsahovat přesně jeden symbol abecedy v každém okamžiku. Turingův stroj provádí svůj výpočet jako posloupnost výpočetních kroků. V každém kroku může číst jednu buňku, případně přepsat její hodnotu a přesunout čtecí / zapisovací hlavu o jednu pozici do levé nebo pravé buňky. Jaká akce bude stroj provádět, je řízena konečným stavovým automatem.
random access machine s omezenou sadu instrukcí a neomezené úložiště je další model stroje, který je stejně silné jako Turingův stroj model.
v zájmu této diskuze, se neobtěžoval nás s precizní stroj model používáme, ale spíše stačí, když řeknu, že stroj má konečný deterministický řídící jednotka, neomezené ukládání a provádí výpočty jako posloupnost kroků, které mohou být počítány.
vzhledem k tomu, že jste ji použili ve své otázce, předpokládám, že jste již obeznámeni s notací „big-O“, takže zde je pouze rychlé obnovení.
Nechť f: n → být funkcí. Množina O(f) obsahuje všechny funkce g: N → N, pro které existují konstanty n0 ∈ N a c ∈ N takové, že pro každé n ∈ N, n > n0 je pravda, že g(n) ≤ c f(n).
nyní jsme připraveni přistoupit ke skutečné otázce.
třída P obsahuje všechny jazyky L, pro které existuje Turingův stroj D, který rozhoduje L a konstanta k ∈ N taková, že pro každý vstup w, D se zastaví po maximálně T(|w|) kroků pro funkci T ∈ O(n ↦ nk).
Od O(n ↦ nk), zatímco matematicky správné, je nevhodné číst a psát, většina lidí – chcete-li být upřímný, všichni kromě mě – obvykle píše jednoduše O(nk).
na Vědomí, že je povinen, závisí na délce w. Proto argument pro jazyk prvočísel je opravit pouze pro čísla v unaray kódování, kde pro kódování w řady n, délka kódování |w| je úměrná n. Nikdo by se nikdy používat takové kódování v praxi. Pomocí pokročilejšího algoritmu, než jen zkoušet všechny možné faktory, však lze ukázat, že jazyk prvočísel zůstává v P, pokud jsou vstupy kódovány v binárním (nebo na jakékoli jiné základně). (Navzdory masivní zájem, že to může být pouze prokázáno Manindra Agrawal, Neeraj Kayal a Nitin Saxena v oceněné papíru v roce 2004, takže můžete hádat, že tento algoritmus je velmi jednoduchý.)
triviální jazyky {} a Σ＊ a netriviální jazyk {ε} jsou zjevně v P (pro libovolnou abecedu Σ). Můžete psát funkce ve vaší oblíbené programovací jazyk, který vezme řetězec jako vstup a vrátí boolean říct, zda řetězec je slovo z jazyka pro každou z nich, a dokázat, že vaše funkce je polynom run-time složitosti?
Každý regulární jazyk (jazyk popsaný regulárním výrazem) je v P.
Σ být abeceda a L ⊆ Σ 锛. Stroj V zakódované n-tice dvou slov w, c ∈ Σ * v a výstupy 0 nebo 1 po konečném počtu kroků je ověřovatel pro L, pokud to má následující vlastnosti.
- daný (w, c), V výstupy 1 pouze pokud w ∈ L.
- pro každé w ∈ L existuje c Σ Σ＊ takové, že V (w, c) = 1.
c ve výše uvedené definici se nazývá svědek (nebo certifikát).
ověřovatel může dát falešné negativy pro nesprávného svědka, i když w je ve skutečnosti v L. není však dovoleno dávat falešné pozitivy. Je také nutné, aby pro každé slovo v jazyce existoval alespoň jeden svědek.
pro jazykový kompozit, který obsahuje desetinná kódování všech celých čísel, která nejsou prvočísla, může být svědek faktorizací. Například (659, 709) je svědkem pro 467231 COMPOSITE COMPOSITE . Můžete snadno ověřit, že na list papíru, zatímco bez svědka vzhledem, dokázat, že 467231 není prime by bylo obtížné bez použití počítače.
neřekli jsme nic o tom, jak lze najít vhodného svědka. Toto je nedeterministická část.
třída NP obsahuje všechny jazyky L, pro které existuje Turingův stroj V, který ověřuje L a konstanta k ∈ N taková, že pro každý vstup (w, c), V. zastaví po maximálně T(|w|) kroků pro funkci T ∈ O(n ↦ nk).
Všimněte si, že výše uvedená definice znamená, že pro každý w ∈ L existuje svědek c S |c| ≤ T (/w|). (Turingův stroj se nemůže dívat na více symbolů svědka.)
NP je nadmnožina P (proč?). Není známo, zda existují jazyky, které jsou v NP, ale ne v p.
celočíselná faktorizace není jazyk sám o sobě. Můžeme však vytvořit jazyk, který představuje problém s rozhodováním, který je s ním spojen. To znamená, že jazyk, který obsahuje všechny n-tice (n, m) takové, že n má faktor d S D ≤ m. nazývejme tento jazykový faktor. Máte-li algoritmus rozhodnout faktor, může být použit k výpočtu plné faktorizace pouze s polynomiální režií provedením rekurzivního binárního vyhledávání pro každý prvočíselný faktor.
je snadné ukázat, že faktor je v NP. Vhodným svědkem by byl jednoduše samotný faktor d a vše, co by ověřovatel musel udělat, je ověřit, že d & leq; m a n mod d = 0. To vše lze provést v polynomiálním čase. (Nezapomeňte znovu, že se počítá délka kódování, která je logaritmická v n.)
Pokud můžete ukázat, že faktor je také v P, můžete si být jisti, že získáte mnoho skvělých ocenění. (A vy jste zlomili podstatnou část dnešní kryptografie.)
pro každý jazyk v NP existuje algoritmus hrubé síly, který o něm rozhoduje deterministicky. Jednoduše provádí vyčerpávající vyhledávání všech svědků. (Všimněte si, že maximální délka svědka je ohraničena polynomem.) Takže váš algoritmus pro rozhodování prvočísel byl ve skutečnosti algoritmus hrubé síly pro rozhodování složeného.
abychom vyřešili vaši poslední otázku, musíme zavést redukci. Redukce jsou velmi silným konceptem teoretické informatiky. Redukce jednoho problému na jiný v podstatě znamená řešení jednoho problému řešením jiného problému.
Nechť Σ je abeceda a A A B jsou jazyky lomeno Σ. A je polynom-čas mnoho-jeden redukovatelné na B, pokud existuje funkce f: Σ * v → Σ * s následující vlastností.
- w A A ⇔ f (w ) B B pro všechny w Σ Σ＊.
- funkci f lze vypočítat Turingovým strojem pro každý vstup w v počtu kroků ohraničených polynomem v / w|.
V tomto případě píšeme A ≤p B.
například, nech To být jazyk, který obsahuje všechny grafy (kódovány jako sousednosti), které obsahují trojúhelník. (Trojúhelník je cyklus délky 3.) Nechť dále B je jazyk, který obsahuje všechny matice s nenulovou stopou. (Stopa matice je součtem jejích hlavních diagonálních prvků.), Pak je polynom-čas mnoho-jeden redukovatelné na B. Abychom to dokázali, musíme nalézt vhodné transformace funkce f. V tomto případě můžeme nastavit f pro výpočet 3. moc sousednosti. To vyžaduje dva maticové maticové produkty, z nichž každá má polynomiální složitost.
je triviálně pravda, že L ≤p L. (můžete to dokázat formálně?)
použijeme to nyní na NP.
jazyk L je NP-těžký, pokud a pouze v případě, L‘ ≤p L pro každý jazyk L ∈ NP.
jazyk NP-hard může nebo nemusí být v NP samotném.
jazyk L je NP-úplný, pokud a pouze pokud
- L ∈ NP a
- L je NP-těžké.
nejznámějším NP-kompletním jazykem je SAT. Obsahuje všechny booleovské vzorce, které mohou být splněny. Například (A ∨ b) ∧ (a ∨ b) SAT SAT. Platným svědkem je {a = 1, b = 0}. Vzorec (a ∨ b) ∧ (a ∨ b) SAT b SAT SAT. (Jak byste to dokázal?)
není těžké ukázat, že SAT ∈ NP. Ukázat NP-tvrdost SAT je nějaká práce, ale to bylo provedeno v roce 1971 Stephen Cook.
jakmile byl znám jeden NP-úplný jazyk, bylo relativně jednoduché ukázat NP-úplnost jiných jazyků pomocí redukce. Je-li známo, že jazyk a je NP-tvrdý, pak ukazuje, že a ≤p B ukazuje, že B je také NP-tvrdý (přes přechodnost „≤p“). V roce 1972 Richard Karp publikoval seznam 21 jazyků, které dokázal ukázat jako NP-kompletní prostřednictvím (tranzitivní) redukce SAT. (Toto je jediný článek v této odpovědi, který ve skutečnosti doporučuji, abyste si přečetli. Na rozdíl od ostatních, to není těžké pochopit, a dává velmi dobrou představu o tom, jak prokazování NP-úplnost prostřednictvím redukce funguje.)
konečně krátké shrnutí. Symboly NPH a NPC použijeme k označení tříd jazyků NP-hard a NP-complete.
- P ⊆ NP
- NPC &podmnožina; NP a NPC &podmnožina, NPH, vlastně NPC = NP ∩ NPH podle definice
- (A ∈ NP) ∧ (B ∈ NPH) ⇒ A ≤p B
Upozorňujeme, že zařazení NPC ⊂ NP je správné i v případě, že P = NP. Chcete-li to vidět, ujasněte si, že žádný netriviální jazyk nelze redukovat na triviální a v NP existují triviální jazyky v P i netriviální jazyky. To je ale (nepříliš zajímavý) rohový případ.
primární zdroj zmatku se zdá být, že jsi myslel „n“ v „O(n ↦ f(n))“ jako výklad algoritmu, vstup, když se to vlastně vztahuje k délce vstupu. To je důležitý rozdíl, protože to znamená, že asymptotická složitost algoritmu závisí na kódování používá pro vstup.
Tento týden byl dosažen nový rekord pro největší známý Mersenne prime. Největší v současné době známé prvočíslo je 274 207 281 − 1. Toto číslo je tak obrovské, že mi dává bolesti hlavy, takže v následujícím příkladu použiji menší: 231 – 1 = 2 147 483 647. Může být kódován různými způsoby.
- jeho Mersenne exponent jako desetinné číslo:
31(2 bajty) - jako desetinné číslo:
2147483647(10 bajtů) - jako unární číslo:
11111…11…má být nahrazen 2 147 483 640 více1s (téměř 2 GiB)
Všechny tyto řetězce kódují stejný počet a vzhledem k tomu některý z nich, můžeme snadno sestrojit nějaké jiné kódování stejné číslo. (Desetinné kódování můžete nahradit binárním, osmičkovým nebo hexadecimálním, pokud chcete. Mění pouze délku konstantním faktorem.)
naivní algoritmus pro testování primality je pouze polynom pro unární kódování. Test AKS primality je polynom pro desetinnou čárku (nebo jakoukoli jinou základnu b ≥ 2). Lucas-Lehmer primality test je nejlepší známý algoritmus pro Mersenne prvočísla Mp s p liché prvočíslo, ale je to stále exponenciální v délce binární kódování Mersenne exponent p (polynomiální v p).
Pokud chceme mluvit o složitosti algoritmu, je velmi důležité, abychom byli velmi jasní, jakou reprezentaci používáme. Obecně lze předpokládat, že se používá nejúčinnější kódování. To znamená binární pro celá čísla. (Všimněte si, že ne každé prvočíslo je Mersenne prvočíslo, takže použití Mersenne exponentu není obecné schéma kódování.)
v teoretické kryptografii je mnoha algoritmům formálně předán zcela zbytečný řetězec k 1s jako první parametr. Algoritmus se na tento parametr nikdy nedívá, ale umožňuje, aby byl formálně polynomiální v k, což je bezpečnostní parametr používaný k vyladění bezpečnosti procedury.
u některých problémů, pro které je rozhodovací jazyk v binárním kódování NP-complete, není rozhodovací jazyk již NP-complete, pokud je kódování vložených čísel přepnuto na unary. Rozhodnutie o ďalších problémoch je stále NP-úplné. Ty se nazývají silně NP-kompletní. Nejznámějším příkladem je bin balení.
je také (a možná i více) zajímavé sledovat, jak se složitost algoritmu mění, pokud je vstup komprimován. Na příkladu prvočísel Mersenne jsme viděli tři kódování, z nichž každé je logaritmicky komprimovanější než jeho předchůdce.
V roce 1983, Hana Galperin a Avi Wigderson napsal zajímavý článek o složitosti běžné grafové algoritmy, pokud je vstupní kódování grafu je stlačený logaritmicky. U těchto vstupů se jazyk grafů obsahujících trojúhelník shora (kde byl jasně v P) náhle stává NP-úplným.
a to proto, že jazykové třídy jako P a NP jsou definovány pro jazyky, nikoli pro problémy.