Avatar uživatele
Pokročilý

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

já vim že je to na internetu ale tam je to moc složitý

Uzamčená otázka – ohodnoťte nejlepší odpověď symbolem palce.

Nejlepší odpověď

Avatar uživatele
Zlatý

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/vyhodnoteniu 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

 

Další odpovědi:

Avatar uživatele
Zlatý

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.


Avatar uživatele
Bronzový

Myslím, že nejstručněji a nejméně vědecky je to zde:
http://www.geneze.info/…
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.

 

Diskuze k otázce

 

U otázky nebylo diskutováno.

 

Přihlásit se

Položte otázku, odpovězte, zapojte se, …

začněte zde

Reklama

Kvalitní odpovědi v: Věda

Zlatý annas 2736
Zlatý quentos 1320
Zlatý mosoj 1305
Zlatý Drap 964
Zlatý hanulka11 627
Zlatý led 604
Zlatý gecco 589
Zlatý marci1 538
Zlatý arygnoc 507
Zlatý Lamalam 487

Zobrazit celkový žebříček

Facebook

 

Váš požadavek se vyřizuje, počkejte prosím.