V zásadě máte pravdu o P a NP, ale ne o NP-tvrdém a NP-úplném.

Pro začátečníky jsou zde velmi stručné definice dotyčných čtyř tříd složitosti:

• P je třída rozhodovacích problémů, které lze vyřešit v polynomiálním čase deterministickým Turingovým strojem.

• NP je třída rozhodovacích problémů, které lze vyřešit v polynomiálním čase nedeterministickým Turingovým strojem. Rovněž je to třída problémů, které lze ověřit v polynomiálním čase deterministickým Turingovým strojem.

• NP-hard je třída rozhodovacích problémů, na kterou lze všechny problémy v NP redukován na v polynomiálním čase deterministickým Turingovým strojem.

• NP-Complete je průsečík NP-hard a NP. Ekvivalentně je NP-Complete třída rozhodovacích problémů v NP, na kterou lze všechny ostatní problémy v NP v polynomiálním čase redukovat pomocí deterministického Turingova stroje.

A zde „sa Eulerův diagram z Wikipedie zobrazující vztahy mezi těmito čtyřmi třídami (za předpokladu, že P se nerovná NP):

Část, o které se domnívám, že vám není nejznámější nebo nejasná je pojem „redukce polynomiálního času“ z problému X na problém Y. Redukce z X na Y je jednoduše algoritmus A, který řeší X využitím nějakého jiného algoritmu B, který řeší problém Y. Tato redukce se nazývá „ polynomiální redukce času „pokud všechny části A jiné než B mají polynomiální časovou složitost. Jako triviální příklad lze uvést, že problém s nalezením nejmenšího prvku v poli je v konstantním čase redukovatelný na problém řazení, protože pole můžete seřadit a vrátit první prvek seřazeného pole.

Jeden to, co je na NP-tvrdé definici snadné přehlédnout, je, že redukce přechází od NP problémů k NP-tvrdým problémům, ale ne nutně naopak . To znamená, že NP-tvrdé problémy mohou být v NP nebo v mnohem vyšší třídě složitosti (jak vidíte z Eulerova diagramu), nebo to nemusí být ani rozhodující problémy.Proto lidé při pokusu o neformální vysvětlení často říkají něco jako „NP-hard znamená přinejmenším stejně tvrdý jako NP“.

Problém zastavení je dobrým příkladem NP-hard problému, který „s jasně není v NP, jak vysvětluje Wikipedia :

Je snadné prokázat, že problém se zastavením je NP-tvrdý, ale není NP-úplný. Například problém s Booleovskou uspokojivostí lze snížit na problém se zastavením jeho transformací na popis Turingova stroje, který zkouší všechna přiřazení hodnot pravdy, a když najde takový, který splňuje vzorec, zastaví se a jinak se dostane do nekonečné smyčky. Je také snadné vidět, že problém zastavení není v NP, protože všechny problémy v NP jsou rozhodnutelné v konečném počtu operací, zatímco problém zastavení je obecně nerozhodnutelný.

Komentáře

• @Nakano Intuitivně se ‚ sa “ redukce “ v tom smyslu, že jeden problém se stává dílčím problémem jiného problému. Skutečnost, že některá z těchto redukcí zvyšují složitost, místo aby ji snižovala díky špatnému výběru “ subproblem “ jednoduše znamená, že byste tyto redukce nikdy nepoužili v jakémkoli kódu skutečného světa. Ačkoli abych byl upřímný, NP-hard mi připadá jako divná a ne strašně zajímavá třída; může být plodnější to ignorovat a přemýšlet o NP-complete jako o souboru problémů NP, na které se všechny ostatní problémy NP snižují.
• @Nakano stackoverflow.com/questions/12637582/… Věřím, že krátká odpověď je, že když lidé mluví o tom, že celočíselná faktorizace je NP, ‚ běžně mluví o opravdu obrovských celých číslech, pro která obvykle začínáte dělat své big-O důkazy s n jako “ počet bitů, které celé číslo zabírá v paměti “ místo “ počtu celých čísel, která jste předali do funkce „.
• @Nakano: Ve značce big-O je n měřítkem velikosti vstupu (počet prvků, bajtů, číslic atd.), Nikoli hodnoty vstup.
• @Nakano Krátká odpověď je, že jste ‚ v pořádku, a proto při práci s časem mplexity analaysis vždy musíte určit, co n znamená . Tvrzení, že n má “ velikost vstupu „, je pouze stručným shrnutím toho, jak se běžně rozhodneme definovat n. Není to ‚ součástí přísných definic notace big-O nebo časové složitosti. Věřím, že máte pravdu, když řeknete, že celočíselná faktorizace je O (sqrt (n)), když n je hodnota vstupu. Stává se, že výsledky složitosti, kde n znamená velikost, jsou v praxi obvykle mnohem užitečnější než ty, kde n znamená hodnotu.
• @Nakano It ‚ Mějte také na paměti, že technicky musíte také definovat časovou složitost svých primitivních operací (přidání, multitplikace, čtení z paměti, zápis do paměti, porovnání dvou čísel). Většinu času buď předpokládáme, že všechny tyto primitivy jsou konstantní, nebo počítáme pouze jeden druh operace (např. Pro třídicí algoritmy tradičně počítáme srovnání). Mám podezření, že výsledky celočíselné faktorizace nepředpokládají, že všechny tyto operace jsou konstantní v čase, jako obvykle, jinak by velikost čísla nebyla ‚ na tom velmi záleží.

Celočíselná faktorizace bude uvedena jako příklad NP, ale osobně nerozumím, proč to není P, protože zkušební faktorizace zabere čas O (sqrt (n)).

Pro účely tříd složitosti je n délka vstupu. Pokud tedy chcete zohlednit celé číslo k, n není k, ale log k, počet bitů (nebo jakýchkoli), které jsou potřeba k zapsání tohoto počtu. Takže celočíselná faktorizace je O(sqrt(k)) jak říkáte, ale toto je O(sqrt(2n)) což je O(2(n/2)).

NP-Hard Předpokládám, že je plný neznámých. Těžko ověřitelné, těžko řešitelné.

Ne. NP-Hard je pouze o tom, jak těžké je problém vyřešit.

NP-Hard problémy jsou přinejmenším těžké jako nejtěžší problém v NP. Víme, že jsou přinejmenším tak těžké, protože kdybychom měli pro problém NP-Hard algoritmus polynomiálního času, mohli bychom tento algoritmus přizpůsobit jakémukoli problému v NP.

NP-Complete Nerozumím vůbec

NP- Kompletní znamená, že problém je jak NP, tak NP-Hard. Znamená to, že můžeme ověřit řešení rychle (NP), ale je přinejmenším stejně těžké jako nejtěžší problém v NP (NP-Hard).

Opravdu nevím, co to znamená, aby to nebylo deterministické.

Ne -determinismus je alternativní definice NP. Nedeterministický turingův stroj je schopen efektivně se kdykoli duplikovat a každý duplikát má jinou cestu provedení. Podle této definice je NP sada problémů, které lze vyřešit v polynomiálním čase počítačem, než se mohou volně duplikovat. Ukázalo se, že se jedná o přesně stejnou sadu problémů, kterou lze ověřit v polynomiálním čase.

Komentáře

• Takže je možné pro $ O ( n ^ k) $ časové algoritmy jako NP problémy?
• k je konstantní reálné číslo? Ano. Všechny P problémy jsou také NP problémy. Je zřejmé, že vše, co můžete vyřešit v polynomiálním čase, lze také ověřit v polynomiálním čase.
• Jak je zde vlastně definována délka / velikost? Například jsem mohl napsat jen $ n $ do velké základny a zmenšit její délku, když jsem ji psal. A co problémy, které ‚ t výslovně neřeší celá čísla, ale říkají grafy s vrcholy $ V $ a hranami $ E $ atd.
• @Nakano, ve skutečnosti velká základna by ji ‚ t nezměnila, protože by šlo pouze o konstantní rozdíl faktorů. ‚ by to tedy neovlivnilo polynomiální vs. nepolynomiální. Pokud byste však číslo napsali unárně, pak by se to změnilo.
• @Nakano, hmm … Neodvážil bych se ‚ pokusit se vysvětlit složitost třídy do pěti let. : P

Nejprve je třeba pochopit, ž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á sada symbolů.

{0 , 1} je abeceda stejně jako znaková sada ASCII. {} není abeceda, protože je prázdná. N (celá čísla) není abeceda, protože není konečná.

