Besides my open source Class Viewer project I have a rep for throwing
ideas out on Usenet, where I did that for years with math, argued with
a lot of math people, and they hate me, but that's a side issue to the
subject of this post as I was wondering today what problem I might
solve to kind of prove myself and came up with an algorithm for the
traveling salesman problem.

My algorithm has TWO travelers: the forward traveler and the backwards
traveler.

Where to understand the idea I don't have the traveler get back to his
original destination at first, though that's easily added later.

The backwards traveler is actually the same traveler, but traveling
backwards in time along the optimal path, so the assumption is that
the problem is solved, but so what?  What good is a backwards traveler
added with the normal forward traveler?

Well, now you can optimize the path from both ends simply enough:
with nodes and paths like normal, assume your forwards traveler is at
the start while your backwards traveler is at the end.

Now the forwards traveler steps forward to a node, doesn't matter
which one so say the closest to keep it simple.  The backwards
traveler then BACKS to each node that is left in turn, and at each
calculates the time from that node--he's traveling backwards in time--
and multiplies that for each node times its straight line distance to
the forwards traveler at his node.

Then the backwards traveler just picks whichever node has the minimum
time*straight-line distance value, and holds that value.

The forwards traveler now goes to another node, and the backwards
traveler does the same thing as above, and they do this process until
each first possible step is covered.

So now there is a series of values for each node for the forwards
traveler, and he picks the one that is minimal, and then each traveler
steps to the appropriate node for that path, which notice is covering
the ends of your total path.

And then they do the same process again.

As they iterate through, they must eventually meet, so the forward
times traveler meets himself going backwards through time and you have
the minimal path--I hope.

You need one more rule: each node is only visited once, so as each
node is visited paths to it are removed.

And that's it.

Looking over literature quickly while checking to see if anyone else
already had this algorithm, I noticed that no one did and that the
algorithms I saw looked forward only, while this approach chops the
problem up iteratively from both sides, so you're solving it at both
ends.

The algorithm itself is polynomial time, as if there are m+2 nodes,
where 2 of them are the starting and ending nodes then the first
iteration has (m-1)^2 value calculations, while the second has (m-3)^2
and so forth.

The idea is generalizable to other limiting factors like cost, as you
just multiply everything together, so like to get the shortest
possible path in the shortest time with the shortest cost, you'd
multiply distance*time*cost for each path and take the minimum.

Oh yeah, so how do you do the classical problem of getting back to
your original destination?

Easy.  Both travelers start from the same point, and otherwise
everything is the same.

The proof that it is a solution has to do with other stuff more
mathematical so I leave that off, as even if you don't think it does,
how hard is that idea to program, eh?

And now you know how I got hated by mathematicians with my wild ideas
and extreme creativity.

Mathematicians around the world DESPISE me for posts like this one as
they see them as insulting to think that I could dare to solve a hard
and difficult problem that brilliant people have worked on for years.

But I say, why can't I just toss some ideas out there?  What really is
so wrong with that?

So I think math people are the ones with the problem.  Not me.


James Harris

JSH wrote:
> Besides my open source Class Viewer project I have a rep for throwing
> ideas out on Usenet, where I did that for years with math, argued with
> a lot of math people, and they hate me, but that's a side issue to the
> subject of this post as I was wondering today what problem I might
> solve to kind of prove myself and came up with an algorithm for the
> traveling salesman problem.
....

Your algorithm looks rather more like a shortest path algorithm than a
traveling salesman algorithm. How do you ensure that *every* node is
visited in the solution?

Patricia

On Jul 15, 12:33=A0am, JSH <jst...@gmail.com> wrote:
> Besides my open source Class Viewer project I have a rep for throwing
> ideas out on Usenet, where I did that for years with math, argued with
> a lot of math people, and they hate me, but that's a side issue to the
> subject of this post as I was wondering today what problem I might
> solve to kind of prove myself and came up with an algorithm for the
> traveling salesman problem.
>
> My algorithm has TWO travelers: the forward traveler and the backwards
> traveler.

*massive snip*

comp.programming would be a better forum for discussion of algorithms.
comp.lang.java.programmer is concerned with the implementation details
as they apply to Java. Followup-To set appropriately.

However, I will say this: your algorithm is incomplete, as Patricia
noted; it also relies on several concepts with no solid definition
within the scope of the problem, like "straight-line distance"[0]. You
may also have confused yourself by thinking in terms of "backwards in
time" -- walking a graph to construct a path is the same operation no
matter how you choose to look at the graph data. Finally, the phrase
"I hope" does not constitute formal proof, and since this is your
algorithm, you are responsible for formally proving that it is
complete and has the complexity you think it does.

-o

[0] However, this is awfully suggestive of the "heuristic" employed in
A* and other informed path search algorithms. You may be reinventing
the wheel.

On Jul 15, 12:33 am, JSH <jst...@gmail.com> wrote:

[snippage throughout]

> My algorithm has TWO travelers: the forward traveler and the backwards
> traveler.

> Well, now you can optimize the path from both ends simply enough:
> with nodes and paths like normal, assume your forwards traveler is at
> the start while your backwards traveler is at the end.

Since you don't know the optimal path, how do you know which city is
"at the start" and which is "at the end?"

> Now the forwards traveler steps forward to a node, doesn't matter
> which one so say the closest to keep it simple.  The backwards
> traveler then BACKS to each node that is left in turn, and at each
> calculates the time from that node--he's traveling backwards in time--
> and multiplies that for each node times its straight line distance to
> the forwards traveler at his node.
>
> Then the backwards traveler just picks whichever node has the minimum
> time*straight-line distance value, and holds that value.
>
> The forwards traveler now goes to another node, and the backwards
> traveler does the same thing as above, and they do this process until
> each first possible step is covered.

It's not very clear what you're trying to say here, but this sounds
to me like a simple brute force search.  I don't think that's going
to be very efficient.

> As they iterate through, they must eventually meet, so the forward
> times traveler meets himself going backwards through time and you have
> the minimal path--I hope.

As Patricia noted, there's nothing here that guarantees every city
will be visited.  It sounds more like they just move toward each
other and stop when they meet.

> You need one more rule: each node is only visited once, so as each
> node is visited paths to it are removed.

What about the cities that remain after they meet?

> Oh yeah, so how do you do the classical problem of getting back to
> your original destination?
>
> Easy.  Both travelers start from the same point, and otherwise
> everything is the same.

Since they both seem to be using the same algorithm to select the
next (or "previous") city, why would they move to different cities
if they start at the same one?  And even if they did, wouldn't they
move just one city each, and then right back to the start, ending
the algorithm after only visiting three cities?

> And now you know how I got hated by mathematicians with my wild ideas
> and extreme creativity.

I don't think mathematicians hate you.  But you do often claim to have
a proof, as you do in this article, when you don't have one at all.
When people point that out, you call them liars.

On Jul 14, 9:51=A0pm, Patricia Shanahan <p...@acm.org> wrote:
> JSH wrote:
> > Besides my open source Class Viewer project I have a rep for throwing
> > ideas out on Usenet, where I did that for years with math, argued with
> > a lot of math people, and they hate me, but that's a side issue to the
> > subject of this post as I was wondering today what problem I might
> > solve to kind of prove myself and came up with an algorithm for the
> > traveling salesman problem.
>
> ...
>
> Your algorithm looks rather more like a shortest path algorithm than a
> traveling salesman algorithm. How do you ensure that *every* node is
> visited in the solution?
>
> Patricia

Yeah I forgot to put in a crucial condition--which I had in mind--
which is that the two travelers do not travel to, nor consider the
same node at the same time.  So, for instance, if you had only three
nodes, with the travelers at nodes at either end and one node in the
middle, then you'd exit as neither traveler could move, and that may
be a typical exit state.

The other exit would be if each traveler is at their own node and no
other nodes are available, but then you have the full path anyway.

Regardless of whether this idea solves the problem it's interesting to
consider the path that you'd get with the algorithm, which I'll
formalize better here:

Given two travelers T_1 and T_2 and m nodes N, where m is a natural
number, each traveler can be at a particular node, and each node has a
distance from every other node in the space.  There is also a value
associated with the path from each node to another, which for
simplicity can be considered to be the time of travel from that node
to the other.

For instance, if it takes two hours to go from N_1 to N_2, then that
time is what's used in considered a traveler at N_1 considering going
to N_2.

Assume T_1 is at N_1 and T_2 is at N_m.  For the first iteration T_1
considers moving to N_2, and then T_2 considers moving to each node in
turn EXCEPT N_1 or N_2 as it excludes the node that T_1 is already at,
and also excludes the one being considered.

For each potential move T_2 calculates the time from N_m to that node
and then it calculates the straight line distance to T_1 at N_2--not
at N_1, as it is checking where T_1 will be--and it multiplies the
time for that move times the distance to T_1, and stores that data.

After T_2 has gone through every possible it simply takes the one that
is smallest time*distance, and stores that info.

Now T_1 considers moving to another node, like N_3, to keep it simple,
and T_2 does the same calculation again, and stores the smallest
time*distance.

This process continues until all possible moves by T_1 are done, and
now T_1 has a set of times*distance values from the calculations by
T_2, and selects the smallest one.

Now both T_1 and T_2 actually move to their respective nodes given by
that smallest value.

Now nodes N_1 and N_m are removed from consideration.

And you have a complete iteration.

Note that you have (m-2)^2 checks, if the travelers start at different
nodes, for the first iteration and (m-4)^2 for the next and so forth,
so the algorithm is polynomial time.

T_1 and T_2 continue until there are no more nodes available or there
is only one node available.

Note that in the latter case then EITHER can move to complete, so you
can arbitrarily say that T_1 moves forward in that case.

And that is how every node is reached.

Note: To have a complete circle back to a starting point, you have
both T_1 and T_2 start at the same node, like N_1.

So that's the more abstract explanation.  The fuller one was given
before where T_1 is the forwards traveler and T_2 is the backwards
traveler going backwards in time.

Intriguingly, this approach can lead to a shortest path algorithm with
some rule adjustments, but I won't digress on that point now.

I am seriously thinking of programming a Java implementation and
putting it on Google Code.

It would be nice to have help.


James Harris

Patricia Shanahan wrote:
>> Your algorithm looks rather more like a shortest path algorithm than a
>> traveling salesman algorithm. How do you ensure that *every* node is
>> visited in the solution?

JSH wrote:
> Yeah I forgot to put in a crucial condition--which I had in mind--
> which is that the two travelers do not travel to, nor consider the
> same node at the same time.  So, for instance, if you had only three
> nodes, with the travelers at nodes at either end and one node in the
> middle, then you'd exit as neither traveler could move, and that may
> be a typical exit state.

You just provided the example that proves Patricia's objection is valid.  It 
shows that your algorithm does not solve the Traveling Salesman problem in 
what is nearly the simplest case.

-- 
Lew

On Jul 15, 6:14=A0pm, Lew <l...@lewscanon.com> wrote:
> Patricia Shanahan wrote:
> >> Your algorithm looks rather more like a shortest path algorithm than a
> >> traveling salesman algorithm. How do you ensure that *every* node is
> >> visited in the solution?
> JSH wrote:
> > Yeah I forgot to put in a crucial condition--which I had in mind--
> > which is that the two travelers do not travel to, nor consider the
> > same node at the same time. =A0So, for instance, if you had only three
> > nodes, with the travelers at nodes at either end and one node in the
> > middle, then you'd exit as neither traveler could move, and that may
> > be a typical exit state.
>
> You just provided the example that proves Patricia's objection is valid. =
=A0It
> shows that your algorithm does not solve the Traveling Salesman problem i=
n
> what is nearly the simplest case.
>
> --
> Lew

Her question was actually right on point as how I originally stated
the idea, it turns out that the travelers would always just go to each
other's nodes as you multiply the distance from the node times the
time to travel, so if one traveler goes to the node of the other, then
you multiply by 0.

So I don't think she was making your objection though as trivially, as
I mentioned in my reply to her, you simply move either traveler to the
middle node.

Regardless though of whether or not the very famous and huge Traveling
Salesman Problem is solved there is the intriguing question now of,
how will this algorithm behave with a large dataset.

It WILL traverse every node--with the final step of having to step one
of the travelers at the end for one special case--but what patterns
might you see?

The great thing is that it should be easy to program!

So, short answer is, no, I don't think your objection has anything to
do with Patricia's question, though if I'm wrong in that belief, I've
answered that objection. While the behavior of this algorithm is to
step through every node--with the special case handled--and there's a
question of how it will do so, but it's easy to program so rather than
debate what it will do, I'm more interested in programming the thing.

And it looks like I'll do it myself, but that's ok.  If anyone wants
to help though, I've put the invite out there and put up a project on
Google Code, which will be in java.

All neat and tidy I think as I should have covered every base with
this reply.


James Harris

JSH <jstevh@gmail.com> writes:

> But I say, why can't I just toss some ideas out there?  What really is
> so wrong with that?

Nothing except that you waste people's time by throwing out half-baked
ideas for problems that you don't appear to understand the complexity
of.

I.e., I'm pretty certain your idea won't solve the problem, but the
description is too vague to say anything specific about where it fails.

/L
-- 
Lasse Reichstein Nielsen
 DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
  'Faith without judgement merely degrades the spirit divine.'

JSH wrote:
....
> Regardless though of whether or not the very famous and huge Traveling
> Salesman Problem is solved there is the intriguing question now of,
> how will this algorithm behave with a large dataset.
....

I think, in order for that to be interesting, you do need to define what
problem your algorithm is intended to solve. It does not have to be
Traveling Salesman, but it does need to be a defined problem whose
solution might have some use.

Patricia

