Reply to thread

Message: [QUOTE="Joshua Cranmer, post: 3617196"] You seem to be missing one key fact about NP-complete algorithms. Any NP problem may be convertible to an NP-complete problem, but the conversion is typically expensive. Here's an example. I wrote a Turing machine to add two numbers. Five state, four symbol. It takes O(3*n lg n) (where n is the number of bits of the larger number) (the constant may be higher, I did the math well over a year ago and I never checked it) steps and uses up O(2*n) slots (I'm throwing in some constants here). By Cook's Theorem, the SAT query will then O(30*n^2 lg n + 15*n lg n) variables and a few hundred times that number of clauses, let's say 100. Transforming to clique, we get the multiplication of these two number of nodes and a triangular (i.e. 1/2n^2) number of edges for nodes. Up to O(3000*n^4 lg n) nodes/O(4500000n^8 lg^2 n) edges. Converting to vertex cover just takes the complement of the graph, so node size stays the same and the edge size should still stay roughly the same size. We now construct a graph with the node size that is twice the number of nodes times the average degree, which should be about N/2 by this point, or another triangular relationship, plus the number of edges, so that we get to about O(9e6*n^8 lg^2 n) nodes. The number of edges by this point becomes too difficult to explain, but, naturally, it's even larger. This graph we solve for the existence of a directed Hamiltonian circuit; triple the number of nodes and make the number of edges equal to 2 * old_node + old_edge for an undirected Hamiltonian circuit. So far, everything was from Karp's paper; since he doesn't mention TSP as NP-complete, I'm shifting to another resource for the TSP graph construction. Here, we keep the node graph and make each edge 1 if it exists in our previous graph or 2 if it didn't (so the edges from the last part don't matter). So, even if we had an O(|V|^5) algorithm for generic TSP with a low constant, our small O(3*n lg n) algorithm becomes O(1.4e37*n^40 lg^10 n) if we attempt to use the algorithm based on the various proofs of NP-completeness. Remember, this is only a 5-state, 4-symbol Turing machine. Also, this doesn't take into account the actions you have to take to *unroll* all the conversions. Finally, these are based on reductions of *decision* problems, but actually solving it is a different class of problem. I believe the function problem equivalents should have identical reductions, though. My tortured point is this: most proofs that an algorithm is NP-complete do so by taking a pre-existing NP-complete algorithm and roughly squaring its complexity (or worse!). So even though the algorithm is polynomial, since it's been forced through many successive stages of conversion, it becomes intractable. So, here's my challenge to you: show us how to construct a graph such that it's TSP solution factors the number. [/QUOTE]

Verification