Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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
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).
