NTIME

In complexity theory is NTIME ( f ) for the set of languages ​​that can be accepted by a nondeterministic Turing machine in time O (f).

Among others, the following complexity classes are defined by means of NTIME:

  • Q: = NTIME ( n )
  • NP: = NTIME (nk)
  • NE: = NTIME ( 2O ( n ) )
  • NEXP: = NTIME ( 2nk )

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

Non-deterministic Turing machine NEXPTIME
610462
de