NP (třída složitosti)

Z Multimediaexpo.cz

Nemáte oprávnění „upravit tuto stránku“. Důvod:

Můžete si prohlédnout a zkopírovat zdrojový kód této stránky:

'''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). 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. == Příklady problémů v NP == * Všechny problémy v [[P (třída složitosti)|'''P''']] * [[Faktorizace přirozených čísel]] – tj. hledání dělitelů čísla * [[Faktorizace|Faktorizace celých čísel]] * [[Izomorfismus grafů]] – problém rozhodnutí, zda je možné dva [[graf (teorie grafů)|grafy]] shodně nakreslit * [[Problém obchodního cestujícího]] {{Článek z Wikipedie}} [[Kategorie:Třídy složitosti]]

Návrat na stránku „NP (třída složitosti)“.