## Asymptotically-Optimal Algorithms to Decide NP Problems

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

### Asymptotically-Optimal Algorithms to Decide NP Problems

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.
JTHM

Posts: 16
Joined: Sun Apr 22, 2012 4:29 am UTC

### Re: Asymptotically-Optimal Algorithms to Decide NP Problems

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.
philoctetes

Posts: 32
Joined: Tue Feb 19, 2008 3:26 pm UTC

### Re: Asymptotically-Optimal Algorithms to Decide NP Problems

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.
Don't pay attention to this signature, it's contradictory.

Strilanc

Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

### Re: Asymptotically-Optimal Algorithms to Decide NP Problems

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1553
Joined: Thu Jul 30, 2009 3:16 pm UTC