Hello, XKCD computer scientists. I have a question:
Has any algorithm for a non-deterministic Turing machine which decides some problem that is in NP but demonstrably not in P, assuming P != NP, been proven to be asymptotically optimal? I can't seem to find an answer to this question anywhere on the Internet.
Bonus points if you can also prove that for every complexity class NEXPTIME, N2-EXPTIME, N3-EXPTIME, etc, there exists some problem in it, but not in EXPTIME, 2-EXPTIME, 3-EXPTIME, etc., provided that EXPTIME != NEXPTIME, 2-EXPTIME != N2-EXPTIME, 3-EXPTIME != N3-EXPTIME, etc., for which an asymptotically optimal algorithm deciding it exists.