NP-úplnost: Porovnání verzí

Odebráno 42 bajtů ,  před 15 lety
m
robot: stylistické, typografické a kódové korekce a náhrady přesměrování podle specifikace
m (robot přidal: sv:NP-fullständig)
m (robot: stylistické, typografické a kódové korekce a náhrady přesměrování podle specifikace)
'''NP-úplné''' ('''NP-complete''', '''NPC''') problémy jsou takové [[nedeterministicky polynomiální problém|nedeterministicky polynomiální problémy]]y, na které jsou [[polynomiální redukce|polynomiálně redukovatelné]] všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty ''nejtěžší'' úlohy z NP. Pokud by byl nalezen deterministický polynomiální algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že ''všechny'' nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“„zhroutí“ do třídy P (NP = P). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP).
 
Vztah mezi P a NP je jedním ze sedmi problémů tisíciletí, které vypsal Clay Mathemathics Institute [[24. květen|24. května]] [[2000]], za rozhodnutí vztahu nabízí 1 000 000 dolarů.
 
== Příklady NP-úplných úloh ==
42 548

editací