I recall seeing a result showing that multi-tape DTIME[T] is strictly contained in random-access NTIME[T] for reasonably large T (so not the PPST proof with the $\log^\star$ sort of factors), but I can’t find it. Does such a result exist?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.