Asymptotically-Optimal Algorithms to Decide NP Problems

[JTHM]

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.

[philoctetes]

Seems like almost any of those we know would do, no? I will now wave my hands like I just don't care:
Say, for SAT, guess a satisfying assignment. Running time is linear, and any sublinear algorithm will fail by some application of the pigeonhole principle.

[Strilanc]

I don't know about optimal, but you can get arbitrarily close to optimal by using variations of the algorithm that takes polynomial time to solve NP problems if and only if P=NP. The constant factors are a bit absurd, though.

The algorithm listed by wikipedia is a factor n away from optimal, since for each step of your program you must pay for a step in n other programs. But if you run smaller programs for longer amounts of time before starting later programs, this cost actually goes down (and your constants become even more absurd). For example, if instead of "for P = 1 to N: run program P for N steps" you used "for P = 1 to N: run program P for 2^N steps" then your running time is a factor log(n) away from optimal.

[WarDaft]

If there is an algorithm that is provably optimal in axiomatic system X, then a Godel machine over those axioms is asymptotically optimal for that problem. It does not particularly matter what complexity category these problems are in.