NTIME

from Wikipedia, the free encyclopedia

In complexity theory is NTIME ( f ) for the set of languages that of a non-deterministic Turing machine in time O ( f ) accepted to be.

Using NTIME , the following complexity classes are defined or characterized, among others:

Q = NTIME ( n ) (Formally, Q is defined as a family of all languages L with L = L (M) , where every computation of M on input w requiresat most | w | steps. A previous source also shows that this class with NTIME (n) coincides.)
NP : = NTIME ( n ^k ) ${\ displaystyle \ bigcup _ {k = 0} ^ {\ infty}}$

NE : = NTIME (2 ^{O ( n )} )

NEXP : = NTIME (2ⁿ^{^k} ) ${\ displaystyle \ bigcup _ {k = 0} ^ {\ infty}}$

By means of diagonalization it can be shown that the subset relationships in the hierarchy Q ⊂ NP ⊂ NE ⊂ NEXP are real .

Web links

NTIME . In: Complexity Zoo. (English)

Individual evidence

↑ Ronald V. Book, Sheila A. Greibach: Quasi-realtime languages (Extended Abstract) . ACM, pp. 15-18. doi : 10.1145 / 800169.805416