Nechť Σ být abeceda. Uspořádané zřetězení konečného počtu symbolů z Σ se nazývá slovo přes Σ .

Řetězec 101 je slovo v abecedě {0, 1}. Prázdné slovo (často psané jako ε ) je slovo nad jakoukoli abecedou. Řetězec penguin je slovo nad abecedou obsahující znaky ASCII. Desetinná notace čísla π není slovo nad abecedou {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} protože to není konečné.

délka slova w , napsaného jako | w |, je počet symbolů v něm.

Například | hello | = 5 a | ε | = 0. Pro jakékoli slovo w , | w | ∈ N a tedy konečné.

Nechť Σ být abeceda. Sada Σ ^＊ obsahuje všechna slova nad Σ , včetně ε . Sada Σ ⁺ obsahuje všechna slova nad Σ , kromě ε . Pro n ∈ N , Σ ⁿ je sada slov o délce n .

Pro každá abeceda Σ , Σ ^＊ a Σ ⁺ jsou nekonečné spočítatelné sady .Pro znakovou sadu ASCII Σ _ASCII jsou regulární výrazy .* a .+ označuje Σ _ASCII ^＊ a Σ _ASCII ⁺ .

{0, 1} ⁷ je sada 7bitových kódů ASCII {0000000, 0000001,…, 1111111}. {0, 1} ³² je sada 32bitových celočíselných hodnot.

Nechť Σ být abeceda a L ⊆ Σ ^＊ . L se nazývá jazyk nad Σ .

U abecedy Σ je prázdná sada a Σ ^＊ jsou triviální jazyky nad Σ . První z nich je často označován jako prázdný jazyk . Prázdný jazyk {} a jazyk obsahující pouze prázdné slovo { ε } se liší.

Podmnožina {0, 1} ³² , který odpovídá hodnotám pohyblivé řádové čárky jiných než NaN IEEE 754, je konečný jazyk.

