Klasifikace problémů
m (kategorizace) |
(formátování) |
||
| Řádka 1: | Řádka 1: | ||
| − | Rozhodovací problémy lze dělit do tříd složitosti | + | Rozhodovací problémy lze dělit do tříd složitosti: |
| − | P (polynomiální) - problém je řešitelný pomocí (deterministického) | + | |
| − | NP (nedeterministicky polynomiální) - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který "uhodne" kterou větví se vydat, případně mu něco "napoví" kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení | + | '''P (polynomiální)''' - problém je řešitelný pomocí (deterministického) [http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj Turingova stroje] v Polynomiálním čase (např. problém řazení), lze dokázat, že všechny problémy P jsou podmnožinou problémů skupiny NP (NP problém s jednou větví, NP problém bez hádání či nápovědy) |
| − | NP-těžké - Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací) | + | |
| − | NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy | + | '''NP (nedeterministicky polynomiální)''' - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který "uhodne" kterou větví se vydat, případně mu něco "napoví" kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení odpovídající problému), nikoliv jej získat - pokud bychom všechny větve umístili řekněme do zásobníku (zásobníkový Turingův stroj), čas pro nalezení řešení by nutně nebyl polynomiální. Je otázkou, zda lze pro NP problémy najít P řešení. |
| + | |||
| + | '''NP-těžké''' - Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací) | ||
| + | |||
| + | '''NP-úplné''' - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy | ||
[[Soubor:Np-problemy.jpg]] | [[Soubor:Np-problemy.jpg]] | ||
Aktuální verze z 21. 5. 2015, 19:26
Rozhodovací problémy lze dělit do tříd složitosti:
P (polynomiální) - problém je řešitelný pomocí (deterministického) Turingova stroje v Polynomiálním čase (např. problém řazení), lze dokázat, že všechny problémy P jsou podmnožinou problémů skupiny NP (NP problém s jednou větví, NP problém bez hádání či nápovědy)
NP (nedeterministicky polynomiální) - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který "uhodne" kterou větví se vydat, případně mu něco "napoví" kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení odpovídající problému), nikoliv jej získat - pokud bychom všechny větve umístili řekněme do zásobníku (zásobníkový Turingův stroj), čas pro nalezení řešení by nutně nebyl polynomiální. Je otázkou, zda lze pro NP problémy najít P řešení.
NP-těžké - Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací)
NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy
A dále je tu složitost problémů, viz 6
