EXPTIME klasse

EXPTIME kompleksitetsklassen (nogle gange blot kaldet EXP) er et sæt af problemer, i beregningskompleksitetsteori, der kan løses af en deterministisk Turing-maskine i O (2 p ( n ) ) tid, hvor p(n) er en polynomisk funktion af n.

Egenskaber

Det er kendt, at

Også ved en:time hierarkisætning og en:space hierarkisætning

Se også

• Eksponentiel kompleksitet

Litteratur

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .