EXPTIME klass
EXPTIME-komplexitetsklassen (ibland kallad helt enkelt EXP) är en uppsättning problem, i beräkningskomplexitetsteori, som kan lösas av en deterministisk Turing-maskin i O (2 p ( n ) ) tid, där p(n) är en polynomfunktion av n.
Egenskaper
Det är känt att
P NP PSPACE EXPTIME NEXPTIME EXPSPACE
Också genom en:time hierarkisatsen och en:space hierarkisatsen
P EXPTIME ; NP NEXPTIME ; PSPACE EXPSPACE
Se även
Litteratur
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M . : "Williams" , 2002. - 528 sid. - ISBN 0-201-44124-1 .
| Komplexitetsklasser av algoritmer | |
|---|---|
| Anses som ljus | |
| Ska vara svårt | |
| Anses vara svårt |
|