Jazyky mohou mít nekonečný počet slov, ale každý jazyk je počítatelný. Sada řetězců {1, 2,…} označujících celá čísla v desítkové soustavě je nekonečným jazykem nad abecedou {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. Nekonečná sada řetězců {2, 3, 5, 7, 11, 13,…} označení prvočísel v desítkové soustavě je jejich řádnou podmnožinou. Jazyk obsahující všechna slova odpovídající regulárnímu výrazu [+-]?\d+\.\d*([eE][+-]?\d+)? je jazyk přes znakovou sadu ASCII (označující podmnožinu platných výrazů s plovoucí desetinnou čárkou, jak jsou definovány programovacím jazykem C).

Neexistuje žádný jazyk, který by obsahoval všechna reálná čísla (v jakémkoli zápisu), protože množinu reálných čísel nelze počítat.

Nechť Σ být abeceda a L ⊆ Σ ^＊ . Stroj D rozhodne L pokud pro každý vstup w ∈ Σ ^＊ vypočítá charakteristickou funkci χ _L ( 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á decider pro L . Píšeme „ D ( w ) = x “ pro „vzhledem k w , D výstupy x ”.

Existuje mnoho modelů strojů. Nejobecnějším, který se dnes v praxi používá, je model Turingova stroje . Turingův stroj má neomezené lineární úložiště seskupené do buněk. Každá buňka může v kterémkoli okamžiku obsahovat přesně jeden symbol abecedy. Turingův stroj provádí svůj výpočet jako posloupnost výpočtový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. Jakou akci stroj provede, je řízen automatem konečného stavu.

Stroj s náhodným přístupem s omezenou sadou pokynů a neomezeným úložištěm je dalším modelem stroje, který je stejně výkonný jako model Turingova stroje. p>

Kvůli této diskusi nás nebudeme obtěžovat přesným modelem stroje, který používáme, ale stačí pouze říct, že stroj má konečnou deterministickou řídicí jednotku, neomezené úložiště a provádí výpočet jako posloupnost kroků to se dá spočítat.

Jelikož jste ji ve své otázce použili, předpokládám, že již znáte notaci „big-O“ takže zde je jen rychlé osvěžení.

Nechť f : N → být funkcí.Sada O ( f ) obsahuje všechny funkce g : N → N pro které existují konstanty n ₀ ∈ N a c ∈ N takové, že pro každé n ∈ N s n > n ₀ 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 ↦ n ^k ).

Od O ( n ↦ n ^k ), i když je matematicky správný, je nepohodlné psát a číst, většina lidí – abych byl upřímný, všichni kromě mě – obvykle píše jednoduše O;(n^k ).

Všimněte si, že vázané závisí na délce w . Argument, který uvedete pro jazyk prvočísel, je tedy správný pouze pro čísla v unaray encodings , kde pro kódování w číslo n , délka kódování | w | je úměrná n . Nikdo by takové kódování v praxi nikdy nepoužil. Použitím pokročilejšího algoritmu než pouhým zkoušením všech možných faktorů je však možné ukázat, že jazyk prvočísel zůstává v P , pokud jsou vstupy kódovány v binární podobě (nebo na jakékoli jiné bázi). (Navzdory velkému zájmu to dokázala pouze Manindra Agrawal, Neeraj Kayal a Nitin Saxena v oceněném příspěvku z roku 2004, takže můžete hádat, že algoritmus není příliš jednoduchý.)

Triviální jazyky {} a Σ ^＊ a netriviální jazyk { ε } jsou samozřejmě v P (pro jakoukoli abecedu Σ ). Můžete psát funkce ve vašem oblíbeném programovacím jazyce, které berou řetězec jako vstup a vrátit logickou hodnotu, která říká, zda je řetězec slovem z jazyka pro každý z nich, a dokázat, že vaše funkce má polynomiální běhovou složitost?

Každý regulární jazyk (jazyk popsaný regulárním výrazem) je v jazyce P .

Nechť Σ být abeceda a L ⊆ Σ ^＊ . Stroj V , který přebírá zakódovanou n-tici dvou slov w , c ∈ Σ ^＊ a výstupy 0 nebo 1 po konečném počtu kroků je ověřovatel pro L , pokud má následující vlastnosti.

• Vzhledem ( w , c ), V výstup 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 nesprávné negativy nesprávnému svědkovi, i když w je ve skutečnosti v L . Není však dovoleno uvádět falešně pozitivní výsledky. Rovněž se vyžaduje, aby pro každé slovo v jazyce existoval alespoň jeden svědek.

U jazyka COMPOSITE, který obsahuje desetinná kódování všech celých čísel, která nejsou primární , svědkem může být faktorizace. Například (659, 709) je svědkem 467231 ∈ KOMPOZITU. Můžete snadno ověřit, že na listu papíru bez svědka by bylo prokázání, že 467231 není prvočíslo, bez použití počítače obtížné.

Neřekli jsme nic o tom, jak může být vhodný svědek nalezeno. Toto je nedeterministická část.

Třída NP obsahuje všechny jazyky L , pro které existuje Turingův stroj V , který ověří L a konstantní k ∈ N takový, že pro každý vstup ( w , c ), V se zastaví po maximálně T (| w |) kroky pro funkci T ∈ O ( n ↦ n^k ).

Z výše uvedené definice vyplývá, ž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žinou P (proč?). Není známo, zda existují jazyky, které jsou v NP , ale ne v P .

Faktorizace celého čísla není jazyk sám o sobě. Můžeme však vytvořit jazyk, který představuje rozhodovací problém s ním spojený. To znamená, že jazyk obsahuje všechny n-tice ( n , m ), takže n má faktor d s d ≤ m . Říkejme tomuto jazyku FAKTOR. Pokud máte algoritmus, který rozhoduje o FAKTORU, lze jej použít 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ý primární faktor.

Je snadné ukázat, že FAKTOR je v NP . Vhodným svědkem by byl jednoduše faktor d a vše, co by ověřovatel musel udělat, je ověřit, že d ≤ m a n mod d = 0. To vše lze provést v polynomiálním čase. (Nezapomeňte, že se počítá délka kódování a je logaritmická v n .)

Pokud můžete ukázat, že FACTOR je také v P , můžete si být jisti, že získáte mnoho skvělých ocenění. (A prolomili jste významnou část dnešní kryptografie.)

Pro každý jazyk v NP existuje algoritmus hrubé síly, který rozhoduje to deterministicky. Jednoduše provede vyčerpávající vyhledávání u všech svědků. (Všimněte si, že maximální délka svědka je omezena polynomem.) Takže váš algoritmus rozhodování PRIMES byl ve skutečnosti algoritmem hrubou silou, který rozhodoval KOMPOZIT.

Abychom mohli odpovědět na vaši poslední otázku, musíme zavést redukci . Redukce jsou velmi silným konceptem teoretické počítačové vědy. Redukce jednoho problému na druhý v zásadě znamená řešení jednoho problému řešením jiného problém.

Nechť Σ být abeceda a A a B být jazyky přes Σ . A je polynomial-time many-one redukovatelné na B , pokud existuje funkce f : Σ ^＊ → Σ ^＊ s následujícími vlastnostmi.

• w ∈ A   ⇔   f ( w ) ∈ B   pro všechny w ∈ Σ ^＊ .
• Funkci f lze vypočítat Turingovým strojem pro každý vstup w v řadě kroků ohraničených polynomem v | w |.

V tomto případě napíšeme A ≤ _p B .

Pro příklad, nechť A je jazyk, který obsahuje všechny grafy (kódované jako matice sousedství), 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ů.) Potom A je polynomiálně mnohonásobně redukovatelné na B . Abychom to dokázali, musíme najít vhodnou transformační funkci f . V tomto případě můžeme nastavit f na výpočet 3. ^rd síly matice sousedství. To vyžaduje dva produkty matice-matice, z nichž každý má polynomiální složitost.

Triviálně platí, že L ≤ _p L . (Dokážete to formálně?)

Nyní to aplikujeme na NP .

Jazyk L je NP -hard právě když L „≤ _p L pro každý jazyk L “ ∈ NP .

Tvrdý jazyk NP může nebo nemusí být v samotném NP .

Jazyk L je NP -complete právě a jen tehdy

• L ∈ NP a
• L je NP -hard.

Nejznámějším úplným jazykem NP je SAT. Obsahuje všechny booleovské vzorce, které lze splnit. Například ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Platným svědkem je { a = 1, b = 0}. Vzorec ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Jak byste to dokázali?)

Není těžké ukázat, že SAT ∈ NP . Ukázat tvrdost NP SAT je práce, ale provedl ji v roce 1971 Stephen Cook .

Jakmile byl znám jeden úplný jazyk NP , bylo relativně jednoduché zobrazit redukci pomocí NP úplnosti jiných jazyků. Pokud je známo, že jazyk A je NP tvrdý, pak ukazuje, že A ≤ _p B ukazuje, že B je také NP -hard (přes tranzitivitu „≤ _p ”). V roce 1972 Richard Karp zveřejnil seznam 21 jazyků, které by mohl ukázat jako NP úplné pomocí (přechodné) redukce SAT. (Toto je jediný článek v této odpovědi, který si vlastně doporučuji přečíst. Na rozdíl od ostatních to není těžké pochopit a poskytuje velmi dobrou představu o tom, jak funguje prokazování úplnosti NP prostřednictvím redukce. )

Na závěr krátké shrnutí. Symboly NPH a NPC použijeme k označení tříd úplných jazyků NP a NP v uvedeném pořadí.

• P ⊆ NP~
• NPC ⊂ NP a NPC ⊂ NPH , vlastně NPC = NP ∩ NPH podle definice
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Upozorňujeme, že zahrnutí 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í jazyk a že v triviálu P existují také triviální jazyky jako netriviální jazyky v NP . Thi s je však (nepříliš zajímavý) případ.

Dodatek

Zdá se, že vaším primárním zdrojem záměny je, že jste mysleli na „ n “v„ O ( n ↦ f ( n )) “Jako interpretace vstupu algoritmu, když ve skutečnosti odkazuje na délku vstupu. Toto je důležitý rozdíl, protože to znamená, že asymptotická složitost algoritmu závisí na kódování použitém pro vstup.

Tento týden nový záznam pro největší známý Mersenne prime bylo dosaženo. Největší v současnosti známé prvočíslo je 2 ^{74   207   281} – 1. Toto číslo je tak obrovské že mě z toho bolí hlava, takže v následujícím příkladu použiji menší: 2 ³¹ – 1 = 2   147   483   647. Lze jej kódovat různými způsoby.

• jeho Mersennovým exponentem jako desetinné číslo: 31 (2 bajty)
• jako desetinné číslo: 2147483647 (10 bajtů)
• jako unární number: 11111…11 kde … má být nahrazen 2   147   483   640 dalších 1 s (téměř 2 GiB)

