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

[Nemo7]

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

Ten semestr až dva se totiž učí matematický aparát okolo, aby pomocí toho aparátu šlo studovaný problém vůbec vydefinovat. 

[Reklama]

[Mirek Prýmek]

Ten semestr až dva se totiž učí matematický aparát okolo, aby pomocí toho aparátu šlo studovaný problém vůbec vydefinovat. 

Ano. A jelikož valná část studentů se tím aparátem neprokouše, nenaučí se vůbec nic, v tom je ta pointa

[Lol Phirae]

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

A až se tenhle kruciální problém vyřeší, tak bude konečně levnější pivo? 

[Ivan]

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

Jakub to asi nejlip. Mozna lepe nez tvuj ucitel. Dulezite je ze problemy lze prevatet. Tzn. jeden problem vyresis prevedenim na jiny. Pro NP-uplne problemy jde ukazat takovy cyklus, ze kazdy z nich lze prevest na nejaky jiny. A pokud by jeden z jich byl efektivne resitelny tak by byly resitelne vsechny. Asi "nejzajimavejsi" problem z tohodle pohledu je problem kachlikovani koupelny, na ktery lze prevest vypocet TS.

[Pali]

Asi "nejzajimavejsi" problem z tohodle pohledu je problem kachlikovani koupelny, na ktery lze prevest vypocet TS.

Pozor, problém vykachličkovania kúpeľne je obmedzený a teda to nebude výpočet TS, ale výpočet lineárne obmedzeného TS (LBA).

[Reklama]

[Nobody]

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

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.

Myslel jsem, ze tzv. Prymkova veta zni: je-li obsah ctverce nad preponou, pak alespon 30% prispevku ve vlakne je Mirka Prymka.


Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?

[fox]

Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?

Ne. V praxi na řešení P/NP problémů nedojde za celý život absolventa. Otázka rozhodnutelnosti nebo problém zastavení je v praxi degenerován na otázku zda algoritmus vyplivne výsledek před spotřebováním přidělených prostředků (čas, RAM, HDD)

[JSH]

Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?

Krom toho, že pak absolvent tuší třeba to, proč se ty všudypřítomné šifry blbě louskají, to nejspíš až tak využitelné není.

Ale pokud si vezmu třeba náplň TINu na FITu, tak tam je P vs. NP taková třešnička na dortu a zabírá to kousek poslední přednášky. Většinu semestru se berou podstatně praktičtější věci jako regulární výrazy a bezkontextové gramatiky. Je to sice teorie, ale úplně odtržená od reality fakt není.

[njn]

Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?

Krom toho, že pak absolvent tuší třeba to, proč se ty všudypřítomné šifry blbě louskají, to nejspíš až tak využitelné není.

Ale pokud si vezmu třeba náplň TINu na FITu, tak tam je P vs. NP taková třešnička na dortu a zabírá to kousek poslední přednášky. Většinu semestru se berou podstatně praktičtější věci jako regulární výrazy a bezkontextové gramatiky. Je to sice teorie, ale úplně odtržená od reality fakt není.

no a v tom bych videl uplne ten nejzasadnejsi problem, protoze presto, ze absolvent zna teorii nazpamet a zkouskou proleze - latku nechape v souvislostech. presne jako zdejsi traged co se ptal. neuvedomuje si, ze jsou k dispozici (dnes uz i komercne) silnejsi metody nez jen turinguv stroj i kdyz teda zatim maji jen mizernou vyuzitelnost kvuli nedokonalemu zvladnuti technologie.

[pseudonym neni anonym]

neuvedomuje si, ze jsou k dispozici (dnes uz i komercne) silnejsi metody nez jen turinguv stroj

Citation needed!

[Mirek Prýmek]

Ne. V praxi na řešení P/NP problémů nedojde za celý život absolventa. Otázka rozhodnutelnosti nebo problém zastavení je v praxi degenerován na otázku zda algoritmus vyplivne výsledek před spotřebováním přidělených prostředků (čas, RAM, HDD)

Spíš když už si z toho chceme utahovat, viděl bych největší pikantnost v tom, že vzhledem k tomu, že jde o asymptotickou složitost, může být v praxi algoritmus A složitosti O(2N) klidně vždy rychlejší než algoritmus B složitosti O(1), páč nás jak na potvoru zajímá jenom zpracování dostatečně malých vstupů