When studying the time-hierarchy and space-hierarchy theorems, the main idea is to use a simulation by the universal TM. It is mentioned that the time bound is increased by a logarithmic factor while the space bound remains the same.

I still can't figure out why, as most of the answers I've found to similar questions involve a multitape TM, while the complexity is determined by the bounds of a single-tape TMs and the time bound is known to strictly increase when converting a multitape TM to a single-tape one.

What am I missing here?


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.