Problémy P, NP, NP-úplné, NP-těžké

[Samufaj]

Zdravím,
 učím se na státnice a už mám odst těch slintů od jednoho nejmenovaného dědka z naši VŠ co debilně vede teoretickou informatiku.

Need help:

NP-těžké problémy - tyhle jsou jasné, patří tam problém obchodního cestujícího (OC). Nezbývá-li nám nic jiného, než vyzkoušet všechna možná řešení která mohou nastat, je problém NP-těžký. Každý problém je transformovatelný na problém OC.

NP-úplné problémy - sem patří problém OC v rozhodovací verzi (Existuje v grafu cesta menší než délky X?) - nemusíme procházet všechna řešení, složitost není nutně n! jako při hledání nejkratší cesty.

NP problémy - tady tu třídu už nevím jak bych zdůvodnil, osobně bych ji spojil s třídou NP-úplných. Patří zde problém izomorfismu dvou grafů (jsou dva grafy navzájem izomorfní?) nicméně nevidím zde v principu žádný rozdíl oproti problému OC v rozhodovací verzi

P problémy - tyhle jsou jasné, jsou to problémy typu třídění, víme u nich jak dlouho budou trvat.


Ví někdo jak vysvětlit, proč OC v rozhodovací verzi patří do NP-úplných, ale izomorfismus dvou grafů patří do NP?

[Reklama]

[njn]

http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg to bude tim, ze se pocita s jeste nespocitanym. nikdo nevi jak to je s (ne)rovnosti P a NP

[JSH]

Je to trochu jinak :

NP znamená, že je dokáže řešit nedeterministický Turingův stroj v polynomiálním čase. Já si to představuju pomocí křišťálové koule, která u každého ifu řekne, kudy se vydat. Bez koule je třeba vyzkoušet všechny možnosti a to je exponenciální počet možných kombinací. Obchodní cestující, barvení grafu a podobně jsou NP.

P znamená polynomiální čas u detetministického stroje. Složitost kvadratická, kubická a i vyšší mocniny patří do P. Nedeterministický TS zvládne i tohle, takže P je podmnožina NP.

Těžký/úplný není o jednom problému, ale o převádění problémů mezi sebou.

NP-těžký - jakýkoliv NP problém jde převést na tenhle. NP-těžký problém může být NP nebo i náročnější.

NP-úplný - NP-těžký problém, který je sám NP. Všechny NP-úplné jsou i NP-těžké. Obchodní cestující, barvení grafu, atd. jsou všechny NP-úplné, protože jsou samy NP.

U isomorfismu grafů se momentálně neví, jak to přesně je. Nedeteministický TS to řešit umí, takže je určitě NP nebo lepší. Ještě nikdo nedokázal, jestli to náhodou nejde i deterministickým TS. Možná je to jen P, akorát se to ještě neví. Čeká se buď na to, že někdo najde algoritmus v P, nebo na to že někdo zvládne převést nějaký NP-úplný problém na hledání izomorfismu a pak bude jasné, že je to NP-úplné.

[JSH]

A samozřejmě jak psal njn, možná P odpovídá NP. Tohle se taky ještě neví. Pak by celý tenhle binec krásne splaskl.

Teď koukám, že jsem ten nedeterministický TS popsal asi trochu matoucím způsobem. Z té koule se tahají možnosti, kudy se má ten algoritmus vydat. Takže bude z koule tahat třeba barvy při barvení grafu nebo města u obchodního cestujícího.

[jb]

P vs. NP and the Computational Complexity Zoo:
https://www.youtube.com/watch?v=YX40hbAHx3s

[Reklama]

[Radek Miček]

NP-těžký - jakýkoliv NP problém jde převést na tenhle. NP-těžký problém může být NP nebo i náročnější.

Jen dodám, že se v tomto případě jedná o převody pomocí DTS v polynomiálním čase.

U isomorfismu grafů se momentálně neví, jak to přesně je. Nedeteministický TS to řešit umí, takže je určitě NP nebo lepší. Ještě nikdo nedokázal, jestli to náhodou nejde i deterministickým TS. Možná je to jen P, akorát se to ještě neví. Čeká se buď na to, že někdo najde algoritmus v P, nebo na to že někdo zvládne převést nějaký NP-úplný problém na hledání izomorfismu a pak bude jasné, že je to NP-úplné.

Pokud se P nerovná NP, pak existují problémy, které jsou v NP, nejsou v P a nejsou ani NP-úplné.

[Pali]

Těžké problémy - http://ksp.mff.cuni.cz/viz/kucharky/tezke-problemy

[student]

NP-těžké problémy - tyhle jsou jasné, patří tam problém obchodního cestujícího (OC). Nezbývá-li nám nic jiného, než vyzkoušet všechna možná řešení která mohou nastat, je problém NP-těžký. Každý problém je transformovatelný na problém OC.

Pozor - to o transformovani neplati. NP-tezky je aj halting problem, ale netransformujes ho na problem OC. NP-tezky = aspon tak tazky, ako najnarocnejsie problemy v NP.

NP-úplné problémy - sem patří problém OC v rozhodovací verzi (Existuje v grafu cesta menší než délky X?) - nemusíme procházet všechna řešení, složitost není nutně n! jako při hledání nejkratší cesty.

NP uplne = najnarocnejsie problemy v NP. Kazdy problem v NP je prevoditelny na NP uplny problem (tym sa da dokazat, ze problem je v NP).

NP problémy - tady tu třídu už nevím jak bych zdůvodnil, osobně bych ji spojil s třídou NP-úplných. Patří zde problém izomorfismu dvou grafů (jsou dva grafy navzájem izomorfní?) nicméně nevidím zde v principu žádný rozdíl oproti problému OC v rozhodovací verzi

NP problemy bud definujes cez nedeterministicky Turingov stroj (ako to robil JSH) ale podla mna je to jednoduchsie vidiet cez overenie riesenia. NP problemy su tie, ktorych riesenie dokazes overit v polynomialnom case.

Oznacim najkratsiu cestu v grafe a opytam sa, ci je tam najkratsia cesta kratsia ako x. To overis lahko.

P problémy - tyhle jsou jasné, jsou to problémy typu třídění, víme u nich jak dlouho budou trvat.

Ten dodatok "vim, jak dlouho budou trvat" tam radsej nedavaj. Ich trvanie sa da obmedzit polynomom velkosti vstupu.

U NP vseobecne sa zatial vie len obmedzenie exponencialou, ale pri P=NP to bude rovnako polynom.
Naviac vieme odhadnut len vypoctovu zlozitost konkretnych algoritmov ("skolske" nasobenie matic bezi v Θ(n^3)) - zlozitost problemu v niektorych pripadoch konkretne nevieme. Nasobenie matic sa urcite neda spravit v case mensom ako Ω(n^2), lebo treba precitat cely vstup. Ci to ale bude O(n^2.38) alebo O(n^2.2), to sa nevie.

[linux_noob]

Pozor - to o transformovani neplati. NP-tezky je aj halting problem, ale netransformujes ho na problem OC. NP-tezky = aspon tak tazky, ako najnarocnejsie problemy v NP.

ehm, halting problem, ze je NP-tezky? Aspon mas pravdu, ze ho netransformujes na TSP no

http://en.wikipedia.org/wiki/Halting_problem

[Pali]

ehm, halting problem, ze je NP-tezky?

Áno, halting problem je NP-ťažký. Je to rozhodovací problém, ktorý neleží v triede NP, ale každý NP-úplný problém sa dá redukovať na ňho.

[JSH]

Naviac vieme odhadnut len vypoctovu zlozitost konkretnych algoritmov ("skolske" nasobenie matic bezi v Θ(n^3)) - zlozitost problemu v niektorych pripadoch konkretne nevieme. Nasobenie matic sa urcite neda spravit v case mensom ako Ω(n^2), lebo treba precitat cely vstup. Ci to ale bude O(n^2.38) alebo O(n^2.2), to sa nevie.

U matic a podobných zrovna bacha. Je rozdíl mezi n v "praktických" a "teoretických" výpočtech složitosti. U praktických popisů je n třeba velikost čísla na vstupu, nebo počet řádků čtvercové matice. Ale pokud to bereme čistě teoreticky, tak je to vždycky počet symbolů na pásce, tzn. nějaká nedůležitá konstanta krát počet bitů nebo bytů vstupu.
Extrémně zákeřný příklad jsou algoritmy, co mají na vstupu jediné číslo. Počet bitů je logaritmus čísla, takže i blbý TS, co jen inkrementuje čísla od 0 do zadaného udělá exponenciální počet kroků.

[linux_noob]

@pali: sorry, nejak jsem si popletl definice, uz je mi to jasny

[Samufaj]

Tak teď jsem z toho ještě víc jelen.

Když na to půjdu logicky:

NP-těžké problémy jsou všechny problémy, u kterých musíme zkoušet všechny možnosti které mohou nastat, protože neznáme žádnou fintu k jejich vyřešení.

NP-úplné problémy jsou všechny NP-těžké problémy, u kterých nehledáme nejlepší řešení, ale chceme dostatečné řešení (např. cesta v grafu kratší než X)

NP problémy opět nedkokážu vysvětlit, prostě mi tu nezapadá. Co třeba problémy, u kterých částečně známe fintu? Např. hamiltonovský cyklus, u kterého jsme schopni vyvodit ihned výsledek. 

P problémy jsou NP-těžké problémy, pro které známe algoritmus který je vyřeší v polynomiálním čase. Např. i obyčejné třídění, kdyby průměrné IQ bylo houpacího koně, bychom řešili zkoušením všech možnosti, kterých by bylo n!. (ptali bychom se: je nyní množina setřízena od nejmenšího po největší?)



Mě prostě ty definice nedávají smysl, očekával bych od nich trochu logiky.

[Samufaj]

(sorry za ty chyby v textu, píšu to narychlo)

[Samufaj]

A taky mi tu nehraje, proč je problém OC NP-úplný, ten problém přece nemá nedeterministickou časovou složitost, protože na základě počtu uzlů jsme hned schopni říct, kolik přesně se má vyzkoušet cest, bude jich n! - na tom přece není nic nedeterministického. Prostě mi to rozdělení do těch tříd celkově nedává smysl.