Please enable JavaScript.
Coggle requires JavaScript to display documents.
15. Složitost (Složitostní třídy (NP (př (HAMPATH (hledání cesty v grafu,…
15. Složitost
-
Složitostní třídy
NP
třída problémů, které lze řešit v polyn. čase na NEDET. TM
pokud je předloženo řešení, jsme ho schopni v rozumném čase ověřit
pokud bychom měli nek. PC, které by vyřešily všechny možnosti ve stejném čase - najdeme řeš. v polyn. čase
alg., které zahrnují rozhodování (nalézt cestu v grafu, plánování, sudoku,...)
-
př
HAMPATH
hledání cesty v grafu, na které navštívíme každý vrchol právě jednou
Klikovost grafu (klika = v neor. grafu, podgraf - ex. hrana mezi každými 2 uzly)
-
-
P
třída problémů, které jsou řešitelné DET. TM v polynom. čase (polyn. počet kroků)
alg. s čistým a přímým řešením (násobení, řazení, hledání prvočísel,...
-
problém patří do P
navrhnout det. TM, který řeší daný problém + postupně analyzovat jeho složitost
ukázat, že problém je řeš. v polyn. počtu kroků + každý z nich je impl. v polynom. čase
př.: řazení, hledání prvočísel
-
-
-
-
dělení na základě času a paměti, které alg. potřebují ke svému vykonání na různých typech TM
P ?= NP
-
NP - oveřím řešení, P - rychle najdu
NP-úplné
-
pokud bychom našli rychlý program pro řešení nějakého NPC problému, pak bychom mohli najít rychlý program pro řešení jakéhokoliv NPC problému
-
využití: kryptografie (rychlé ověření správnosti řešení), nalezení může trvat dlouho
-
-
-
NP-těžké
pokud se na ní redukuje NP-úplná úloha, ale nevíme, jestli je v NP
-
alespoň tak těžké, jako NP-úplné
PSPACE
problémy řešitelné při možnosti nekonečného času, ale pouze polyn. prostor (paměť)
jazyk L je ve třídě PSPACE právě tehdy, když ex. deter. TM, který pracuje s polyn. paměťovou slož. a přijímá L
-
NPSPACE
jazyk L je ve třídě PSPACE právě tehdy, když ex. nedet. TM, který pracuje s polyn. paměťovou slož. a přijímá L
-
-
-
-
-
-
-
-