problém ve věku P versus NP
takže co je tedy problém P versus NP?
pro záznam, status quo je, že P≠NP.
P (polynomický čas) označuje třídu problémů, které lze vyřešit algoritmem v polynomiálním čase. Problémy ve třídě P se mohou pohybovat od všeho tak jednoduchého jako násobení až po nalezení největšího počtu v seznamu. Jsou to relativně „jednodušší“ soubor problémů.
NP (nedeterministický polynomický čas) označuje třídu problémů, které lze v polynomiálním čase vyřešit nedeterministickým počítačem., To je v podstatě další způsob, jak říci“pokud mám neomezenou výpočetní sílu (tj. tolik počítačů, kolik potřebuji), jsem schopen vyřešit jakýkoli problém ve většině polynomiálních časů“. Více intuitivně, i když, to se odkazuje na třídu problémů, které v současné době nemá žádný způsob, jak najít rychlé (polynomiální čas) stačí odpověď, ALE může být rychle ověřit (v polynomiálním čase), pokud jedna nabízí řešení problému. Termín ověřený zde znamená, že je možné zkontrolovat, zda je poskytnuté řešení skutečně správné.
jasně, na základě výše uvedené definice, P ⊆ NP., Podívejme se na příklad pro ilustraci tohoto abstraktního problému.
jedním z nejčastějších, ale účinných příkladů je Sudoku. Vzhledem k nevyřešené mřížce Sudoku (například 9 x 9) by trvalo, než by algoritmus vyřešil jeden. Pokud se však mřížka 9 x 9 zvýší na mřížku 100 x 100 nebo 10 000 x 10 000, čas potřebný k vyřešení by se exponenciálně zvýšil, protože samotný problém se stává výrazně těžší., Vzhledem k vyřešené mřížce Sudoku (9 x 9) je však poměrně jednoduché ověřit, zda je konkrétní řešení skutečně správné, i když velikost se pohybuje na 10 000 x 10 000. Bylo by to pomalejší, ale čas na kontrolu řešení se zvyšuje pomaleji (polynomiálně).
existuje mnoho dalších problémů s NP, včetně problému s batohem a problému cestujících prodejců, a jsou podobné v tom, že je těžké je vyřešit, ale rychle ověřit., Základní problém se snažíme vyřešit, je:
být schopen rychle rozpoznat NP správné odpovědi znamenají, že tam je také rychlý způsob, jak je najít?
Pokud ano (tj. P=NP), mohlo by to výrazně změnit to, jak se díváme na tyto NP problémy, protože to znamená, že tam je rychlý způsob, jak vyřešit všechny tyto problémy, jen to, že jsme nebyli schopni přijít na to, jak, ALE.
pokud to není dost komplikované,okořeníme to.,
mezi těmito problémy NP existuje král všech problémů, které vědci nazývají NP-kompletní problémy. Formálně, oni jsou řadu problémů, z nichž každý jiné NP problém může být snížena (uvedeny níže) v polynomiálním čase, a jejichž řešení může být ještě ověřit v polynomiálním čase. To znamená, že jakýkoli problém NP může být přeměněn na problém NP-Complete.
neformálně jsou „nejtěžší“ problémy NP., Pokud tedy lze nějaký problém NP-Complete vyřešit v polynomiálním čase, pak lze každý problém NP-Complete vyřešit v polynomiálním čase a každý problém v NP lze vyřešit v polynomiálním čase (tj. P=NP). Nejznámějším příkladem by byl problém cestujících prodejců.
existuje také sadu problémů nazývá NP-Těžké problémy., Tyto problémy jsou přinejmenším stejně těžké jako problémy s NP, ale bez podmínky, která vyžaduje, aby byly vyřešeny v polynomiálním čase. To naznačuje, že problémy NP-Hard nemusí být nutně součástí třídy NP. Příkladem by bylo řešení šachovnice-vzhledem k stavu šachovnice je téměř nemožné zjistit, zda daný pohyb v daném stavu je ve skutečnosti optimálním tahem. Formálně neexistuje žádný polynomický časový algoritmus pro ověření řešení problému NP-Hard.,
pokud dáme oba dohromady, problém s NP-kompletní znamená, že je NP-tvrdý, ale problém s NP-Hard neznamená, že je kompletní NP.
Definování NP-Úplnost
problém L je NP-Úplný, pokud:
- L je NP-Těžké
- L patří do NP
obrázek níže (zaměření na levé straně), by měl dělat věci jasnější.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Neformálně, problém L1 může být snížena na další problém, L2, pokud:
- Žádné instance L1 lze modelovat jako instance L2
- řešení, k druhé poskytuje řešení pro bývalé a naopak
pochopit intuitivně, jeden může myslet na to jako takové:
Pokud L1 je redukovatelné na L2, L1 musí být maximálně tvrdé jako L2. Naopak, L2 musí být alespoň tak tvrdý jako L1.
Matematicky, je označován jako: L1 ≤p L2 (číst jako „L1 je polynomially redukovatelné na L2“).,
