<p>The best known lower bounds for TSP are essentially the same as those for 3SAT (within polylogarithmic factors), and they apply the fact that there are very efficient reductions from 3SAT to Hamiltonian Path. (So, a good algorithm for Hamiltonian path would imply one for 3SAT, but certain lower bounds show that sufficiently good algorithms don't exist for 3SAT.)</p>

<p>For the best 3SAT lower bounds known, see <a href="https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat/120#120">this answer</a>. The bottom line is that the only non-trivial lower bounds known for these problems impose a <em>space restriction</em> 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).</p>

CC BY-SA 2.5
2011-01-18T15:48:20.617Z
Thanks, a very good read!
I'm off studying these time ans space restrictions :-)
Valmond
CC BY-SA 2.5
2011-01-17T23:12:20.657Z
2011-01-17T23:12:20.657Z
2017-04-13T12:32:28.167Z
Ryan Williams
<p>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.</p>

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

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

<p>Thanks again</p>

CC BY-SA 2.5
2011-01-17T23:03:55.253Z
have you seen this question? http://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat
Lev Reyzin
CC BY-SA 2.5
2011-01-20T04:21:50.400Z
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 http://tinyurl.com/lkyrs2 (also: http://www.tsp.gatech.edu/).
Sariel Har-Peled
<cc.complexity-theory><lower-bounds><np>
Highest lower bound on NP problems (TSP)
Valmond
# Highest lower bound on NP problems (TSP)

(Asked by: username_0 on 2011-01-17)

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

**Tags:** cc.complexity-theory, lower-bounds, np
> **Comments:**
> **username_1**: have you seen this question? http://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat  
> **username_2**: 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 http://tinyurl.com/lkyrs2 (also: http://www.tsp.gatech.edu/).  

---

## 1 answers

### Answer by username_3 on 2011-01-17. Score: 12 | Accepted answer

The best known lower bounds for TSP are essentially the same as those for 3SAT (within polylogarithmic factors), and they apply the fact that there are very efficient reductions from 3SAT to Hamiltonian Path. (So, a good algorithm for Hamiltonian path would imply one for 3SAT, but certain lower bounds show that sufficiently good algorithms don't exist for 3SAT.)

For the best 3SAT lower bounds known, see [this answer](https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat/120#120). 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).

> **Comments:**
> **username_0**: Thanks, a very good read! I'm off studying these time ans space restrictions :-)  

---