Všechny tyto řetězce kódují stejné číslo a vzhledem k některému z nich můžeme snadno sestavit jakékoli jiné kódování se stejným číslem. (Desítkové kódování můžete nahradit binárním, osmičkovým nebo hexadecimálním mal, pokud chceš. Změní pouze délku o konstantní faktor.)

Naivní algoritmus pro testování primality je pro unární kódování pouze polynomický. Test primality AKS je polynomický pro desítkové (nebo jakýkoli jiný základ b ≥ 2 ). Lucas-Lehmerův test primality je nejznámější algoritmus pro Mersenneovy prvočísla M _p s p lichým prvočíslem, ale stále je exponenciální v délce binárního kódování Mersennova exponentu p (polynom v p ).

Chceme-li hovořit o složitosti algoritmu, je velmi důležité, abychom si byli velmi jasní, jakou reprezentaci používáme. Obecně lze předpokládat, že se používá nejefektivnější kódování. To znamená binární pro celá čísla. (Všimněte si, že ne každé prvočíslo je Mersennovým prvočíslem, takže použití Mersennova exponentu není obecným schématem kódování.)

V teoretické kryptografii je mnoha algoritmům formálně předán zcela zbytečný řetězec k 1 s jako první parametr. Algoritmus se na tento parametr nikdy nepodílí, ale umožňuje mu formálně být polynomem v k , což je bezpečnostní parametr slouží k vyladění zabezpečení postupu.

U některých problémů, u kterých je rozhodovací jazyk v binárním kódování NP – úplný, rozhodovací jazyk již není NP – dokončeno, pokud je kódování vložených čísel přepnuto na unární. Rozhodovací jazyky pro další problémy zůstávají NP – úplné i poté. Posledně jmenované se nazývají silně NP – úplné . Nejznámějším příkladem je bin packing .

Je také (a možná i více) zajímavé sledovat, jak složitost algoritmu se změní, pokud je vstup komprimován . U příkladu Mersennových prvočísel 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ý dokument o složitosti běžných algoritmů grafů, když je vstupní kódování grafu logaritmicky komprimováno. U těchto vstupů se jazyk grafů obsahujících trojúhelník shora (kde byl jasně v P ) najednou stává úplným NP .

A to „protože jazykové třídy jako P a NP jsou definovány pro jazyky , nikoli pro problémy .

Komentáře

• Tato odpověď pravděpodobně není užitečná pro úroveň porozumění tazateli. Přečtěte si další odpovědi a podívejte se, s čím se společnost Nanako potýká. Myslíte si to odpověď mu pomůže?
• Tato odpověď nemusí OP pomoci, ale rozhodně pomůže ostatním čtenářům (včetně mě).
• velmi užitečná odpověď! měli byste zvážit nesprávnou opravu matematických symbolů zobrazeno.

Pokusím se vám poskytnout stejnou neformální definici.

P problémy: problémy, které lze vyřešit v polynomiálním čase. Obsahuje problémy, které lze efektivně řešit.

NP problém: problémy, které lze ověřit v polyno čas. Například: Obchodní cestující, návrh obvodů. Problémy s NP jsou jako hádanky (jako sudoku). Při správném řešení problému můžeme naše řešení zkontrolovat velmi rychle, ale pokud se ho skutečně pokusíme vyřešit, může to trvat věčně.

Nyní se P vs NP vlastně ptá, zda problém, jehož řešení může být rychle zkontrolováno, že je správné, pak existuje vždy rychlý způsob, jak to vyřešit. Matematicky tedy píšeme: je NP podmnožinou P nebo ne?

Nyní se vracíme k NP úplné: to jsou opravdu těžké problémy NP. Proto pokud existuje rychlejší způsob řešení NP complete, pak NP complete se stane P a NP se sbalí do P.

NP hard: problémy, které nelze v polynomiálním čase ani zkontrolovat, jsou np těžké. Jedním z nich je například výběr nejlepšího tahu v šachu.

Pokud něco není jasné, zkuste sledovat toto video: https://www.youtube.com/watch?v=YX40hbAHx3s

Doufám, že to poskytne nějaký rozmazaný obrys.