6
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, a very good read! I'm off studying these time ans space restrictions :-) $\endgroup$ – Valmond Jan 18 '11 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.