http://www.multimediaexpo.cz/mmecz/index.php?action=history&feed=atom&title=NP_%28t%C5%99%C3%ADda_slo%C5%BEitosti%29 2026-06-22T18:55:03Z Historie editací této stránky MediaWiki 1.16.5 http://www.multimediaexpo.cz/mmecz/index.php?title=NP_(t%C5%99%C3%ADda_slo%C5%BEitosti)&diff=1519495&oldid=prev 2019-03-03T10:42:01Z

<p>+ Nový článek</p> <p><b>Nová stránka</b></p><div>'''NP''' (zkratka '''nedeterministicky polynomiální''') je [[množina]] problémů, které lze řešit v [[polynom]]iálně omezeném čase na nedeterministickém [[Turingův stroj|Turingově stroji]] – na ''[[počítač]]i'', který umožňuje v každém kroku rozvětvit výpočet na ''n'' větví, v nichž se posléze řešení hledá současně. Ekvivalentně se hovoří o stroji, který na místě rozhodování uhodne správnou cestu výpočtu. Alternativně lze tyto problémy definovat tak, že je to množina problémů, u kterých lze ''pro dodaný výsledek'' v polynomiálním čase ověřit jeho správnost (ale obecně nikoliv ''nalézt řešení'' v polynomiálním čase).<br /> <br /> Složitostní třída [[P (třída složitosti)|P]] je obsažena v NP, ale NP obsahuje velké množství důležitých problémů, zvaných [[NP-úplnost|NP-úplné]], pro které není znám žádný polynomiální algoritmus. Pravděpodobně nejdůležitějším problémem současné [[informatika|informatiky]] (patří mezi [[Problémy tisíciletí|Problémy milénia]]) je otázka, zda [[Problém P versus NP|'''P''' = '''NP''']]. Většina expertů ale věří, že P je [[vlastní podmnožina|vlastní podmnožinou]] NP.<br /> <br /> == Příklady problémů v NP ==<br /> * Všechny problémy v [[P (třída složitosti)|'''P''']]<br /> * [[Faktorizace přirozených čísel]] – tj. hledání dělitelů čísla<br /> * [[Faktorizace|Faktorizace celých čísel]]<br /> * [[Izomorfismus grafů]] – problém rozhodnutí, zda je možné dva [[graf (teorie grafů)|grafy]] shodně nakreslit <br /> * [[Problém obchodního cestujícího]]<br /> <br /> <br /> {{Článek z Wikipedie}}<br /> [[Kategorie:Třídy složitosti]]</div>

Sysop