The authors separate nondeterministic and deterministic complexity classes as well as alternating and nondeterministic complexity classes for one-head and multihead Turing machines. In doing so, they consider the product of time and space as a combined complexity measure. In Section 3, they show that for one-head Turing machines,
( NTM ( 1 ) - TIME × SPACE ( n log n ) ) -
( DTM ( 1 ) - TIME × SPACE ( O ( n 2 ) ) ) ≠ 0
and ( ATM ( 1 ) - TIME × SPACE ( n log n ) ) -
( NTM ( 1 ) - TIME × SPACE ( O ( n 2 ) ) ) ≠ 0
. As a consequence, for Turing machines working in the logarithmic space, ( NLOG - TIME ( n ) ) -
( DLOG - TIME ( O ( n 2 &slash; log n ) ) ) ≠ 0
and ( ALOG - TIME ( n ) ) -
( NLOG - TIME ( O ( n 2 &slash; log n ) ) ) ≠ 0
The main result obtained in the second part of the paper (Section 4) is the following. Let M be one of the DTM(1), NTM(1), or ATM(1) models, let a ( n ) be a computable function, and let b ( n ) be a function such that b ( n ) = O ( a ( n 2 )). Then ( M - TIME × SPACE ( a 2 ( n ) ) ) -
( M - TIME × SPACE ( b ( n ) ) ) ≠ 0
The authors obtain similar results for multihead Turing machines.