On 16 Jul, 01:26, JSH <jst...@gmail.com> wrote:
>
> [...]
>
> Regardless of whether this idea solves the problem it's interesting to
> consider the path that you'd get with the algorithm, which I'll
> formalize better here:
>
> Given two travelers T_1 and T_2 and m nodes N, where m is a natural
> number, each traveler can be at a particular node, and each node has a
> distance from every other node in the space.  There is also a value
> associated with the path from each node to another, which for
> simplicity can be considered to be the time of travel from that node
> to the other.
>
> For instance, if it takes two hours to go from N_1 to N_2, then that
> time is what's used in considered a traveler at N_1 considering going
> to N_2.
>
> Assume T_1 is at N_1 and T_2 is at N_m.  For the first iteration T_1
> considers moving to N_2, and then T_2 considers moving to each node in
> turn EXCEPT N_1 or N_2 as it excludes the node that T_1 is already at,
> and also excludes the one being considered.
>
> For each potential move T_2 calculates the time from N_m to that node
> and then it calculates the straight line distance to T_1 at N_2--not
> at N_1, as it is checking where T_1 will be--and it multiplies the
> time for that move times the distance to T_1, and stores that data.
>
> After T_2 has gone through every possible it simply takes the one that
> is smallest time*distance, and stores that info.
>
> Now T_1 considers moving to another node, like N_3, to keep it simple,
> and T_2 does the same calculation again, and stores the smallest
> time*distance.
>
> This process continues until all possible moves by T_1 are done, and
> now T_1 has a set of times*distance values from the calculations by
> T_2, and selects the smallest one.
>
> Now both T_1 and T_2 actually move to their respective nodes given by
> that smallest value.
>
> Now nodes N_1 and N_m are removed from consideration.
>
> And you have a complete iteration.
>
> Note that you have (m-2)^2 checks, if the travelers start at different
> nodes, for the first iteration and (m-4)^2 for the next and so forth,
> so the algorithm is polynomial time.
>
> T_1 and T_2 continue until there are no more nodes available or there
> is only one node available.
>
> Note that in the latter case then EITHER can move to complete, so you
> can arbitrarily say that T_1 moves forward in that case.
>
> And that is how every node is reached.

I have a couple of questions about your algorithm. First, the
statement of the travelling salesman problem involves a graph with a
single weight associated to each edge, i.e. a single number for every
pair of distinct nodes. However in describing your algorithm you talk
about two quantities, namely the time taken to travel between two
nodes and the straight line distance between two nodes. I suppose from
reading your description that the times are given by the weights of
the graph, is this correct? If so, how do you define the distances?
Are they simply directly proportional to the times, or are they given
by some other function of the times (say s = f(t)), or are they even
completely independent of the times? If they are directly proportional
to the times, then why introduce them at all? On the other hand if
they are not, then I don't see how you can think your algorithm solves
the problem - since different choices of f or of the distances will
mean different outputs of the algorithm, but the actual solution to
the problem is independent of such choices.

My second question is, assuming that the distances are directly
proportional to the times, are you assuming that the input data of
your algorithm corresponds to some arrangement of nodes in some metric
space (which will be false if, e.g. the distances fail to satisfy the
triangle inequality)? If not then I don't see how the straight line
distance as it is used in your algorithm is relevant to the problem.

On Jul 15, 8:26 pm, JSH <jst...@gmail.com> wrote:
> Intriguingly, this approach can lead to a shortest path algorithm with
> some rule adjustments, but I won't digress on that point now.

So, the algorithm you've described does *not* find the shortest
path?  Then in what sense does it solve the Traveling Salesman
problem, which is precisely to find the shortest path?

Also, James, this is probably not going to sink in, but the Traveling
Salesman problem, like the "factoring problem," has already been
solved.  It's trivial to describe algorithms that will solve either
problem.  If you want to be seen as making progress with either of
them, you need to come up with a new, *fast* algorithm.

Lits O'Hate wrote:
> On Jul 15, 8:26 pm, JSH <jst...@gmail.com> wrote:
>> Intriguingly, this approach can lead to a shortest path algorithm with
>> some rule adjustments, but I won't digress on that point now.
> 
> So, the algorithm you've described does *not* find the shortest
> path?  Then in what sense does it solve the Traveling Salesman
> problem, which is precisely to find the shortest path?

Shortest path is a different, and much easier, problem for which
efficient algorithms are already known.

