In complexity theory we have Borodin's theorem as follows: enter image description here

I do not get what the consequence is. So, wikipedia told me that there are arbitrarily large gaps between the complexity classes. Isn't that what the hierarchy theorem tells us already? Anyways, here we look at $DTIME(r\circ s)$, which I understand as a "higher" complexity class than $DTIME(r)$. And these two are equal. So actually I would understand it as that a higher class can be made arbitrarily small. But the theorem claims the opposite. So, my question is: Where is the link to the consequence that the gap can be made arbitrarily large?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.