# Highest lower bound on NP problems (TSP)

I'll try another question that I haven't been able to find almost any kind of information about, thanks a lot for any kind of pointers or explanations.

Is there a list of the proven lower bounds of NP algorithms (particularly for the TSP problems)?

Like one might imagine that someone already has proven 3SAT to run at at least 2n² for example.

Thanks again

• have you seen this question? cstheory.stackexchange.com/questions/93/… Jan 17 '11 at 23:03
• TSP might not be the best problem to look at as far as NP-Completeness and lower bounds, since in practice it can be solved quite efficiently for very large instances tinyurl.com/lkyrs2 (also: tsp.gatech.edu). Jan 20 '11 at 4:21

For the best 3SAT lower bounds known, see this answer. The bottom line is that the only non-trivial lower bounds known for these problems impose a space restriction on the candidate algorithm, as well as a time restriction. So for example, we can say TSP cannot be solved in $n^{1.5}$ time and $O(log n)$ space, but we don't know if TSP can be solved in $n^{1.5}$ time (with no space restriction).