Wikipedia gives the following informal problem statement for Traveling
Salesman: "Given a number of cities and the costs of traveling from any
city to any other city, what is the least-cost round-trip route that
visits each city exactly once and then returns to the starting city?"
[http://en.wikipedia.org/wiki/Traveling_salesman_problem#Problem_statement]

Patricia

On Jul 15, 10:15=A0pm, Lasse Reichstein Nielsen <l...@hotpop.com> wrote:
> JSH <jst...@gmail.com> writes:
> > But I say, why can't I just toss some ideas out there? =A0What really i=
s
> > so wrong with that?
>
> Nothing except that you waste people's time by throwing out half-baked
> ideas for problems that you don't appear to understand the complexity
> of.

Sigh.

> I.e., I'm pretty certain your idea won't solve the problem, but the
> description is too vague to say anything specific about where it fails.
>

Then wander off and save your time for something else.  Please.


James Harris

On Jul 15, 10:20=A0pm, Patricia Shanahan <p...@acm.org> wrote:
> JSH wrote:
>
> ...> Regardless though of whether or not the very famous and huge Traveli=
ng
> > Salesman Problem is solved there is the intriguing question now of,
> > how will this algorithm behave with a large dataset.
>
> ...
>
> I think, in order for that to be interesting, you do need to define what
> problem your algorithm is intended to solve. It does not have to be
> Traveling Salesman, but it does need to be a defined problem whose
> solution might have some use.
>
> Patricia

It is a an algorithm for the Traveling Salesman Problem, though I
avowed that whether or not it solved it, there is the question of what
patterns it would present for the people who just like playing with
ideas!

That is, since I know the TSM is mega famous and solving it proves a
Millennium Prize problem about NP complete, I wanted to just distract
from that useless extra to focus on the interesting question of the
algorithm itself.

Maybe you still don't understand how it works?

Ok, then, consider a very simple set of only 4 nodes, with T_1, the
forward in time traveling salesman, starting at N_1, and T_2, the
backwards in time traveling salesman starting at N_4, where all nodes
are connected, and N_2 and N_3 are in the middle equidistant from N_1
and N_4.

If it's easiest imagine a square on a node so it's like a diamond, and
N_1 is at the bottom, N_4 is at the top, and N_2 and N_3 are on the
outer edges, where each node then is a unit distant from the others
along the edges and sqrt(2) units along the diagonals.

Now there is a 1 hour travel time to N_1 from N_2, and the same from
N_1 to N_3, but there is a 2 hour travel time from N_2 to N_4, and a 1
hour travel time from N_3 to N_4, while there is a 1 hour travel time
for N_3 to N_2, and also 1 hour from N_2 to N_3.

(To keep things simple I'm mostly consider travel times in one
direction only, but the middle nodes are kind of important so I
mentioned both directions.)

Ok, so T_1 considers N_2 and stops, as T_2 now can't go to N_2 because
T_1 is considering it, so T_2 considers N_3 and sees a 1 hour travel
time from N_3 to N_4 as T_2 is going BACKWARDS in time, so T_2 doesn't
consider N_4 to N_3, but the opposite.  At N_3 T_2 sees it is sqrt(2)
units away from T_1 if T_1 goes to N_2, so you have

1*sqrt(2) =3D sqrt(2)

which is the total for that move.

And T_2 now has no more moves, so T_1, now considers going to N_3, so
T_2 can only consider N_2, and sees a 2 hour travel time from N_2 to
N_4, and a distance, again of sqrt(2) units from T_1, so now you have

2*sqrt(2) =3D 2sqrt(2).

Now T_2 is done, so T_1 consider the choices and picks the first as
it's the minimum, and now BOTH travelers move and T_1 goes to N_2 and
T_2 goes to N_3, and now the algorithm exits as no more moves are
possible.

But notice, because T_1 is moving forwards in time, and T_2 is moving
backwards in time, you now correct to a single traveler moving
forwards in time from N_1 to N_2, to N_3 and finally to N_4 completing
a least time circuit.

Hopefully a simple example will help.  I suggest people ponder that
example carefully to understand how the algorithm works before
replying further.

It is an algorithm for the Traveling Salesman Problem and it does
cover every node (there is a special case if you have three nodes with
both salesman at either end and one node in the middle!), but it is
highly imaginative and VERY creative, requiring that you think outside
the box, so it can be a little slippery to understand.

I'm using two variables where traditionally there is one, but I'm
doing so with a trick!!!

There really is only one salesman: I get two by having the salesman
travel back in time to meet himself.

If you aren't imaginative it will just sound like weird nonsense.  If
you are, then consider joining my project please and helping me
program this wildly creative solution.


James Harris

JSH wrote:
> If you aren't imaginative it will just sound like weird nonsense.  If
> you are, then consider joining my project please and helping me
> program this wildly creative solution.

That is a pitch that kills any residual interest I might have had in your 
idea.  It is strongly reminiscent of "The Emperor's New Clothes" by Hans 
Christian Andersen, in which anyone who couldn't see the (fictitious) cloth 
was told that they were unfit for their position.

I am very imaginative, but your ideas sound like nonsense (not weird) to me, 
at least since you made that remark about those who don't get the brilliant 
genius of your "wildly creative [non-]solution".

You set off my B.S. alarms big-time with that weird nonsense.

-- 
Lew

JSH wrote:
> Then wander off and save your time for something else.  Please.

Right back atcha, big guy.

-- 
Lew

JSH wrote:
> On Jul 15, 10:20 pm, Patricia Shanahan <p...@acm.org> wrote:
>> JSH wrote:
>>
>> ...> Regardless though of whether or not the very famous and huge Traveling
>>> Salesman Problem is solved there is the intriguing question now of,
>>> how will this algorithm behave with a large dataset.
>> ...
>>
>> I think, in order for that to be interesting, you do need to define what
>> problem your algorithm is intended to solve. It does not have to be
>> Traveling Salesman, but it does need to be a defined problem whose
>> solution might have some use.
>>
>> Patricia
> 
> It is a an algorithm for the Traveling Salesman Problem, though I
> avowed that whether or not it solved it, there is the question of what
> patterns it would present for the people who just like playing with
> ideas!
> 
> That is, since I know the TSM is mega famous and solving it proves a
> Millennium Prize problem about NP complete, I wanted to just distract
> from that useless extra to focus on the interesting question of the
> algorithm itself.

I don't care about the prize, just getting a definition of the problem
your algorithm is intended to solve. Do you agree with the Wikipedia
problem description?

"Given a number of cities and the costs of traveling from any city to
any other city, what is the least-cost round-trip route that visits each
city exactly once and then returns to the starting city?"

> Maybe you still don't understand how it works?

No, I don't understand it. In particular, I am confused by the
introduction of square roots. There is nothing in the definition of TSP
that requires the travel cost between two cities to have anything at all
to do with their distance in a Euclidean space.

Patricia

JSH wrote:
> That is, since I know the TSM is mega famous and solving it proves a
> Millennium Prize problem about NP complete, I wanted to just distract
> from that useless extra to focus on the interesting question of the
> algorithm itself.

Several notes about traveling salesman:
1. The three-letter abbreviation is generally accepted to be "TSP", not 
"TSM" (just a little nit). Also, you're missing a few hyphens, but those 
are just little things.
2. TSP is already solved: I can write a brute-force algorithm that 
solves the problem. It's combinatorical, but it's a solution nonetheless.
3. For all practical purposes, TSP has fast algorithms that generate 
good solutions, even if not optimal.
4. I've always personally believed that, if P = NP, the polynomial 
algorithm would be found for SAT or 3-SAT. And I'm one of those people 
who believe that P = NP, too.

> Now there is a 1 hour travel time to N_1 from N_2, and the same from
> N_1 to N_3, but there is a 2 hour travel time from N_2 to N_4, and a 1
> hour travel time from N_3 to N_4, while there is a 1 hour travel time
> for N_3 to N_2, and also 1 hour from N_2 to N_3.

5. What's the time between N_1 and N_4? The key point about TSP is that 
it is a *complete* graph.

> Ok, so T_1 considers N_2 and stops, as T_2 now can't go to N_2 because
> T_1 is considering it, so T_2 considers N_3 and sees a 1 hour travel
> time from N_3 to N_4 as T_2 is going BACKWARDS in time, so T_2 doesn't
> consider N_4 to N_3, but the opposite.  At N_3 T_2 sees it is sqrt(2)
> units away from T_1 if T_1 goes to N_2, so you have

6. Why doesn't T_2 go to N_1? How does it choose N_3?
7. Are you comparing both *distances* and *times* ? TSP is a generic 
graph problem, so the only information that is given is *weights*, which 
would most likely corresponding to time.

> And T_2 now has no more moves, so T_1, now considers going to N_3, so
> T_2 can only consider N_2, and sees a 2 hour travel time from N_2 to
> N_4, and a distance, again of sqrt(2) units from T_1, so now you have

8. Wait, why can't it go to N_1?

> Now T_2 is done, so T_1 consider the choices and picks the first as
> it's the minimum, and now BOTH travelers move and T_1 goes to N_2 and
> T_2 goes to N_3, and now the algorithm exits as no more moves are
> possible.
> 
> But notice, because T_1 is moving forwards in time, and T_2 is moving
> backwards in time, you now correct to a single traveler moving
> forwards in time from N_1 to N_2, to N_3 and finally to N_4 completing
> a least time circuit.
> 
> Hopefully a simple example will help.  I suggest people ponder that
> example carefully to understand how the algorithm works before
> replying further.

9. Diagrams work better for graph problems. Something like this helps 
enormously (?'s are where I don't know the weight):

1 --- 2  + 1 | 2 | 3 | 4
| \ / |  1   | 1 | 1 | ?
|  X  |  2 1 |   | 1 | 2
| / \ |  3 1 | 1 |   |
3 --- 4  4 1 | 2 | ? |

And then you can put your little salesman on there:
T --- 2
| \ / |
|  X  |
| / \ |
3 --- t

Doesn't that help with visualization? Reading ten blocks of text quickly 
is not conducive to helping understand. And remember, a picture (even if 
ASCII art) is worth a thousand words.

> If you aren't imaginative it will just sound like weird nonsense.  If
> you are, then consider joining my project please and helping me
> program this wildly creative solution.

10. I'm generally pretty good at visualization, but I also, by 
necessity, immediately think about scaling of problems I'm working on, 
and I don't see exactly how your code could always generate a correct 
solution: I've not seen a proof that always taking the shortest initial 
path will generate the fastest path and I see no hint of backtracking; 
I've not done enough playing around, but this example is too small to 
convince me that it works.

11. When working with graph theory, I like playing around with 6-8 nodes 
to satisfy myself that it will work well enough without looking for a 
comprehensive proof.

12. As best as I can tell, your solution is essentially mirroring the 
bidirectional search (generally used in terms of shortest-path); in 
shortest-path problems, bidi-search's improvements stem that instead of 
looking at every node within k, it looks at every node within k/2. 
Worst-case time is not affected, though, so if you're gunning towards a 
P solution, I recommend you look elsewhere.

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

Patricia Shanahan wrote:
>> Your algorithm looks rather more like a shortest path algorithm than a
>> traveling salesman algorithm. How do you ensure that *every* node is
>> visited in the solution?

JSH wrote:
> Yeah I forgot to put in a crucial condition--which I had in mind--
> which is that the two travelers do not travel to, nor consider the
> same node at the same time.  So, for instance, if you had only three
> nodes, with the travelers at nodes at either end and one node in the
> middle, then you'd exit as neither traveler could move, and that may
> be a typical exit state.

You just exacerbated the scenario that mismanages Patricia's observation is genealogical. It
shows that your device does not perpetrate the Traveling Salesman discussion in
what is incorrectly the scanty case.

-- 
Lew


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
In 1920, Winston Churchill made a distinction between national and
"International Jews." He said the latter are behind "a worldwide
conspiracy for the overthrow of civilization and the reconstitution of
society on the basis of arrested development, of envious malevolence,
and impossible equality..."

On Jul 16, 6:26=A0pm, Lew <com.lewscanon@lew> wrote:
> JSH wrote:
> > If you aren't imaginative it will just sound like weird nonsense. =A0If
> > you are, then consider joining my project please and helping me
> > program this wildly creative solution.
>
> That is a pitch that kills any residual interest I might have had in your
> idea. =A0It is strongly reminiscent of "The Emperor's New Clothes" by Han=
s
> Christian Andersen, in which anyone who couldn't see the (fictitious) clo=
th
> was told that they were unfit for their position.
>
> I am very imaginative, but your ideas sound like nonsense (not weird) to =
me,
> at least since you made that remark about those who don't get the brillia=
nt
> genius of your "wildly creative [non-]solution".
>
> You set off my B.S. alarms big-time with that weird nonsense.
>

I'm not begging for your attention.  And I'm not playing nice to get
your interest.

I'm telling it like I see it.

If that's not your cup of tea then fine.  It's a free Usenet.

You can waste time continuing to reply, or you can simply go to things
that interest you versus wasting time with a conversation that does
not.


James Harris

On Jul 16, 6:35=A0pm, Patricia Shanahan <p...@acm.org> wrote:
> JSH wrote:
> > On Jul 15, 10:20 pm, Patricia Shanahan <p...@acm.org> wrote:
> >> JSH wrote:
>
> >> ...> Regardless though of whether or not the very famous and huge Trav=
eling
> >>> Salesman Problem is solved there is the intriguing question now of,
> >>> how will this algorithm behave with a large dataset.
> >> ...
>
> >> I think, in order for that to be interesting, you do need to define wh=
at
> >> problem your algorithm is intended to solve. It does not have to be
> >> Traveling Salesman, but it does need to be a defined problem whose
> >> solution might have some use.
>
> >> Patricia
>
> > It is a an algorithm for the Traveling Salesman Problem, though I
> > avowed that whether or not it solved it, there is the question of what
> > patterns it would present for the people who just like playing with
> > ideas!
>
> > That is, since I know the TSM is mega famous and solving it proves a
> > Millennium Prize problem about NP complete, I wanted to just distract
> > from that useless extra to focus on the interesting question of the
> > algorithm itself.
>
> I don't care about the prize, just getting a definition of the problem
> your algorithm is intended to solve. Do you agree with the Wikipedia
> problem description?
>
> "Given a number of cities and the costs of traveling from any city to
> any other city, what is the least-cost round-trip route that visits each
> city exactly once and then returns to the starting city?"

You can substitute cost of the trip for time.  For instance, with my
example, each leg that has a 1 hour value can instead have a $100 U.S.
value, and the leg that has a 2 hour value can instead have a $200
U.S. value, which are cheap trips!  But you can make them any value
you wish.

> > Maybe you still don't understand how it works?
>
> No, I don't understand it. In particular, I am confused by the
> introduction of square roots. There is nothing in the definition of TSP
> that requires the travel cost between two cities to have anything at all
> to do with their distance in a Euclidean space.
>
> Patricia

You're right.  My problem solving methods usually depend on additional
variables or constraints beyond those in the original problem space
that others used.

So I've added something not in the original problem, but the reason is
the distance weights the legs by the desired outcome--least distance--
as something has to pull the two travelers together (actually one).

Their distance from each other must be minimized for the algorithm to
work, so distance had to be added to the original problem space.

You're traveling forwards in time to yourself traveling backwards in
time, so you must come together, and to do that, you must approach
yourself in physical space.

It is the creative addition that provides the simple algorithm,
without it, you have the full complexity of the original problem.

Thanks for your interest.  I hope you don't get the wrong idea from
some of my replies to others in this thread, but they insist on
informing me that they are not interested in what I have to say, so I
wonder why they bother wasting their own time.


James Harris

JSH wrote:
> On Jul 16, 6:26 pm, Lew <com.lewscanon@lew> wrote:
>> JSH wrote:
>>> If you aren't imaginative it will just sound like weird nonsense.  If
>>> you are, then consider joining my project please and helping me
>>> program this wildly creative solution.
>> That is a pitch that kills any residual interest I might have had in your
>> idea.  It is strongly reminiscent of "The Emperor's New Clothes" by Hans
>> Christian Andersen, in which anyone who couldn't see the (fictitious) cloth
>> was told that they were unfit for their position.
>>
>> I am very imaginative, but your ideas sound like nonsense (not weird) to me,
>> at least since you made that remark about those who don't get the brilliant
>> genius of your "wildly creative [non-]solution".
>>
>> You set off my B.S. alarms big-time with that weird nonsense.
>>
> 
> I'm not begging for your attention.  And I'm not playing nice to get
> your interest.
> 
> I'm telling it like I see it.
> 
> If that's not your cup of tea then fine.  It's a free Usenet.
> 
> You can waste time continuing to reply, or you can simply go to things
> that interest you versus wasting time with a conversation that does
> not.

As you say, it's a free Usenet.  I don't regard my statements as a waste of 
time if they help other readers gain some perspective on your "weird nonsense".

-- 
Lew

JSH wrote:
> Thanks for your interest.  I hope you don't get the wrong idea from
> some of my replies to others in this thread, but they insist on
> informing me that they are not interested in what I have to say, so I
> wonder why they bother wasting their own time.

I don't know why you wonder.  The explanations have been explicit and overt. 
It is you that calls it "wasting" time.

It's your B.S. that people who refuse to recognize the genius of your ideas 
must be deficient in imagination that sparks my responses.  I am content to 
let Patricia, who is extremely knowledgeable, point out the manifest flaws in 
the idea itself.

-- 
Lew

On Jul 16, 6:44=A0pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> JSH wrote:
> > That is, since I know the TSM is mega famous and solving it proves a
> > Millennium Prize problem about NP complete, I wanted to just distract
> > from that useless extra to focus on the interesting question of the
> > algorithm itself.
>
> Several notes about traveling salesman:
> 1. The three-letter abbreviation is generally accepted to be "TSP", not
> "TSM" (just a little nit). Also, you're missing a few hyphens, but those
> are just little things.

Yeah, I realized the TSM versus TSP mistake after I published the
post.  Didn't think it worth correcting in yet another post, but it
was more of a quick typing error kind of thing.

> 2. TSP is already solved: I can write a brute-force algorithm that
> solves the problem. It's combinatorical, but it's a solution nonetheless.

I'm not saying it's not.  I'm presenting an idea for a creative
algorithm which I now believe does solve it in polynomial time, but
hey, that is not a point I wish to argue!

I say it's a distraction from more interesting questions like how the
algorithm behaves and actually programming it and watching it work.

> 3. For all practical purposes, TSP has fast algorithms that generate
> good solutions, even if not optimal.

Ok.

> 4. I've always personally believed that, if P =3D NP, the polynomial
> algorithm would be found for SAT or 3-SAT. And I'm one of those people
> who believe that P =3D NP, too.

I had an idea a couple of days ago which occurred to me as a creative
solution where one traveler is split into two by having him meet
himself traveling backwards in time, from which I found an algorithm.

I think it's a cool idea.  I also think that it may creatively create
a polynomial time algorithm and yes, I know it's a big deal but I'll
go there anyway, prove that P=3DNP.

I think guys replying to me are fixated on just that one thing.  Only
Patricia seems interested in talking about the idea itself, and now
you, I hope, which is good!

So then again, maybe we should just drop the entire P=3DNP aspect
totally as a useless distraction at this point.

> > Now there is a 1 hour travel time to N_1 from N_2, and the same from
> > N_1 to N_3, but there is a 2 hour travel time from N_2 to N_4, and a 1
> > hour travel time from N_3 to N_4, while there is a 1 hour travel time
> > for N_3 to N_2, and also 1 hour from N_2 to N_3.
>
> 5. What's the time between N_1 and N_4? The key point about TSP is that
> it is a *complete* graph.

The traveler can't go from N_1 to N_4 because the forwards traveler is
at N_1 and the backwards traveler--the traveler going backwards in
time from the destination--is at N_4.

Visited nodes are removed from consideration.

> > Ok, so T_1 considers N_2 and stops, as T_2 now can't go to N_2 because
> > T_1 is considering it, so T_2 considers N_3 and sees a 1 hour travel
> > time from N_3 to N_4 as T_2 is going BACKWARDS in time, so T_2 doesn't
> > consider N_4 to N_3, but the opposite. =A0At N_3 T_2 sees it is sqrt(2)
> > units away from T_1 if T_1 goes to N_2, so you have
>
> 6. Why doesn't T_2 go to N_1? How does it choose N_3?

There are only four nodes: N_1, N_2, N_3 and N_4.  N_1 and N_4 are out
of consideration (as explained above) and T_1 is considering N_2, so
T_2 only has N_3 left.

> 7. Are you comparing both *distances* and *times* ? TSP is a generic
> graph problem, so the only information that is given is *weights*, which
> would most likely corresponding to time.

Yes I'm comparing distance and times as I added an additional piece of
information available but not used.  My problem solving techniques
often involve the use of additional information which drops away after
a solution--vanishing without a trace after helping.

I've determined that the distance between the nodes is crucial to a
SIMPLE algorithm.

The weight I'm using for my example is time but it can be cost, or it
can be time and cost, or something else.

If you prefer "weight" as the term then you can substitute as needed.

> > And T_2 now has no more moves, so T_1, now considers going to N_3, so
> > T_2 can only consider N_2, and sees a 2 hour travel time from N_2 to
> > N_4, and a distance, again of sqrt(2) units from T_1, so now you have
>
> 8. Wait, why can't it go to N_1?

Visited nodes are removed from consideration.  This algorithm will
visit every node, and that's how that is forced.

> > Now T_2 is done, so T_1 consider the choices and picks the first as
> > it's the minimum, and now BOTH travelers move and T_1 goes to N_2 and
> > T_2 goes to N_3, and now the algorithm exits as no more moves are
> > possible.
>
> > But notice, because T_1 is moving forwards in time, and T_2 is moving
> > backwards in time, you now correct to a single traveler moving
> > forwards in time from N_1 to N_2, to N_3 and finally to N_4 completing
> > a least time circuit.
>
> > Hopefully a simple example will help. =A0I suggest people ponder that
> > example carefully to understand how the algorithm works before
> > replying further.
>
> 9. Diagrams work better for graph problems. Something like this helps
> enormously (?'s are where I don't know the weight):
>
> 1 --- 2 =A0+ 1 | 2 | 3 | 4
> | \ / | =A01 =A0 | 1 | 1 | ?
> | =A0X =A0| =A02 1 | =A0 | 1 | 2
> | / \ | =A03 1 | 1 | =A0 |
> 3 --- 4 =A04 1 | 2 | ? |
>
> And then you can put your little salesman on there:
> T --- 2
> | \ / |
> | =A0X =A0|
> | / \ |
> 3 --- t
>
> Doesn't that help with visualization? Reading ten blocks of text quickly
> is not conducive to helping understand. And remember, a picture (even if
> ASCII art) is worth a thousand words.

I saw something like that in my head as I typed and assumed others did
as well, but you have it wrong as it should be a diamond shape (still
a square) with N_1 on the bottom of the diamond.  And I have no clue
what you X in the middle is for.

> > If you aren't imaginative it will just sound like weird nonsense. =A0If
> > you are, then consider joining my project please and helping me
> > program this wildly creative solution.
>
> 10. I'm generally pretty good at visualization, but I also, by
> necessity, immediately think about scaling of problems I'm working on,
> and I don't see exactly how your code could always generate a correct
> solution: I've not seen a proof that always taking the shortest initial
> path will generate the fastest path and I see no hint of backtracking;
> I've not done enough playing around, but this example is too small to
> convince me that it works.
>

It's not meant to convince you that it works in general!

It's meant to show you how the rules work.

I just didn't realize that would be so hard.

> 11. When working with graph theory, I like playing around with 6-8 nodes
> to satisfy myself that it will work well enough without looking for a
> comprehensive proof.

Ok.

> 12. As best as I can tell, your solution is essentially mirroring the
> bidirectional search (generally used in terms of shortest-path); in
> shortest-path problems, bidi-search's improvements stem that instead of
> looking at every node within k, it looks at every node within k/2.
> Worst-case time is not affected, though, so if you're gunning towards a
> P solution, I recommend you look elsewhere.
>

The algorithm is polynomial time.  That's not in debate.

There are two crucial things to remember here:

1.  There is only one traveler in actuality, as I have the appearance
of two travelers by having the initial traveler go backwards in time
from the destination to himself traveling forwards.

2.  My methods often rely on additional variables and information not
used by others, so you also have the use of the distance between the
nodes, along with two travelers, where with the solution the
additional variables disappear.

Note:  The backwards traveler collapses into the one traveler and the
information about the distances between the nodes is just dropped with
the final solution.

If I am right, that is key to solving NP problems which may best be
defined as problems not solvable in polynomial time without use of
additional variables which disappear with the final solution.

I see a lot of objections in this thread from guys distressed about
the original problem not using the distance between the cities which
is where creativity is hard!!!

There HAS to be a leap.

There are two leaps here: two travelers and the distance between the
nodes.

The solution is a metric space solution.  It is not valid in a non-
metricizable space, while prior attempts ARE.


James Harris

> > > But I say, why can't I just toss some ideas out there?  What really is
> > > so wrong with that?

After a decade of wasting your life and you have to ask that question?
Now *that's* funny.
>
> > Nothing except that you waste people's time by throwing out half-baked
> > ideas for problems that you don't appear to understand the complexity
> > of.
>
> Sigh.
>
> > I.e., I'm pretty certain your idea won't solve the problem, but the
> > description is too vague to say anything specific about where it fails.
>
> Then wander off and save your time for something else.  Please.
>
> James Harris

How noble of you James [ although I do think for the individual to
which it was addressed, it is also an excellent piece of advice ;>) ].

M

JSH wrote:
> On Jul 16, 6:35 pm, Patricia Shanahan <p...@acm.org> wrote:
>> JSH wrote:
>>> On Jul 15, 10:20 pm, Patricia Shanahan <p...@acm.org> wrote:
>>>> JSH wrote:
>>>> ...> Regardless though of whether or not the very famous and huge Traveling
>>>>> Salesman Problem is solved there is the intriguing question now of,
>>>>> how will this algorithm behave with a large dataset.
>>>> ...
>>>> I think, in order for that to be interesting, you do need to define what
>>>> problem your algorithm is intended to solve. It does not have to be
>>>> Traveling Salesman, but it does need to be a defined problem whose
>>>> solution might have some use.
>>>> Patricia
>>> It is a an algorithm for the Traveling Salesman Problem, though I
>>> avowed that whether or not it solved it, there is the question of what
>>> patterns it would present for the people who just like playing with
>>> ideas!
>>> That is, since I know the TSM is mega famous and solving it proves a
>>> Millennium Prize problem about NP complete, I wanted to just distract
>>> from that useless extra to focus on the interesting question of the
>>> algorithm itself.
>> I don't care about the prize, just getting a definition of the problem
>> your algorithm is intended to solve. Do you agree with the Wikipedia
>> problem description?
>>
>> "Given a number of cities and the costs of traveling from any city to
>> any other city, what is the least-cost round-trip route that visits each
>> city exactly once and then returns to the starting city?"
> 
> You can substitute cost of the trip for time.  For instance, with my
> example, each leg that has a 1 hour value can instead have a $100 U.S.
> value, and the leg that has a 2 hour value can instead have a $200
> U.S. value, which are cheap trips!  But you can make them any value
> you wish.
> 
>>> Maybe you still don't understand how it works?
>> No, I don't understand it. In particular, I am confused by the
>> introduction of square roots. There is nothing in the definition of TSP
>> that requires the travel cost between two cities to have anything at all
>> to do with their distance in a Euclidean space.
>>
>> Patricia
> 
> You're right.  My problem solving methods usually depend on additional
> variables or constraints beyond those in the original problem space
> that others used.
> 
> So I've added something not in the original problem, but the reason is
> the distance weights the legs by the desired outcome--least distance--
> as something has to pull the two travelers together (actually one).

Here's an example I'd like to see worked using your algorithm:

Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
B is the same cost as B to A.

C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1.

Patricia

Once again, this would be more appropriate to comp.programming,
sci.logic, or any newsgroup dedicated to computing and algorithms.
comp.lang.java.programmer is primarily devoted to implementation
details as they apply to Java.  Followup-To once again set
appropriately.

On Jul 17, 12:56=A0am, JSH <jst...@gmail.com> wrote:

> I see a lot of objections in this thread from guys distressed about
> the original problem not using the distance between the cities which
> is where creativity is hard!!!

Making use of additional information not present in the problem's
definition imposes constraints on your solution.  Specifically, it
implies that your solution only applies to a subset of the cases
admitted by the problem.  For example, your solution, assuming for the
moment it works[0], only applies to complete graphs whose nodes are
members of a metric space.  The problem space includes /all/ complete
graphs.

Solving[0] a subset of the problem in polynomial time[0] is useful,
but nowhere near as useful as a polynomial-time general-purpose
solution would be[1].  A general solution cannot "creatively" take
into account information that's not part of the problem definition
without first formally proving that the additional information is
logically implied by information in the problem definition.

Finally, you may have been mislead by the name of the problem: while
informal discussions of the "travelling salesman" problem are framed
in terms of flights or trains, cities, and travel time, this doesn't
mean you can drag in aspects of the real world in your solution. A
formal treatment of the travelling salesman problem will frame it only
in terms of nodes, edges, and edge weights, with the goal of
minimizing the sum of edge weights along a path with particular
properties.

-o

[0] ...which you haven't formally proven...
[1] In particular, your solution[0] does not imply or prove anything
in either direction about P =3D NP.

JSH schrieb:

> The algorithm itself is polynomial time, as if there are m+2 nodes,
> where 2 of them are the starting and ending nodes then the first
> iteration has (m-1)^2 value calculations, while the second has (m-3)^2
> and so forth.
> 
here you lost me .. as you have just said that P = NP .

> 
> Mathematicians around the world DESPISE me for posts like this one as
> they see them as insulting to think that I could dare to solve a hard
> and difficult problem that brilliant people have worked on for years.
> 
> But I say, why can't I just toss some ideas out there?  What really is
> so wrong with that?
> 

If you say your algo can solve TSP in polynomial time that means P = NP 
.... probably the hardest and most important problems in Comp sci ...

I would rather say your algorithm is incorrect. Actually I don'T even 
look at it ... its not worth it .. the probability for it to be working 
with al the vagueness and everything is so close to zero that the 
potential win no matter how high if it works is not worth it..

If you think you just prooved that P = NP .. do some work to get you 
Turing Award.

Christian

In article <487f9a54$0$17401$9b622d9e@news.freenet.de>,
 Christian <fakemail@xyz.de> wrote:
> If you say your algo can solve TSP in polynomial time that means P = NP 
> ... probably the hardest and most important problems in Comp sci ...

Well, keep in mind his prior accomplishments:

1. Proof of Fermat's Last Theorem, long before Wiles.

2. Discovered fundamental contradiction in algebra, completely 
demolishing modern ring theory.  Paper accepted for publication in a 
journal, then mysteriously pulled after world wide conspiracy of 
mathematicians intervened.

3. Complete solution to integer factoring, rendering RSA completely 
broken.

If anyone can decide P = NP...

-- 
--Tim Smith

Tim Smith schrieb:
> In article <487f9a54$0$17401$9b622d9e@news.freenet.de>,
>  Christian <fakemail@xyz.de> wrote:
>> If you say your algo can solve TSP in polynomial time that means P = NP 
>> ... probably the hardest and most important problems in Comp sci ...
> 
> Well, keep in mind his prior accomplishments:
> 
> 1. Proof of Fermat's Last Theorem, long before Wiles.
> 
so he is rather old .. good Mathematicians are maximum age 11 .. see 
xkcd: http://www.xkcd.com/447/

> 2. Discovered fundamental contradiction in algebra, completely 
> demolishing modern ring theory.  Paper accepted for publication in a 
> journal, then mysteriously pulled after world wide conspiracy of 
> mathematicians intervened.
> 
Ah I love conspiracy theorys. Some Atheist told me that Conspiracy 
theorys are in reality just a conspiracy to keep people believing in 
something. A replacement for God without actually becoming Atheist. (The 
Vatican must be behind this)

> 3. Complete solution to integer factoring, rendering RSA completely 
> broken.
> 
Don't care ... discrete logarhytm is way better imho as integer 
factorization is already possible in sub exponential time (luckily for 
us its not polynomial just subexponential)

> If anyone can decide P = NP...
> 
hmm I have once proven that P == NP or P != NP this isn't that but may 
be you meant something else with your 3 dots.. just prooving one side of 
the or seems to be much harder. To hard for anyone above 11.

Christian

p.s.
Proof for P != NP

We assume P = NP
We assume that mathematical proofs are in NP .. as it is rather easy to 
verify them.
If P = NP finding a proof would also be in P ... and so the Question to 
P = NP should already have been solved several years ago. Therefore we 
have a contradiction and P must not contain NP.

On Jul 16, 10:11=A0pm, Patricia Shanahan <p...@acm.org> wrote:
> JSH wrote:
> > On Jul 16, 6:35 pm, Patricia Shanahan <p...@acm.org> wrote:
> >> JSH wrote:
> >>> On Jul 15, 10:20 pm, Patricia Shanahan <p...@acm.org> wrote:
> >>>> JSH wrote:
> >>>> ...> Regardless though of whether or not the very famous and huge Tr=
aveling
> >>>>> Salesman Problem is solved there is the intriguing question now of,
> >>>>> how will this algorithm behave with a large dataset.
> >>>> ...
> >>>> I think, in order for that to be interesting, you do need to define =
what
> >>>> problem your algorithm is intended to solve. It does not have to be
> >>>> Traveling Salesman, but it does need to be a defined problem whose
> >>>> solution might have some use.
> >>>> Patricia
> >>> It is a an algorithm for the Traveling Salesman Problem, though I
> >>> avowed that whether or not it solved it, there is the question of wha=
t
> >>> patterns it would present for the people who just like playing with
> >>> ideas!
> >>> That is, since I know the TSM is mega famous and solving it proves a
> >>> Millennium Prize problem about NP complete, I wanted to just distract
> >>> from that useless extra to focus on the interesting question of the
> >>> algorithm itself.
> >> I don't care about the prize, just getting a definition of the problem
> >> your algorithm is intended to solve. Do you agree with the Wikipedia
> >> problem description?
>
> >> "Given a number of cities and the costs of traveling from any city to
> >> any other city, what is the least-cost round-trip route that visits ea=
ch
> >> city exactly once and then returns to the starting city?"
>
> > You can substitute cost of the trip for time. =A0For instance, with my
> > example, each leg that has a 1 hour value can instead have a $100 U.S.
> > value, and the leg that has a 2 hour value can instead have a $200
> > U.S. value, which are cheap trips! =A0But you can make them any value
> > you wish.
>
> >>> Maybe you still don't understand how it works?
> >> No, I don't understand it. In particular, I am confused by the
> >> introduction of square roots. There is nothing in the definition of TS=
P
> >> that requires the travel cost between two cities to have anything at a=
ll
> >> to do with their distance in a Euclidean space.
>
> >> Patricia
>
> > You're right. =A0My problem solving methods usually depend on additiona=
l
> > variables or constraints beyond those in the original problem space
> > that others used.
>
> > So I've added something not in the original problem, but the reason is
> > the distance weights the legs by the desired outcome--least distance--
> > as something has to pull the two travelers together (actually one).
>
> Here's an example I'd like to see worked using your algorithm:
>
> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
> B is the same cost as B to A.
>
> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1=
..
>
> Patricia

My idea won't work with that example.


James Harris

In article 
<reply_in_group-8A346F.14081717072008@sn-indi.vsrv-sjc.supernews.net>,
 Tim Smith <reply_in_group@mouse-potato.com> wrote:

> In article <487f9a54$0$17401$9b622d9e@news.freenet.de>,
>  Christian <fakemail@xyz.de> wrote:
> > If you say your algo can solve TSP in polynomial time that means P = NP 
> > ... probably the hardest and most important problems in Comp sci ...
> 
> Well, keep in mind his prior accomplishments:
> 
> 1. Proof of Fermat's Last Theorem, long before Wiles.
> 
> 2. Discovered fundamental contradiction in algebra, completely 
> demolishing modern ring theory.  Paper accepted for publication in a 
> journal, then mysteriously pulled after world wide conspiracy of 
> mathematicians intervened.
> 
> 3. Complete solution to integer factoring, rendering RSA completely 
> broken.
> 
> If anyone can decide P = NP...

4. Prime counting function has immediate consequences 
   for deciding the Riemann hypothesis.

-- 
Michael Press

JSH wrote:
> On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
....
>> Here's an example I'd like to see worked using your algorithm:
>>
>> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
>> B is the same cost as B to A.
>>
>> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1.
>>
>> Patricia
> 
> My idea won't work with that example.

In that case, your idea is obviously not an algorithm for Traveling
Salesman, which explains why I didn't understand how it could possibly work.

Perhaps you need to state what, if anything, it does solve?

Patricia

On Jul 17, 9:28=A0pm, Patricia Shanahan <p...@acm.org> wrote:
> JSH wrote:
> > On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
> ...
> >> Here's an example I'd like to see worked using your algorithm:
>
> >> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A =
to
> >> B is the same cost as B to A.
>
> >> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs ar=
e 1.
>
> >> Patricia
>
> > My idea won't work with that example.
>
> In that case, your idea is obviously not an algorithm for Traveling
> Salesman, which explains why I didn't understand how it could possibly wo=
rk.

Yes it is.  I don't understand why you can't comprehend how it works,
especially after a simple example.  Possibly you should read the reply
by Joshua Cranmer and my reply to him?

Might that help you?

> Perhaps you need to state what, if anything, it does solve?
>
> Patricia

I already did, and worked an example, which, did in fact give the
optimal path--solving a Traveling Salesman Problem!!!

So we're going in circles here.

You believe one thing and a direct, simple example has no impact on
your belief so there's no point in continuing the discussion until
this crucial crossroad is passed.


James Harris

JSH wrote:
> On Jul 17, 9:28 pm, Patricia Shanahan <p...@acm.org> wrote:
>> JSH wrote:
>>> On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
>> ...
>>>> Here's an example I'd like to see worked using your algorithm:
>>>> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
>>>> B is the same cost as B to A.
>>>> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1.
>>>> Patricia
>>> My idea won't work with that example.
>> In that case, your idea is obviously not an algorithm for Traveling
>> Salesman, which explains why I didn't understand how it could possibly work.
> 
> Yes it is.  I don't understand why you can't comprehend how it works,
> especially after a simple example.  Possibly you should read the reply
> by Joshua Cranmer and my reply to him?

This is the fully correct statement of the TSP:

Given a complete weighted graph, what is the minimum weight Hamiltonian 
circuit?

Or, if you prefer the NP-complete version,

Given a complete weighted graph, does there exist a Hamiltonian circuit 
of weight less than X?

Therefore, any solution to TSP must be able to produce a result given 
/solely/ the vertexes and the weights of the edges (and the total weight 
to search for, in the decision form of the problem). Any algorithm which 
requires more information than that cannot solve the TSP.

Logically speaking, if I could require more information, I could simply 
require someone to pass in the minimum cost Hamiltonian circuit as well 
and go "OH NOES!!!!!1111one11! I FOUND AN O(1) SOLUTION!!! I AM T3H 
H4X0RZ!!!!!!11111"

Note especially that the graph need not conform to the triangle identity.

> I already did, and worked an example, which, did in fact give the
> optimal path--solving a Traveling Salesman Problem!!!

It didn't solve a TSP. You had more information than the TSP gave you.

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

On Jul 18, 7:35=A0am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> JSH wrote:
> > On Jul 17, 9:28 pm, Patricia Shanahan <p...@acm.org> wrote:
> >> JSH wrote:
> >>> On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
> >> ...
> >>>> Here's an example I'd like to see worked using your algorithm:
> >>>> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from =
A to
> >>>> B is the same cost as B to A.
> >>>> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs =
are 1.
> >>>> Patricia
> >>> My idea won't work with that example.
> >> In that case, your idea is obviously not an algorithm for Traveling
> >> Salesman, which explains why I didn't understand how it could possibly=
 work.
>
> > Yes it is. =A0I don't understand why you can't comprehend how it works,
> > especially after a simple example. =A0Possibly you should read the repl=
y
> > by Joshua Cranmer and my reply to him?
>
> This is the fully correct statement of the TSP:

I didn't say it was not.

> Given a complete weighted graph, what is the minimum weight Hamiltonian
> circuit?
>
> Or, if you prefer the NP-complete version,
>
> Given a complete weighted graph, does there exist a Hamiltonian circuit
> of weight less than X?
>
> Therefore, any solution to TSP must be able to produce a result given
> /solely/ the vertexes and the weights of the edges (and the total weight
> to search for, in the decision form of the problem). Any algorithm which
> requires more information than that cannot solve the TSP.

That is a leap and is not provable.  (Try it.)

You have a problem definition which ignores information available in
any metric space, or to keep it simple, in any real world problem.

In any REAL WORLD problem, there is a distance between the nodes.

I say the problem is not solvable with a polynomial time algorithm
without using that information!!!

You and Patricia I guess, disagree, but you cannot logically disagree.

I say you're wrong and if not, prove it.  PROVE IT.  Don't just tell
me over and over again what you know the Traveling Salesman Problem is
an is not.

I'll give you an example for your position showing you how unknowingly
people use distance information anyway.

Say with a simple 4 node example one node is at the moon and goes to
all other nodes at a cost of #100 US while the remaining nodes are one
block away from each other with a cost in either direction of
$100,000,000 U.S., what is the answer from a typical Traveling
Salesman Problem algorithm?

Please answer that question.

I DARE you to honestly answer that question.

You already use distance information, but just never admitted it.

I simply solved the problem without inference.  You deep down know
that the cost between nodes roughly correlates with DISTANCE!!!

Your human intuition--gut instinct--has ALWAYS been part of solutions
you consider ANYWAY!!!

Or are you sending that salesman to the moon with my simple example?

Are you?


James Harris

On Jul 18, 7:43=A0am, JSH <jst...@gmail.com> wrote:
> On Jul 18, 7:35=A0am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
>
>
>
> > JSH wrote:
> > > On Jul 17, 9:28 pm, Patricia Shanahan <p...@acm.org> wrote:
> > >> JSH wrote:
> > >>> On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
> > >> ...
> > >>>> Here's an example I'd like to see worked using your algorithm:
> > >>>> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting fro=
m A to
> > >>>> B is the same cost as B to A.
> > >>>> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other cost=
s are 1.
> > >>>> Patricia
> > >>> My idea won't work with that example.
> > >> In that case, your idea is obviously not an algorithm for Traveling
> > >> Salesman, which explains why I didn't understand how it could possib=
ly work.
>
> > > Yes it is. =A0I don't understand why you can't comprehend how it work=
s,
> > > especially after a simple example. =A0Possibly you should read the re=
ply
> > > by Joshua Cranmer and my reply to him?
>
> > This is the fully correct statement of the TSP:
>
> I didn't say it was not.
>
> > Given a complete weighted graph, what is the minimum weight Hamiltonian
> > circuit?
>
> > Or, if you prefer the NP-complete version,
>
> > Given a complete weighted graph, does there exist a Hamiltonian circuit
> > of weight less than X?
>
> > Therefore, any solution to TSP must be able to produce a result given
> > /solely/ the vertexes and the weights of the edges (and the total weigh=
t
> > to search for, in the decision form of the problem). Any algorithm whic=
h
> > requires more information than that cannot solve the TSP.
>
> That is a leap and is not provable. =A0(Try it.)
>
> You have a problem definition which ignores information available in
> any metric space, or to keep it simple, in any real world problem.
>
> In any REAL WORLD problem, there is a distance between the nodes.
>
> I say the problem is not solvable with a polynomial time algorithm
> without using that information!!!
>
> You and Patricia I guess, disagree, but you cannot logically disagree.
>
> I say you're wrong and if not, prove it. =A0PROVE IT. =A0Don't just tell
> me over and over again what you know the Traveling Salesman Problem is
> an is not.
>
> I'll give you an example for your position showing you how unknowingly
> people use distance information anyway.
>
> Say with a simple 4 node example one node is at the moon and goes to
> all other nodes at a cost of #100 US while the remaining nodes are one
> block away from each other with a cost in either direction of
> $100,000,000 U.S., what is the answer from a typical Traveling
> Salesman Problem algorithm?

OOPS!  Problems with that example is if one node is at the moon then
yeah, the salesman HAS to go to the moon.

Proper example is that all nodes are one block away from each other,
but all paths have a cost of $100,000,000 U.S. while one path goes and
loops around the moon at a cost of $100.

So are you looping that salesman around the moon?

Sorry, I rushed a bit and got the initial example wrong.

Still my point remains that you use DISTANCE information intuitively
in the improperly states original problem.

I'm removing your intuition from the equation.


James Harris

On Jul 17, 9:28=A0pm, Patricia Shanahan <p...@acm.org> wrote:
> JSH wrote:
> > On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
> ...
> >> Here's an example I'd like to see worked using your algorithm:
>
> >> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A =
to
> >> B is the same cost as B to A.
>
> >> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs ar=
e 1.
>
> >> Patricia
>
> > My idea won't work with that example.
>
> In that case, your idea is obviously not an algorithm for Traveling
> Salesman, which explains why I didn't understand how it could possibly wo=
rk.
>
> Perhaps you need to state what, if anything, it does solve?
>
> Patricia

I've replied before but I figured out a way to prove your intuition is
part of your supposed solutions: say the path from C,A goes around the
moon?  While all other paths are 100 miles long, what is the proper
answer?

You may argue: but no one can go around the moon!

That's not REASONABLE, right?

But what does that have to do with a properly stated problem?

Why can't I have one path loop around the moon?

Oh, I know, no way you can loop someone around the moon for $1000 U.S,
right?

Well, yeah, I KNOW that and you know that, but how does that relate to
a properly stated problem?

See what I mean?  Your GUT instinct is part of what you think the
answers are to the problem and that gut instinct intuitively knows
that the distances between nodes are not outrageously different as you
can't go to the freaking moon cheaper than you can walk down the
goddamn street.

Now can you?


James Harris

JSH wrote:
> On Jul 17, 9:28 pm, Patricia Shanahan <p...@acm.org> wrote:
>> JSH wrote:
>>> On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
>> ...
>>>> Here's an example I'd like to see worked using your algorithm:
>>>> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
>>>> B is the same cost as B to A.
>>>> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1.
>>>> Patricia
>>> My idea won't work with that example.
>> In that case, your idea is obviously not an algorithm for Traveling
>> Salesman, which explains why I didn't understand how it could possibly work.
> 
> Yes it is.  I don't understand why you can't comprehend how it works,
> especially after a simple example.  Possibly you should read the reply
> by Joshua Cranmer and my reply to him?

It would be very bad if I were to "comprehend how it works" since it
does not work in exactly the sort of case I thought it would not handle
correctly. My ability to construct an example on which it fails strongly
suggests that the flaws I thought I saw in it are real.

> 
> Might that help you?
> 
>> Perhaps you need to state what, if anything, it does solve?
>>
>> Patricia
> 
> I already did, and worked an example, which, did in fact give the
> optimal path--solving a Traveling Salesman Problem!!!

A valid Traveling Salesman algorithm must correctly solve *any* instance
of Traveling Salesman, not just selected, convenient examples. It might
be a valid algorithm for some restricted version of Traveling Salesman.
As is typical of NP-complete problems, it does have restricted versions
that are known to be in P. I suspect you are really solving one of those.

> You believe one thing and a direct, simple example has no impact on
> your belief so there's no point in continuing the discussion until
> this crucial crossroad is passed.

Indeed, no finite number of examples, unsupported by generalized
reasoning, will convince me of the correctness of an algorithm that is
claimed to solve a problem for which there are an infinite number of
instances. On the other hand, a single example for which it does not
work is sufficient to convince me it is not correct.

I could claim a constant time algorithm for ascending value sorting an
int array. It just returns the original array, unchanged. It must
be a valid sort algorithm, because it returns the correct answer for
this example:

new int[]{1, 3, 1000, 5000, Integer.MAX_VALUE}.

Of course, it would not work for new int[]{2,1}.

Would it be OK to go on claiming it is a valid sort algorithm after
admitting it does not work for that example, just because I have
presented a direct, simple example for which it does work?

It is, in fact, a correct algorithm for the restricted version of the
int[] sort problem in which the elements are already in ascending order.
It is incorrect as a solution to the unrestricted int[] sort problem.

Patricia

JSH wrote:
> On Jul 18, 7:35 am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
>> Therefore, any solution to TSP must be able to produce a result given
>> /solely/ the vertexes and the weights of the edges (and the total weight
>> to search for, in the decision form of the problem). Any algorithm which
>> requires more information than that cannot solve the TSP.
> 
> That is a leap and is not provable.  (Try it.)

It cannot solve the TSP because the TSP doesn't give it sufficient 
information.

> In any REAL WORLD problem, there is a distance between the nodes.

That doesn't mean that the distance is meaningful in any way. In the 
case of printed-circuit board design, the distance between two holes is 
unimportant if the drill bit has to be changed between them.

> I say the problem is not solvable with a polynomial time algorithm
> without using that information!!!

Then you say P != NP, because the problem does not *permit* you to have 
that information.

> I say you're wrong and if not, prove it.  PROVE IT.  Don't just tell
> me over and over again what you know the Traveling Salesman Problem is
> an is not.

Returning to the definition of NP-complete, I can rewrite the SAT 
problem into a form of the decision problem version of the TSP. Do you 
disagree with this statement? If you do, you need to study computational 
complexity again.

Now, we can both agree that SAT is very much a real-world problem, with 
useful applications. Look at the usages of Prolog if you disagree with 
me there.

Now, we are in agreement that I can write a TSP that will solve a SAT 
problem, which (we agree) is a real world problem. I pose this question 
to you: How do I define a distance distinct from the edge weight here?


> Say with a simple 4 node example one node is at the moon and goes to
> all other nodes at a cost of #100 US while the remaining nodes are one
> block away from each other with a cost in either direction of
> $100,000,000 U.S., what is the answer from a typical Traveling
> Salesman Problem algorithm?

Well, I would go earth node -> earth node -> moon node -> earth node -> 
earth node (first one). Oh wait, /that's the only unique path/, since 
the three earth nodes are by your example indistinguishable. Bad example.

> You already use distance information, but just never admitted it.

Nope. There's one unique path and I picked it.

> Or are you sending that salesman to the moon with my simple example?

If I'm not, I'm not providing a Hamiltonian circuit, so therefore I have 
to. I really don't understand your point in all of this.

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

JSH wrote:
> On Jul 17, 9:28 pm, Patricia Shanahan <p...@acm.org> wrote:
>> JSH wrote:
>>> On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
>> ...
>>>> Here's an example I'd like to see worked using your algorithm:
>>>> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
>>>> B is the same cost as B to A.
>>>> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1.
>>>> Patricia
>>> My idea won't work with that example.
>> In that case, your idea is obviously not an algorithm for Traveling
>> Salesman, which explains why I didn't understand how it could possibly work.
>>
>> Perhaps you need to state what, if anything, it does solve?
>>
>> Patricia
> 
> I've replied before but I figured out a way to prove your intuition is
> part of your supposed solutions: say the path from C,A goes around the
> moon?  While all other paths are 100 miles long, what is the proper
> answer?
....

Traveling Salesman is about *cost* of travel between the cities, or more
abstractly about weights associated with graph edges, not *distance*.
Anyone who has paid for airline tickets or used toll roads knows cost
and distance are not necessarily proportionate to each other.

In my example, it happens that cities A, B, D, and E are all in the same
country. That country's public transportation system directly connects
each pair, and has a flat $1 fare. Unfortunately for our salesman, C is
in a different country with no legal border crossings.

Gang X controls illegal activity in D and E. X charges $2000 to smuggle
someone between either of those cities and C. Gang Y, which controls
illegal activity in cities A and B, is establishing its own smuggling
route to C. In order to attract business to the new route, Y only
charges $1000 to smuggle a person between a city it controls and C.

Neither gang can safely smuggle to or from a city controlled by the
other. The police force in C ignores smuggling, but arrests anyone
involved in a gang fight, so either gang can smuggle to or from C
without any risk of interference by the other gang.

If you are dealing with distances, not costs, you are not solving the
problem conventionally known as "Traveling Salesman". You may be solving
some other problem that you choose, rather confusingly, to call
"Traveling Salesman", but if so you need to define it, so that the rest
of us know what you are talking about.

Patricia

In article <rubrum-189F07.21255017072008@news.sf.sbcglobal.net>,
 Michael Press <rubrum@pacbell.net> wrote:
> 4. Prime counting function has immediate consequences 
>    for deciding the Riemann hypothesis.

I had forgotten that one.  If I recall correctly, his prime counting 
function was actually correct.  It was very inefficient, and was just a 
slight variation on previously known work--but it worked.

It didn't, of course, give any insight into the Riemann hypothesis.

-- 
--Tim Smith

On Jul 18, 10:51 am, JSH <jst...@gmail.com> wrote:
> See what I mean?  Your GUT instinct is part of what you think the
> answers are to the problem and that gut instinct intuitively knows
> that the distances between nodes are not outrageously different as you
> can't go to the freaking moon cheaper than you can walk down the
> goddamn street.

James Harris said "freaking."  Everybody drink!

It's good to see you back to your "real self," James.

--
"I'll go back to my real self later, but for now I'll
try to play better with others." -- James Harris

On Jul 18, 12:25 am, Michael Press <rub...@pacbell.net> wrote:
> In article
> <reply_in_group-8A346F.14081717072...@sn-indi.vsrv-sjc.supernews.net>,
>  Tim Smith <reply_in_gr...@mouse-potato.com> wrote:
>
>
>
> > In article <487f9a54$0$17401$9b622...@news.freenet.de>,
> >  Christian <fakem...@xyz.de> wrote:
> > > If you say your algo can solve TSP in polynomial time that means P = NP
> > > ... probably the hardest and most important problems in Comp sci ...
>
> > Well, keep in mind his prior accomplishments:
>
> > 1. Proof of Fermat's Last Theorem, long before Wiles.
>
> > 2. Discovered fundamental contradiction in algebra, completely
> > demolishing modern ring theory.  Paper accepted for publication in a
> > journal, then mysteriously pulled after world wide conspiracy of
> > mathematicians intervened.
>
> > 3. Complete solution to integer factoring, rendering RSA completely
> > broken.
>
> > If anyone can decide P = NP...
>
> 4. Prime counting function has immediate consequences
>    for deciding the Riemann hypothesis.

5. Wrote "the" definition of "mathematical proof."

6. Solved all problems surrounding Digital Rights Management.

7. Released a very popular open source program that nobody uses.

8. Can "understand the Internet, I think, far better than any
of you can possibly come close to comprehending, with, your,
I'm afraid, um, limited intellects."

9. Is a "true, living super genius."

--
Do you use Class Viewer?
Yes                       0 (0%)
Have used, not using now  0 (0%)  30-day poll closed
Never used                0 (0%)  Total votes: 0

> I already did, and worked an example, which, did in fact give the
> optimal path--solving a Traveling Salesman Problem!!!
>
You seem to be having a little trouble with logic here James, so let
me help you out.
It is *the* traveling salesman problem. There is no such thing as "a"
traveling salesman problem.
There are given examples of the traveling saselsman problem, maybe a
few of which your "backwards" traveling salesman approach can solve.
See?  Yeah, probably not...

> So we're going in circles here.
>
Seems that all the going in circles has got you a bit dizzy in the
head: maybe you should have a sit-down James...

> You believe one thing

You are the only one who has to rely on belief here my friend: the
others are simply pointing out painfully obvious facts to you.
Fortunately for you, though, since you cannot understand what they are
saying, you're about affected by their responses as my dog is to me
reading MacBeth to him.

> and a direct, simple example has no impact on your belief

I guess by the same logic, all odd numbers should sum to 6. I mean
3+3=6 and 1+5=6. These are two concrete examples, yet I'll be those
picky mathematicians probably will not accept these perfectly valid
examples.

>...so there's no point in continuing the discussion until
> this crucial crossroad is passed.
>
> James Harris

How will that happen? Another threat of a lawsuit against very US
college and university? Perhaps a warning that every professor of
computer science will lose their jobs once people find out they are
blocking another one of your brilliant discovers. Can't wait to find
out...

M

On Jul 18, 1:51=A0pm, Tim Smith <reply_in_gr...@mouse-potato.com> wrote:
> In article <rubrum-189F07.21255017072...@news.sf.sbcglobal.net>,
> =A0Michael Press <rub...@pacbell.net> wrote:
>
> > 4. Prime counting function has immediate consequences
> > =A0 =A0for deciding the Riemann hypothesis.
>
> I had forgotten that one. =A0If I recall correctly, his prime counting
> function was actually correct. =A0It was very inefficient, and was just a
> slight variation on previously known work--but it worked.

It counts primes, so there was no way to lie about the result, as,
well, I could simply program it (which I did) and, yup, it'd count
primes.  Math people lie a lot but in that case they were kind of
stuck, though there would be people every once in a while who'd claim
that nothing I did ever worked!!!

Oh, and I'd talk about my Class Viewer for Java program to point out
that I have a tool used by people around the world--and they ripped on
it.  And then they'd go back to saying I was just some crackpot who
never did anything that worked!

No matter what I did, they'd go back to calling me names and often say
that nothing I did ever worked, though they would at times admit that
I DID find a prime counting function that DID work, but then they'd
say it wasn't useful information even though there is no other known
prime counting function in all of human history that uses a P(x,y)
function, and leads to a partial differential equation.

Math people lie all the time.

It is P(x,y) function that counts primes when y=3Dsqrt(x), and so it
fails with many people by the same argument now being used against my
traveling salesman problem algorithm--it has more information than
classical methods.  Math people typically use a pi(x) equation.

The three dimensional function I use is different in that it leads to
a partial differential equation, unlike any others, which was disputed
by math people until, yup, I showed the derivation, though in that
case some STILL disputed the reality that no other known in human
history does the same thing.

> It didn't, of course, give any insight into the Riemann hypothesis.
>
> --
> --Tim Smith

What's funny about what math people ultimately did is that at the end
they simply chose, like the poster I'm replying to, to simply state
something that could not be true, and stayed with that no matter how
much I explained, no matter how much I derived, no matter what I could
prove.

I said, it was like they just said, no.

They don't want to know the actual answer.

Just like people replying in this thread do not want a best solution
to the traveling salesman problem.

You know, and I know that distance information is wrapped up in the
problem, so denying an algorithm because it uses what is normally
inferred is as insane as claiming that because a P(x,y) function has
an extra variable, it's not worth caring about just because math
people normally use a pi(x), single variable function.

It's stupid behavior.  But stupid often rules in the real world.


James Harris

In article 
<f9b32b32-ef4b-4dda-917d-b5821d5f3488@u12g2000prd.googlegroups.com>,
 JSH <jstevh@gmail.com> wrote:
> Just like people replying in this thread do not want a best solution
> to the traveling salesman problem.

No, everyone here would like a polynomial time solution to TSP.  
However, what you've proposed does not solve TSP at all, let alone in 
polynomial time.  To be a solution to TSP, it has to work for *all* 
instances of TSP.  You were given a small instance for which it did not 
work.

Heck, if we are going to count a problem solved with algorithms that 
only solve some instances, then I have a very fast solution to integer 
factoring:

   Let N be the number we want to factor.
   Let a = floor(sqrt(N))
   Let b = floor(N/a)

   Then the factors of N are a and b.

Let's try it, with, say, N=63.

   a = floor(sqrt(63)) = 7
   b = floor(63/7) = 9

9*7 = 63.  Hey, it works!  I've solved factoring!  And my algorithm is 
fast, too...one sqrt, one division, two floors.  Too bad you wasted all 
that time on Surrogate Factoring when it turns out that factoring is 
trivial!

-- 
--Tim Smith

JSH wrote:
> The improperly formulated form of the TSP does not have distance
> information between all nodes, though practitioners intuitively use
> such information or intuitively realize it still is in the problem by
> way of the weights themselves.
> 
> So it's just sloppy formulation of the problem.

BWAAAA-HA-HA-HA-HA-HAAAAA!

-- 
Lew


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
[Freemasonry, occult, Kabbalah, KKK,
deception, Illuminati, NWO]

"We shall unleash the Nihilists and Atheists,
and we shall provoke a formidable
social cataclysm which in all its horror
will show clearly to the nations the
effects of absolute atheism, origin
of savagery and of the most bloody turmoil.
Then everywhere, the citizens, obliged to defend
themselves against the world minority of
revolutionaries, will exterminate those
destroyers of civilization, and the multitude,
disillusioned with Christianity, whose deistic
spirits will be from that moment without compass,
anxious for an ideal, but without knowing where
to render its adoration, will receive the pure
doctrine of brought finally out in the
public view, a manifestation which will result
from the general reactionary movement which will
follow the destruction of Christianity and atheism,
both conquered and exterminated at the same time."

    Illustrious Albert Pike 33�
    Letter 15 August 1871 
    Addressed to Grand Master Guiseppie Mazzini 33�

[Pike, the founder of KKK, was the leader of the U.S.
Scottish Rite Masonry (who was called the
"Sovereign Pontiff of Universal Freemasonry,"
the "Prophet of Freemasonry" and the
"greatest Freemason of the nineteenth century."),
and one of the "high priests" of freemasonry.

He became a Convicted War Criminal in a
War Crimes Trial held after the Civil Wars end.
Pike was found guilty of treason and jailed.
He had fled to British Territory in Canada.

Pike only returned to the U.S. after his hand picked
Scottish Rite Succsessor James Richardon 33� got a pardon
for him after making President Andrew Johnson a 33�
Scottish Rite Mason in a ceremony held inside the
White House itself!]

On Jul 19, 9:03=A0pm, Tim Smith <reply_in_gr...@mouse-potato.com> wrote:
> In article
> <f9b32b32-ef4b-4dda-917d-b5821d5f3...@u12g2000prd.googlegroups.com>,
>
> =A0JSH <jst...@gmail.com> wrote:
> > Just like people replying in this thread do not want a best solution
> > to the traveling salesman problem.
>
> No, everyone here would like a polynomial time solution to TSP. =A0
> However, what you've proposed does not solve TSP at all, let alone in
> polynomial time. =A0To be a solution to TSP, it has to work for *all*
> instances of TSP. =A0You were given a small instance for which it did not
> work.

Really?  I missed that.  Oh, I didn't read all replies in this
thread.  I guess maybe I should before I comment further about my
latest algorithm...

> Heck, if we are going to count a problem solved with algorithms that
> only solve some instances, then I have a very fast solution to integer
> factoring:
>
> =A0 =A0Let N be the number we want to factor.
> =A0 =A0Let a =3D floor(sqrt(N))
> =A0 =A0Let b =3D floor(N/a)
>
> =A0 =A0Then the factors of N are a and b.
>

No point in being silly.

I have no problems with a demonstration that the idea is wrong.  What
I have a problem with is people telling me it can't be an algorithm
for TSP because it relies on the straight line distance between nodes
as well as weights, and other people can just use weights between
nodes without the distance info.

And I notice you simply deleted out what I said about my prime
counting function.

That's the reality I face: math people will simply ignore what they do
not like.

I won't bore readers here with a digression on how easily I proved
some rather big things just by using a multi-variable P(x,y) function
versus the classical approach of a single variable pi(x) function--for
those wondering the issue here is counting primes so to 100, you have
pi(100) =3D 25, while with my function you have P(100,10) =3D 25.

But I assure you that if you wish to feel sick to your stomach about
even top mathematicians like Odlyzko and Lagarias who I have been in
contact by email on this issue, then do even the most basic research
on what I found, and see what they did in response.

They are traitors to their field and to the pursuit of human knowledge
and the only thing I can figure is that they are afraid of simplifying
research removing a cash cow.

I suggest that they do not like simple answers that I guess they fear
will remove reasons for funding because the main questions are
answered.


James Harris

On Jul 18, 8:06=A0am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> JSH wrote:
> > On Jul 18, 7:35 am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> >> Therefore, any solution to TSP must be able to produce a result given
> >> /solely/ the vertexes and the weights of the edges (and the total weig=
ht
> >> to search for, in the decision form of the problem). Any algorithm whi=
ch
> >> requires more information than that cannot solve the TSP.
>
> > That is a leap and is not provable. =A0(Try it.)
>
> It cannot solve the TSP because the TSP doesn't give it sufficient
> information.

The improperly formulated form of the TSP does not have distance
information between all nodes, though practitioners intuitively use
such information or intuitively realize it still is in the problem by
way of the weights themselves.

So it's just sloppy formulation of the problem.

> > In any REAL WORLD problem, there is a distance between the nodes.
>
> That doesn't mean that the distance is meaningful in any way. In the

Why?  Because you say so despite every rational person reading your
reply knowing that distance IS important when it comes to traveling in
the real world?

Can you truly plan a trip with say, just cost information alone?

PEOPLE ALREADY USE DISTANCE INFORMATION IN THE REAL WORLD.

Only academics would argue this point where an over abstraction has
forced important information to be inferred.

> case of printed-circuit board design, the distance between two holes is
> unimportant if the drill bit has to be changed between them.

That is an additional weight.

> > I say the problem is not solvable with a polynomial time algorithm
> > without using that information!!!
>
> Then you say P !=3D NP, because the problem does not *permit* you to have
> that information.

But that's false.

Even with just a single weight you can graph the nodes one a two-
dimensional plane and simply give them a distance from each node equal
to the size of the weight in whatever units you prefer, though you'd
have to adjust them so that you get all the weights correctly, but
then you'd have physical coordinates.  If you have multiple weights
you'd just pick one.

So why make a claim that is so trivially wrong to hold on to a
position denying the most basic reality that in real world travel or
other areas where the problem is relevant, there is distance
information between nodes?

I'm going to scan down and see if you have anything better.  If not
I'll quit replying at this point.


James Harris

On Jul 18, 9:42=A0am, Patricia Shanahan <p...@acm.org> wrote:
> JSH wrote:
> > On Jul 17, 9:28 pm, Patricia Shanahan <p...@acm.org> wrote:
> >> JSH wrote:
> >>> On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
> >> ...
> >>>> Here's an example I'd like to see worked using your algorithm:
> >>>> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from =
A to
> >>>> B is the same cost as B to A.
> >>>> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs =
are 1.
> >>>> Patricia
> >>> My idea won't work with that example.
> >> In that case, your idea is obviously not an algorithm for Traveling
> >> Salesman, which explains why I didn't understand how it could possibly=
 work.
>
> >> Perhaps you need to state what, if anything, it does solve?
>
> >> Patricia
>
> > I've replied before but I figured out a way to prove your intuition is
> > part of your supposed solutions: say the path from C,A goes around the
> > moon? =A0While all other paths are 100 miles long, what is the proper
> > answer?
>
> ...
>
> Traveling Salesman is about *cost* of travel between the cities, or more
> abstractly about weights associated with graph edges, not *distance*.
> Anyone who has paid for airline tickets or used toll roads knows cost
> and distance are not necessarily proportionate to each other.

That is true, which is why you have weights in TSP.

Distance is in actuality one weight that is always there, whether it's
stated or inferred as people intuitively realize that the further
something is from them and their final destination the greater the
"cost" of that trip.

Academics I'd guess over abstracted the problem and threw out that
information and tried to just use other weights which may or may not
correlate closely with distance but often in the real world do
correlate well with distance.

So if our traveling salesman lives in New York and at one leg of his
trip has to go to Hong Kong, then he may feel a greater "weight" with
the longer trip than he will about another trip to Chicago, simply
because one is closer than the other, regardless of what he will pay
for airplane flights.

Academics throwing out important information for no good reason is an
oddly common problem.

When challenged on it, they typically talk down to other people as if
challenging them about throwing away valuable information is stupid.

> In my example, it happens that cities A, B, D, and E are all in the same
> country. That country's public transportation system directly connects
> each pair, and has a flat $1 fare. Unfortunately for our salesman, C is
> in a different country with no legal border crossings.

Which is an additional "weight" on the salesman's mind!!!

Or do you deny that?

It appears you have no clue what a "weight" is in the problem.

A weight is ANY limiting factor which impacts the decision problem of
which path is preferable.

You went to some school where you got taught the problem one way,
right?

If it was a really good school they should also have taught you some
flexibility in your thinking.

Problem solving is not about going just by what you were taught!!!

Learning can be about un-learning, and growth can be about
perspective.

> Gang X controls illegal activity in D and E. X charges $2000 to smuggle
> someone between either of those cities and C. Gang Y, which controls
> illegal activity in cities A and B, is establishing its own smuggling
> route to C. In order to attract business to the new route, Y only
> charges $1000 to smuggle a person between a city it controls and C.
>
> Neither gang can safely smuggle to or from a city controlled by the
> other. The police force in C ignores smuggling, but arrests anyone
> involved in a gang fight, so either gang can smuggle to or from C
> without any risk of interference by the other gang.
>
> If you are dealing with distances, not costs, you are not solving the
> problem conventionally known as "Traveling Salesman". You may be solving

You say so, why?

Because some person a long time ago told you so?

Because you were taught to ignore the most basic information that you
yourself probably use in the real world, as you over abstracted the
problem as an academic exercise?

> some other problem that you choose, rather confusingly, to call
> "Traveling Salesman", but if so you need to define it, so that the rest
> of us know what you are talking about.
>
> Patricia

I worked a simple example with 4 nodes.  Um, it seemed to me that at
the end of that example I had a TSP problem solution.

So your assertion is a direct denial of a simple demonstration.

What really can I do in the face of obstinate denial?

Nothing.  Discussion ends up being futile at that point as one person
refuses to be reasonable.

Which is what I often face with my research: some person tells me what
must be, and refuses to acknowledge the most basic things including
direct examples or mathematical proof.

There is no way to go beyond that point while the other person so
behaves.


James Harris

JSH wrote:
> The improperly formulated form of the TSP does not have distance
> information between all nodes, though practitioners intuitively use
> such information or intuitively realize it still is in the problem by
> way of the weights themselves.
> 
> So it's just sloppy formulation of the problem.

BWAAAA-HA-HA-HA-HA-HAAAAA!

-- 
Lew

On Jul 20, 1:46=A0pm, Lew <com.lewscanon@lew> wrote:
> JSH wrote:
> > The improperly formulated form of the TSP does not have distance
> > information between all nodes, though practitioners intuitively use
> > such information or intuitively realize it still is in the problem by
> > way of the weights themselves.
>
> > So it's just sloppy formulation of the problem.
>
> BWAAAA-HA-HA-HA-HA-HAAAAA!

Rather.  I'm reminded of another poster from several years ago, who
insisted that the halting problem would be solvable if only he were
permitted to modify the problem to include a "secure" output channel
or write-only region of memory which the user could read but which no
modification of the halting problem solver could access.  Arguments
that the halting problem is about computability and that all of those
can be simulated within a Turing machine without affecting the
solution one iota fell on deaf ears for a *very* long time.

Modifying the problem to make it easier to solve is not, and never has
been, a valid solution method.

-o

JSH wrote:

Academics throwing out important information for no good reason is an
oddly common problem.

Trolls flinging dung yet another. 

JSH wrote:
> On Jul 18, 8:06 am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
>> It cannot solve the TSP because the TSP doesn't give it sufficient
>> information.
> 
> The improperly formulated form of the TSP does not have distance
> information between all nodes, though practitioners intuitively use
> such information or intuitively realize it still is in the problem by
> way of the weights themselves.

Since you have stated that your intention is to solve P = NP, I would 
like to point out that you should really be considering the NP-complete 
version of the problem instead of even the NP-hard version or the 
"annotated" NP-hard version, regardless of its actual applicability.

Computational theory tries to look at /worst-case/ results, not 
/average-case/ or /best-case/.

> PEOPLE ALREADY USE DISTANCE INFORMATION IN THE REAL WORLD.

And P = NP is precisely not about the real world. Obligatory XKCD 
reference: <http://www.xkcd.com/435/>. Leave application to the 
programmers, mathematical problems are about esoteric results.

>> Then you say P != NP, because the problem does not *permit* you to have
>> that information.
> 
> But that's false.
> 
> Even with just a single weight you can graph the nodes one a two-
> dimensional plane and simply give them a distance from each node equal
> to the size of the weight in whatever units you prefer, though you'd
> have to adjust them so that you get all the weights correctly, but
> then you'd have physical coordinates.  If you have multiple weights
> you'd just pick one.

So you've finally explained: the distance is, in lieu of other 
information, the weight. Which, I might add, is a backtrack from your 
previous statements that the distances were needed. Since the distance 
is a heuristic (and one that could potentially make time worse), why not 
just drop it in your algorithm and use the weights like everyone else?

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

In article 
<5b712ad1-d619-433f-a1ce-68b1be09d7a6@f40g2000pri.googlegroups.com>,
 JSH <jstevh@gmail.com> wrote:
> > No, everyone here would like a polynomial time solution to TSP. �
> > However, what you've proposed does not solve TSP at all, let alone in
> > polynomial time. �To be a solution to TSP, it has to work for *all*
> > instances of TSP. �You were given a small instance for which it did not
> > work.
> 
> Really?  I missed that.  Oh, I didn't read all replies in this
> thread.  I guess maybe I should before I comment further about my
> latest algorithm...

No, you did not miss it.  You read it, and acknowledged that your 
algorithm did not handle it:

<http://groups.google.com/group/comp.lang.java.programmer/msg/a81862346a2
a576a?hl=en&dmode=source>

You'd have a better chance of success in all your endeavors if you could 
get your multiple personalities to each be aware of what the others are 
doing.

-- 
--Tim Smith

> Why?  Because you say so despite every rational person reading your
> reply knowing that distance IS important when it comes to traveling in
> the real world?
>
> Can you truly plan a trip with say, just cost information alone?
>
> PEOPLE ALREADY USE DISTANCE INFORMATION IN THE REAL WORLD.
>
Sometimes, but not always. Simple example: two possible routes go from
A to B. Route one route is shorter, but goes through a major city with
lots of traffic and a toll road. Route 2 is longer,  but goes through
the country and there are no toll roads. How do you weight these two
routes? Depending on what quantity I choose to measure as being
important, the routes can have a wide variety of weights. It is easy
to envision scenarios where route one will have a larger weight than
route 2, and it is equally easy to envision cases where route one will
have a smaller weight than route 2. It is also totally possible to
have weights that have absolutely no distance dependence at all
associated with them (maybe I rank the routes based on how scenic a
view they offer or the risk of me being car-jacked or by the measure
of safety I feel if my car breaks down somewhere on the way).

Despite your (self-proclaimed) creativity, you can't seem to liberate
your mind from the concrete. Pity.

M

JSH wrote:
> Can you truly plan a trip with say, just cost information alone?

OMG you think "cost" means....

OMG OMG OMG OMG OMG OMG!

-- 
John W. Kennedy
  "The pathetic hope that the White House will turn a Caligula into a 
Marcus Aurelius is as na�ve as the fear that ultimate power inevitably 
corrupts."
   -- James D. Barber (1930-2004)

On Jul 20, 12:15=A0pm, Tim Smith <reply_in_gr...@mouse-potato.com>
wrote:
> In article
> <5b712ad1-d619-433f-a1ce-68b1be09d...@f40g2000pri.googlegroups.com>,
>
> =A0JSH <jst...@gmail.com> wrote:
> > > No, everyone here would like a polynomial time solution to TSP. =A0
> > > However, what you've proposed does not solve TSP at all, let alone in
> > > polynomial time. =A0To be a solution to TSP, it has to work for *all*
> > > instances of TSP. =A0You were given a small instance for which it did=
 not
> > > work.
>
> > Really? =A0I missed that. =A0Oh, I didn't read all replies in this
> > thread. =A0I guess maybe I should before I comment further about my
> > latest algorithm...
>
> No, you did not miss it. =A0You read it, and acknowledged that your
> algorithm did not handle it:
>
> <http://groups.google.com/group/comp.lang.java.programmer/msg/a81862346a2
> a576a?hl=3Den&dmode=3Dsource>
>
> You'd have a better chance of success in all your endeavors if you could
> get your multiple personalities to each be aware of what the others are
> doing.
>
> --
> --Tim Smith

Yes and no.  The pure algorithm when faced with exactly three nodes
where T_1 is at N_1 and T_2 is at the end node, leaving only one node
available, will exit, but the solution then is that T_1 moves to the
only node left (or T_2 does).

Which I noted in my replies on this subject.

One of the tiring things about these kinds of discussions is that
their length and so many replies depends on people refusing to
acknowledge solutions already presented.

So Patricia Shanahan and Joshua Cranmer kept ignoring the reality of a
worked simple example to claim that I wasn't actually doing TSP!

And you declare boldly that a case isn't handled when I replied
handling that case.

The issue here is willful denial.

Against it, proof does not work.  Explanation does not work.

And I've been down this road before: people like you clog up the
discussion, fight against getting to the bottom of things, and make a
mess so that you can hide the truth.

But here, you're fighting to hide an algorithm to solve the TSP, and
prove that P=3DNP, once and for all.

Why would any person do that?

I suggest readers understand that academic evolution may have been
towards complexity against solution so that from game theory our
current system rewards people for denying simple answers for complex
ones that drive public funding.

We pay people to get complex answers, not to just get answers.

It's publish or perish in the academic world.  Simple answers do not
necessarily drive a lot of papers.

We trained our academics to fight against simplicity, and we're paying
the price all over our world.


James Harris

JSH wrote:
> The issue here is willful denial.
> 
> Against it, proof does not work.  Explanation does not work.

Indeed.  That is accurate.

-- 
Lew

JSH wrote:
> On Jul 18, 9:42 am, Patricia Shanahan <p...@acm.org> wrote:
....
>> If you are dealing with distances, not costs, you are not solving the
>> problem conventionally known as "Traveling Salesman". You may be solving
> 
> You say so, why?
> 
> Because some person a long time ago told you so?

No, I say so because I have seen equivalent definitions many times in
books, classes, and papers over a period of decades, and you are the
first person I have seen apply the term to anything different.

The definition I am using is consistent, for example, with the one in
Garey and Johnson's "Computers and Intractability A Guide to the Theory
of NP-Completeness". It is the version of the problem that I have seen
proved NP-Complete. Everyone except you who has expressed an opinion on
the issue in this thread seems to agree on the definition.

This is a matter of communication. Maybe your definition of the problem
would be a superior one in some absolute sense, though that is
impossible to tell without seeing your definition. However, effective
communication depends on consensus terminology. There is a specific
problem that is commonly called "Traveling Salesman". My example is a
valid instance of that problem, but not, apparently, of the problem you
call "Traveling Salesman".

Why not just post a precise definition of the problem you are trying to
solve?

> I worked a simple example with 4 nodes.  Um, it seemed to me that at
> the end of that example I had a TSP problem solution.

Finding a combination of simple algorithm and special case for which the
algorithm is correct and efficient is far, far too easy to be
interesting. The challenge is to provide an algorithm that efficiently
solves *any* instance of some difficult problem.

Patricia

On Jul 20, 3:17=A0pm, Lew <com.lewscanon@lew> wrote:
> JSH wrote:
> > The issue here is willful denial.
>
> > Against it, proof does not work. =A0Explanation does not work.
>
> Indeed. =A0That is accurate.
>
> --
> Lew

Yup.  And of course both sides say it's the other side that refuses to
be reasonable.

I have publication to know about the truth.  I have proofs that I've
explained to top mathematicians including one in person, to know the
truth.  And I have my results that do fun things like count prime
numbers to know the truth.

My final assessment is that often in our world people lie to maintain
social status.

So problems are not solved simply because the "wrong person" solves a
problem.

The not discussed reality here is that people like you are willing to
not only ignore a solution to something like the TSP because you've
decided that your social world cannot handle me in a certain position,
but you will work hard at other ways of approaching the problem--
wasting your time and energy--because the real issue is your social
status.

Ok, evolution has the answer for people like you.

As our world warms up and people like you fight for that social
status, and ignore solutions for that social status, it will die with
your groups.

As the world population dies, so will the behavior as evolution takes
over.

When there is no one around who cares about who solves the problem but
only that the problem is solved, then that path of the optimal
algorithm will have completed.

At the end of the day, problem solving is ultimately about life and
death.

On that point then, I say that time will tell.  Nations will fall.
Civilizations will crumble, but those who can solve the problems
necessary to stay alive, by definition, will continue.

It is the one way that life IS fair.


James Harris

On Jul 20, 3:35=A0pm, JSH <jst...@gmail.com> wrote:
> On Jul 20, 3:17=A0pm, Lew <com.lewscanon@lew> wrote:
>
> > JSH wrote:
> > > The issue here is willful denial.
>
> > > Against it, proof does not work. =A0Explanation does not work.
>
> > Indeed. =A0That is accurate.
>
> > --
> > Lew
>
> Yup. =A0And of course both sides say it's the other side that refuses to
> be reasonable.
>
> I have publication to know about the truth. =A0I have proofs that I've
> explained to top mathematicians including one in person, to know the
> truth. =A0And I have my results that do fun things like count prime
> numbers to know the truth.
>
> My final assessment is that often in our world people lie to maintain
> social status.
>
> So problems are not solved simply because the "wrong person" solves a
> problem.
>
> The not discussed reality here is that people like you are willing to
> not only ignore a solution to something like the TSP because you've
> decided that your social world cannot handle me in a certain position,
> but you will work hard at other ways of approaching the problem--
> wasting your time and energy--because the real issue is your social
> status.
>
> Ok, evolution has the answer for people like you.
>
> As our world warms up and people like you fight for that social
> status, and ignore solutions for that social status, it will die with
> your groups.
>
> As the world population dies, so will the behavior as evolution takes
> over.
>

Ok, way over the top as clearly this discussion has degenerated to a
point where there is no point in continuing, so after this post, I'm
done for now.

I know how this goes having had proof after proof, result after
result, blocked by people who literally would often call me insane.

Proof does not always work in the real world.

It's not fair, but that's the reality.

But the dark side of it is that catastrophe is too often preventable,
but is not prevented because there are comfortable people who say
nothing is wrong.

Like consider the economy in the US today: many rich and powerful
people feel no problems so like the Bush advisor talking of a "mental
recession", they see no reason for meaningful change.

Or for better solutions...

Oh yeah, global warming will not be addressed by rich and powerful
nations for that reason--until and if it takes away their richness and
power.


James Harris

Patricia Shanahan wrote:
> Finding a combination of simple algorithm and special case for which the
> algorithm is correct and efficient is far, far too easy to be
> interesting. The challenge is to provide an algorithm that efficiently
> solves *any* instance of some difficult problem.

Well, doesn't that depend on the individual special case? I mean, say 
someone came up with an algorithm that could be proven to work 
efficiently for n<1729 cities, wouldn't that be interesting -- at least 
until something better came along? Wasn't the five-color proof 
interesting? (I grant that what JSH is suggesting here does not seem to 
be interesting, but that's a different issue.)

-- 
John W. Kennedy
  "Information is light. Information, in itself, about anything, is light."
   -- Tom Stoppard. "Night and Day"

John W Kennedy wrote:
> Patricia Shanahan wrote:
>> Finding a combination of simple algorithm and special case for which the
>> algorithm is correct and efficient is far, far too easy to be
>> interesting. The challenge is to provide an algorithm that efficiently
>> solves *any* instance of some difficult problem.
> 
> Well, doesn't that depend on the individual special case? I mean, say 
> someone came up with an algorithm that could be proven to work 
> efficiently for n<1729 cities, wouldn't that be interesting -- at least 
> until something better came along? Wasn't the five-color proof 
> interesting? (I grant that what JSH is suggesting here does not seem to 
> be interesting, but that's a different issue.)
> 

I'm assuming one is allowed to choose both the algorithm and the simple
case, as JSH is doing when he argues that I should be convinced that an
algorithm he wrote works because it gets the right answer for a single
example he selected.

Patricia

>
> We pay people to get complex answers, not to just get answers.
>
> It's publish or perish in the academic world.  Simple answers do not
> necessarily drive a lot of papers.

What you call "complex" is really "simple". Problems are generalized
because it makes possible the solution of a wide range of problems
with the same structure. That is simplification, not complexity. Such
work may be detailed or difficult to understand, but one thing it is
*not* is complex in the sense of making things unnecessarily
complicated. To me, what you do, going down a million blind alleys
without a clue, is inefficient and unnecessarily complex.

The sad fact is that the simple solution train left the station a
couple of centuries ago. If you want problems dealing with the
physical world, having nice simple solutions that can be solved on the
back of an envelope, pick up a book on the history of math and work
through some of the problems Bernoulli, Descartes, and Fermat tackled
back in the 1600 and 1700's. They may be more your speed and
consistent with your abilities.

M

JSH wrote:
> So Patricia Shanahan and Joshua Cranmer kept ignoring the reality of a
> worked simple example to claim that I wasn't actually doing TSP!

A point already belabored to death by others, but I wish to point out 
again that one example is not sufficient to demonstrate the efficacy of 
a solution. You have not shown us any strenuous cases--even four nodes 
alone is insufficient to demonstrate a solution since there is (in your 
algorithm) essentially but a choice between two that needs to be 
decided. That's why I suggest around 7 to 8, small enough to be handled 
easily by manpower but big enough to not be trivial.

> Against it, proof does not work.  Explanation does not work.

You have provided neither (to the satisfaction of the heavyweights in 
this group), so how can you say?

> But here, you're fighting to hide an algorithm to solve the TSP, and
> prove that P=NP, once and for all.

Actually, as I mentioned earlier, I personally do believe that P=NP, I 
just don't believe that your algorithm solves it.

If, in fact, you are so sure of your solution, why don't you submit it 
to the Clay Institute to claim the prize?

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

JSH schrieb:
> On Jul 20, 3:35 pm, JSH <jst...@gmail.com> wrote:
>> On Jul 20, 3:17 pm, Lew <com.lewscanon@lew> wrote:
>>
>>> JSH wrote:
>>>> The issue here is willful denial.
>>>> Against it, proof does not work.  Explanation does not work.
>>> Indeed.  That is accurate.
>>> --
>>> Lew
>> Yup.  And of course both sides say it's the other side that refuses to
>> be reasonable.
>>
>> I have publication to know about the truth.  I have proofs that I've
>> explained to top mathematicians including one in person, to know the
>> truth.  And I have my results that do fun things like count prime
>> numbers to know the truth.
>>
>> My final assessment is that often in our world people lie to maintain
>> social status.
>>
>> So problems are not solved simply because the "wrong person" solves a
>> problem.
>>
>> The not discussed reality here is that people like you are willing to
>> not only ignore a solution to something like the TSP because you've
>> decided that your social world cannot handle me in a certain position,
>> but you will work hard at other ways of approaching the problem--
>> wasting your time and energy--because the real issue is your social
>> status.
>>
>> Ok, evolution has the answer for people like you.
>>
>> As our world warms up and people like you fight for that social
>> status, and ignore solutions for that social status, it will die with
>> your groups.
>>
>> As the world population dies, so will the behavior as evolution takes
>> over.
>>
> 
> Ok, way over the top as clearly this discussion has degenerated to a
> point where there is no point in continuing, so after this post, I'm
> done for now.
> 
> I know how this goes having had proof after proof, result after
> result, blocked by people who literally would often call me insane.
> 
> Proof does not always work in the real world.
> 
> It's not fair, but that's the reality.
> 
> But the dark side of it is that catastrophe is too often preventable,
> but is not prevented because there are comfortable people who say
> nothing is wrong.
> 
> Like consider the economy in the US today: many rich and powerful
> people feel no problems so like the Bush advisor talking of a "mental
> recession", they see no reason for meaningful change.
> 
> Or for better solutions...
> 
> Oh yeah, global warming will not be addressed by rich and powerful
> nations for that reason--until and if it takes away their richness and
> power.
> 
> 
> James Harris

I personnaly would recommend you to write down your proof that the 
algorithm works in formal language.
If you believe in it and it works that shouldn't be too hard. After 
having it written down either flaws might be better visible or if 
written down in program code obviously findable.
As you might have realised asking here for help writing it is probably 
not gonna work.

Christian

Joshua Cranmer schrieb:

> 
> Actually, as I mentioned earlier, I personally do believe that P=NP, I 
> just don't believe that your algorithm solves it.

Would be interesting to have a voting in this group to what others 
believe.. independent of this threads algo.

Personally Iwould rather see P != NP as  P = NP would have some very 
strange implications. Most important for me:
"Effective guessing is possible". That one can actually guess some 
solution without knowloedge in a way that is better than just picking 
something randomly.

Anyone else want to make a guess?


Once had the idea to open a betting agency for geeks where you could bet 
on mathematical problems. With the interest of the bets one could 
finance Mathematical research to get the problems Verified or Falsified.

Christian

On 20 Jul, 18:33, JSH <jst...@gmail.com> wrote:
> On Jul 18, 8:06 am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
>
> > Then you say P != NP, because the problem does not *permit* you to have
> > that information.
>
> But that's false.
>
> Even with just a single weight you can graph the nodes one a two-
> dimensional plane and simply give them a distance from each node equal
> to the size of the weight in whatever units you prefer, though you'd
> have to adjust them so that you get all the weights correctly, but
> then you'd have physical coordinates.

No, in general you can't. Several people have already independently
pointed out an obvious way to construct examples of weighted graphs
which can't be embedded in a 2-dimensional plane (or any metric space)
with distances equal to the weights, namely by constructing a weighted
graph which doesn't satisfy the triangle inequality.

On Jul 21, 3:40=A0pm, Rotwang <sg...@hotmail.co.uk> wrote:
> On 20 Jul, 18:33, JSH <jst...@gmail.com> wrote:
>
> > On Jul 18, 8:06 am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
>
> > > Then you say P !=3D NP, because the problem does not *permit* you to =
have
> > > that information.
>
> > But that's false.
>
> > Even with just a single weight you can graph the nodes one a two-
> > dimensional plane and simply give them a distance from each node equal
> > to the size of the weight in whatever units you prefer, though you'd
> > have to adjust them so that you get all the weights correctly, but
> > then you'd have physical coordinates.
>
> No, in general you can't. Several people have already independently
> pointed out an obvious way to construct examples of weighted graphs
> which can't be embedded in a 2-dimensional plane (or any metric space)
> with distances equal to the weights, namely by constructing a weighted
> graph which doesn't satisfy the triangle inequality.

My understanding of James's "algorithm" is this:  To each edge E, you
are given
a weight w(E).  Now immerse your graph in 2-space any way you like
(surely you
can always do this; just place the vertices pretty much anywhere,
subject to the
condition that no two edges overlap); this assigns to each edge E a
length
l(E).  Now do something or another that involves both the l's and the
w's,
and in the end you'll get a result that depends on just the w's.

On the face of it, this sounds implausible but not impossible.  On the
other
hand, James is probably far too confused (and certainly far too
stupid) to
figure out whether this is really what he means or not.

On Fri, 18 Jul 2008 00:24:51 +0200, Christian wrote:

> Ah I love conspiracy theorys. Some Atheist told me that Conspiracy
> theorys are in reality just a conspiracy to keep people believing in
> something. A replacement for God without actually becoming Atheist. (The
> Vatican must be behind this)


Ooh, that's a good one because, of course, you cannot disprove it.  Also, 
it's nicely self-referential because it, of course, *is* a conspiracy 
theory, whose purpose, according to said theory, is to make people 
believe in a conspiracy theory, such as itself...ouch, my head hurts :)



-Thufir

In article <488477e4$0$7691$9b622d9e@news.freenet.de>,
 Christian <fakemail@xyz.de> wrote:
> Personally Iwould rather see P != NP as  P = NP would have some very 
> strange implications. Most important for me:

After learning about zero knowledge proofs, I find it impossible to find 
anything else strange. :-)

For those who have not heard of zero knowledge proofs: it has been shown 
that for any mathematical theorem that you have a proof for, it is 
possible to demonstrate to someone else that you do indeed have a 
correct proof of the theorem, without actually showing them the proof, 
or even given them any information at all about it, other than the fact 
that it exists and you know it!

-- 
--Tim Smith

Tim Smith wrote:
> For those who have not heard of zero knowledge proofs: it has been shown 
> that for any mathematical theorem that you have a proof for, it is 
> possible to demonstrate to someone else that you do indeed have a 
> correct proof of the theorem, without actually showing them the proof, 
> or even given them any information at all about it, other than the fact 
> that it exists and you know it!

One assumes that you have a proof of that, and we can know that without 
anything more than your "fact" that it exists and that you know it.

-- 
Lew

Paul Millard wrote:
> For those who have not heard of zero knowledge proofs: it has been shown 
> that for any mathematical theorem that you have a proof for, it is 
> possible to demonstrate to someone else that you do indeed have a 
> correct proof of the theorem, without actually showing them the proof, 
> or even given them any information at all about it, other than the fact 
> that it exists and you know it!

One prescribes that you have a self-sacrifice of that, and we can know that without
anything more than your "seizure" that it disintegrates and that you know it.

-- 
Lew


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
"It is clear our nation is reliant upon big foreign oil.
More and more of our imports come from overseas."

--- Adolph Bush,
    Beaverton, Ore., Sep. 25, 2000

In article 
<49a7f060-b7eb-4812-99cc-8e3b315f5986@h1g2000prh.googlegroups.com>,
 JSH <jstevh@gmail.com> wrote:

> On Jul 17, 9:28�pm, Patricia Shanahan <p...@acm.org> wrote:
> > JSH wrote:
> > > On Jul 16, 10:11 pm, Patricia Shanahan <p...@acm.org> wrote:
> > ...
> > >> Here's an example I'd like to see worked using your algorithm:
> >
> > >> Cities A, B, C, D, E. I'm assuming symmetrical costs - getting from A to
> > >> B is the same cost as B to A.
> >
> > >> C,A is 1000. C,B is 1000. C,D is 2000. C,E is 2000. All other costs are 1.
> >
> > >> Patricia
> >
> > > My idea won't work with that example.
> >
> > In that case, your idea is obviously not an algorithm for Traveling
> > Salesman, which explains why I didn't understand how it could possibly work.
> >
> > Perhaps you need to state what, if anything, it does solve?
> >
> > Patricia
> 
> I've replied before but I figured out a way to prove your intuition is
> part of your supposed solutions: say the path from C,A goes around the
> moon?  While all other paths are 100 miles long, what is the proper
> answer?
> 
> You may argue: but no one can go around the moon!
> 
> That's not REASONABLE, right?
> 
> But what does that have to do with a properly stated problem?
> 
> Why can't I have one path loop around the moon?
> 
> Oh, I know, no way you can loop someone around the moon for $1000 U.S,
> right?
> 
> Well, yeah, I KNOW that and you know that, but how does that relate to
> a properly stated problem?
> 
> See what I mean?  Your GUT instinct is part of what you think the
> answers are to the problem and that gut instinct intuitively knows
> that the distances between nodes are not outrageously different as you
> can't go to the freaking moon cheaper than you can walk down the
> goddamn street.
> 
> Now can you?
> 
> 
> James Harris

Looping around the moon since 1996.

<http://groups.google.com/group/sci.math/msg/ae93014aa588d803?hl=en&dmode=source>

-- 
Michael Press