EXPTIME-luokka
Monimutkaisuusluokka EXPTIME (jota joskus kutsutaan yksinkertaisesti EXP) on laskennallisen monimutkaisuuden teoriassa joukko ongelmia, jotka voidaan ratkaista deterministisellä Turingin koneella O (2 p ( n ) ) -ajassa , missä p(n) on polynomifunktio. n.
Ominaisuudet
On tiedossa, että
P NP PSPACE EXPTIME SEURAAVA EXPTIME
Myös en:aikahierarkialauseella ja en:avaruushierarkialauseella
P EXPTIME ; NP NEXPTIME ; PSPACE EXPACE
Katso myös
Kirjallisuus
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .
| Algoritmien monimutkaisuusluokat | |
|---|---|
| Kevyenä pidetty | |
| Taitaa olla vaikeaa | |
| Vaikeaksi pidetty |
|