vysvětlíte mi někdo co to je Problém P versus NP?

Problém P versus NP je, jednoducho povedané, otázka, či sú tieto triedy totožné.

zjednodušene si to predstavte ako vetvenie (programu) pri hľadaní riešenia (napr ako strom).

trieda p sa zaoberá priamo hľadaním riešenia – po jeho nájdení ďalej nepátra, či je i iné riešenie.

trieda np sa zaoberá hľadaním, či problém riešenie má – po jeho nájdení ďalej nepátra, či je i iné riešenie.

tieto operácie prebiehajú v nejakom čase, ktorý sa nazýva polynomiálny (daný plynómom, sumou mnohočlenu – všetkých časov strávených hľadaním vo všetkých vetvách/odbočkách hľadania riešenia, resp. možnosti riešenia).
preto je tento čas konečný, podobne, ako počet hľadaní.

algoritmy potrebné k vyriešeniu/vy­hodnoteniu problému sú neefektívne, preto so zložitosťou problému narastá i čas potrebný na nájdenie požadovaného výsledku (z toho vyplýva otázka problému: ak je rýchly čas výpočtu, je rýchly i čas overenia?, resp naopak? [1]).

rozdiel tried je v spôsobe, ako sa dospieva ku cieľu – u problému p sa pristupuje ku hľadaniu riešenia/overenia deterministickým (tj. lineárnym) postupom (vykonáva sa jedna operácia v jednej „vetve“), kdežto v triede np nedeterministickým (tj. nelineárnym) postupom (vykonávajú sa viaceré operácie naraz v rôznych „vetvách“).

otázka teda je, či je „zložitosť“ tried rovnaká. (pozri otázku [1])

no a to je celé.

;-Q

Bohužel, nejenom na internetu, ale i ve skutečnosti je to velice složité.

Takže jenom velice jednoduše: Pod písmenem P se skrývá třída úloh, které umí deterministický Turingův stroj vyřešit v polynomiálním čase. Po NP pak třída úloh, jejichž řešení umí v polynomiálním čase ověřit (pozor, nikoliv vyřešit) také deterministický Turingův stroj, ale ono řešení umí v polynomiálním čase najít jen nedeterministický Turingův stroj. Je zřejmé, že P je podmnožinou NP, ale otázka, zda jsou tyto třídy úloh ekvivalentní, patří (či možná patřila) mezi nejdůležitější úlohy matematiky a informatiky.

Rozumíš tomu? Já ne.

Myslím, že nejstručněji a nejméně vědecky je to zde:
http://www.ge­neze.info/poj­my/subdir/pro­blemy_tisicile­ti.htm
PROBLÉM P VERSUS NP
Jediný problém, týkající se počítačů (v pův. Hilbertových problémech byl problém č. 10 také „počítačový“ – šlo o důkaz, že jisté rovnice nelze vyřešit strojem – problém byl vyřešen r. 1970)
Výpočetní úlohy pro počítače se dělí do dvou skupin: kategorie P (polynomální), jež mohou být úspěšně vyřešeny strojem a úlohy typu E (exponenciální), jejichž vyřešení počítačem by vyžadovalo miliony let strojového času. Většina důležitých výpočetních úloh spadá do kategorie NP, která, jak se zdá, leží někdy mezi typy P a E. Ale není náhodou kategorie NP jen ‚převlečná‘ P ? Většina odborníků věří, že NP a P nejsou totožné, ale stále o tom není rozhodnuto. Kladná odpověď (NP = P) by našla významné aplikace v průmyslu či elektronických komunikačních prostředcích.