6

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

Valmond
  • 165
  • 5
  • 3
    have you seen this question? http://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat – Lev Reyzin 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 http://tinyurl.com/lkyrs2 (also: http://www.tsp.gatech.edu/). – Sariel Har-Peled Jan 20 '11 at 04:21

1 Answers1

12

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

Community
  • 1
Ryan Williams
  • 27,465
  • 7
  • 115
  • 164