Re: Innovation, my TSP algorithm and factoring, timelines

JSH wrote:


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.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth