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

Samufaj

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #15 kdy: 08. 06. 2015, 19:48:53 »
(pardon, má tam být NP-těžký)


Samufaj

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #16 kdy: 08. 06. 2015, 19:55:10 »
Tak snad na tu třídu NP jsem přišel: patří tam problém hemiltonovského cyklu, ten tedy nebude NP-úplný, protože známe částečně způsob, jak určit, že v grafu hemilt. cyklus existuje (viz wiki, je to něco s uzly) - kdežto třeba u problému OC v rozhodovací verzi žádnou neznáme a proto je NP-úplný.

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  :-\

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #17 kdy: 08. 06. 2015, 20:42:18 »
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.

rookie

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #18 kdy: 08. 06. 2015, 21:25:36 »
Mrkni na skripte Demlove, mohlo by ti to pomoct:

http://math.feld.cvut.cz/demlova/teaching/tal/predn_tal.html

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #19 kdy: 08. 06. 2015, 21:32:18 »
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.

Ty definice logické jsou, chyba je v "uživateli".


Samufaj

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #20 kdy: 08. 06. 2015, 21:33:23 »
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.

No super, díky, teď už mi to dává smysl že je to relativně k TS. Záhada století vyřešena :-)

Samufaj

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #21 kdy: 08. 06. 2015, 21:38:25 »
Ale ještě ti tam chybí NP-úplné problémy, to jsou pak jaké?

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #22 kdy: 08. 06. 2015, 21:43:53 »
Ale ještě ti tam chybí NP-úplné problémy, to jsou pak jaké?

Nechybí, píšu o nich úplně dole.

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #23 kdy: 08. 06. 2015, 21:46:04 »
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
Zapomněl jsi ještě na jeden důležitý teorém (tzv. Prýmkův):

Citace
Každá ptákovina, kterou:
  • tě ve škole učí semestr až dva
  • vůbec jí po těch dvou semestrech nerozumíš
  • a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
je v polynomiálním čase převoditelná na 36 řádků naprosto srozumitelného, jasného textu, který teprve ti umožní ty státnice udělat.

;)

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #24 kdy: 08. 06. 2015, 22:43:56 »
Ještě bych možná doporučil kouknout se na tento obrázek:




Předpokládá se, že asi P != NP a tedy platí ta varianta vlevo.

njn

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #25 kdy: 09. 06. 2015, 06:27:16 »
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
Zapomněl jsi ještě na jeden důležitý teorém (tzv. Prýmkův):

Citace
Každá ptákovina, kterou:
  • tě ve škole učí semestr až dva
  • vůbec jí po těch dvou semestrech nerozumíš
  • a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
je v polynomiálním čase převoditelná na 36 řádků naprosto srozumitelného, jasného textu, který teprve ti umožní ty státnice udělat.

;)

Jo taky nechápu proč už se neučí složitosti kvantových algoritmů. Tam aspoň ještě je co objevovat.

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #26 kdy: 09. 06. 2015, 08:40:29 »
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
Zapomněl jsi ještě na jeden důležitý teorém (tzv. Prýmkův):

Citace
Každá ptákovina, kterou:
  • tě ve škole učí semestr až dva
  • vůbec jí po těch dvou semestrech nerozumíš
  • a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
je v polynomiálním čase převoditelná na 36 řádků naprosto srozumitelného, jasného textu, který teprve ti umožní ty státnice udělat.

;)

Jen aby ten polynomiální čas nebyl třeba O(n^1000000)...

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #27 kdy: 09. 06. 2015, 08:58:44 »
Jen aby ten polynomiální čas nebyl třeba O(n^1000000)...
Jak vidíš, Kuba to zvládl v celkem krátkém čase :)

fish

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #28 kdy: 09. 06. 2015, 10:02:25 »
Tady je to poměrně dobře zpracované:

http://math.feld.cvut.cz/demlova/teaching/tal/p-tal5dohr.pdf

JSH

Re:Problémy P, NP, NP-úplné, NP-těžké
« Odpověď #29 kdy: 09. 06. 2015, 10:50:39 »
Každá ptákovina, kterou:
  • tě ve škole učí semestr až dva
  • vůbec jí po těch dvou semestrech nerozumíš
  • a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
Jestli jsi studoval na škole, kde se tohle učilo semestr až dva, tak celkem chápu odpor k univerzitám :)