# 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

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