My OPE & the Euclicidean TSP

[Patricia Shanahan]

Simpler to me if it's all incorrect. Kind of preferable.

Good, because, although I like to keep an open mind, "it's all
incorrect" is the way to bet on proposed polynomial time algorithms for
NP-complete problems.

Have you ever been on a product development team from the beginning
all the way to the end? ...

Many, many times, on a wide range of project sizes, including complete
computer system developments, hardware as well as software.

However, the issue here is simply coding an algorithm you know in a
language you know. That is tiny compared to any sort of product
development, even a small software application. It's more like a
fraction of one weeks' homework for a CS student taking an algorithms
course.

If you produce a working implementation of a polynomial time algorithm
for 2-D Euclidean TSP you will have no trouble at all getting all the
help you need on the rest of your project.

Patricia

 

[Alan Morgan]

A little while back I posted for a while on a creative algorithm I
came up with for tracing out a path through nodes, and discussions got
bogged down on the issue of whether or not it solved the TSP, where
the consensus of several members was that it did not.

If you have an algorithm which you claim solves the TSP then it is
hardly bogging down the discussion to debate whether or not it actually
does.

But I have made
a project for the full algorithm at Google Code for coding in java and
while the welcome mat for coders has been put out, I have no
responses, so I have decided to talk more about the algorithm here
with the Euclidean TSP as I realized it'd be simpler to explain.

First question: What problem does your algorithm actually solve?
What does it, for want of a better word, *do*?

Alan

 

[Tom Anderson]

Until then, you're in my "crank" pit, and still digging.

In case anyone's not seen it, Mr Harris has a whole section to himself
(albeit small) on crank.net:

http://www.crank.net/harris.html

If someone fancies writing an account of the TSP saga, i'm sure that could
be added.

tom

 

[Lits O'Hate]

Oh, that's wrong.

oops++;

 

[JSH]

Good, because, although I like to keep an open mind, "it's all
incorrect" is the way to bet on proposed polynomial time algorithms for
NP-complete problems.

Sounds ok to me...

I don't mind dis-interest, but it'd kind of be nice if you
demonstrated it more, by posting less, which may sound rude, but it's
about consistency.

You feel that there is nothing to my idea unless I prove it to you
with code. I have more than once stated I have no interest in doing
so, which to me sounds like all bases are covered, so I'm curious
about continued discussion with you.

Many, many times, on a wide range of project sizes, including complete
computer system developments, hardware as well as software.

Cool. I'll Google you. I'm curious now.

However, the issue here is simply coding an algorithm you know in a
language you know. That is tiny compared to any sort of product
development, even a small software application. It's more like a
fraction of one weeks' homework for a CS student taking an algorithms
course.

Yeah, if I do it half-way, and say, do a proof of concept program to
just tackle Euclidean TSP, but what if I did so, and had code that
showed tremendous promise?

Might I not have a herd of people suddenly interested?

I don't like herds.

I'm interested now in the people who might be interested even though
they think it's all crap, and have no evidence from me but the
algorithm and these discussions.

If none exists and I do it myself then it is mine alone.

I get to be the solo genius and share nothing.

If you produce a working implementation of a polynomial time algorithm
for 2-D Euclidean TSP you will have no trouble at all getting all the
help you need on the rest of your project.

Patricia

From the herd. I don't care about the herd as I see them as losers.

If no one wants in, fine. Eventually, down the line, I probably will
code my ideas, but if it's going to be me then it is going to be mine,
like my math and all my other research.

Part of what I've been doing is kind of checking as I was so
disappointed with my Class Viewer project which I see now as a
prototype which became a final version because I ended up by myself
for all the coding.

As an experiment I'm seeing if I can recruit with another idea and
mainly be an architect on the project, but if no, then, big deal, you
know?

I CAN do it all myself so what do I lose now by floating out the idea
in this way?

Nothing.

I get to discuss. Hang out. Have fun, and lose nothing.

I still wonder why you continue to discuss when our positions are
clear and your stated position is one of dis-interest in what you see
as something that must be flawed.

I, on the other hand, am perfectly consistent.

The solitary and angry maybe "mad" genius who stands against the world
and does things my way, and no other.

It is all my way.


James Harris

 

[JSH]

In case anyone's not seen it, Mr Harris has a whole section to himself
(albeit small) on crank.net:

http://www.crank.net/harris.html

Yeah Erik Max Francis put me on years ago. We did argue a bit way
back.

I think at one point he intimated that I should commit suicide.

Maybe he thinks putting me on that page might convince me.

If someone fancies writing an account of the TSP saga, i'm sure that could
be added.

Nope. He seems to have lost interest in updating the page. Of course
he is in San Jose and I live not far away. I have offered to chat.

Hey, you people do realize that I'm in the heart of the Java world? I
get invites to all kinds of nice things but just don't go.

Now you want to go along with someone calling me a crackpot?

Maybe all Java programmers are crazy? Eh? You too?

tom

Yeah. You're a true believer.

Do you even know Erik Max Francis? Ever been in San Jose?

What makes you think his webpage has any more validity then any other
webpage out there?

I know, you're a true believer, that's what.


James Harris

 

[Alan Morgan]

Sounds ok to me...

I don't mind dis-interest, but it'd kind of be nice if you
demonstrated it more, by posting less, which may sound rude, but it's
about consistency.

"May sound rude"? What would qualify as "definitely rude" in your
world?

You feel that there is nothing to my idea unless I prove it to you
with code.

No, I think she is suggesting that trying to decide if a gray suit or
a black suit would be more appropriate for your Nobel Prize acceptance
speech should probably wait until after you have done the research (I'd
go gray and wow them with a pink waist-coat, but that's just me).

You claim to have an algorithm that solves the Travelling Salesman
Problem (I think. Frankly, I no longer remember exactly what you claim).
Great, code that bad boy up. It shouldn't take a competent programmer
(which you appear to be) more than a couple of days. If you can't
rustle up the interest to do it then why should anyone else?

Alan

 

[JSH]

"May sound rude"?  What would qualify as "definitely rude" in your
world?

Patricia Shanahan doesn't believe I have anything. Fine. But why
does she feel a need to bother posting in this thread then?

I get a vibe that she is thinking about others as in, convincing them
that I have nothing.

Hey, why bother?

No, I think she is suggesting that trying to decide if a gray suit or
a black suit would be more appropriate for your Nobel Prize acceptance
speech should probably wait until after you have done the research (I'd
go gray and wow them with a pink waist-coat, but that's just me).

And that's how so many people are so predictable as don't you think I
know how it grinds on some of you to hear me go on as if I did
something great?

THAT is the point for many of you, what you know you will never
achieve, and your fury at the idea of someone you see as beneath you
making what you see as a claim to greatness.

You couldn't care less about discovery, or learning, or
accomplishment, as you care most of all about what you think comes
from great discovery or great accomplishment.

You focus on what you think is the prize.

You claim to have an algorithm that solves the Travelling Salesman
Problem (I think.  Frankly, I no longer remember exactly what you claim).
Great, code that bad boy up.  It shouldn't take a competent programmer
(which you appear to be) more than a couple of days.  If you can't
rustle up the interest to do it then why should anyone else?

Why should they? I say they should not. Given the convincing
arguments of so many of you, why should they bother?

I am not going to code anything now.

Repeatedly asking me for the same old thing over and over again will
not change my mind.

Maybe in a few months or maybe years if I'm alone on this I will code
it.

In the meantime I will if I wish, talk about it, despite not coding
it.

If you hate my freedom of speech in this regard then you are a
totalitarian idiot.

If you do not, then you have your own choices which include continued
replies which repeat old ground as if you cannot understand English.

You are free to do what you wish, as am I.

The replies in this thread are ludicrous as in too many!!!

What a waste of time.

I have been very consistent in my position.

Where is the intelligence in the behavior I'm seeing now?


James Harris

 

[JSH]

...

I don't see any need for a team project on this. Take a look athttp://groups.google.com/group/comp.lang.java.programmer/msg/c11bbb43...

I'm replying again here to emphasize what I saw here earlier.

If Patricia Shanahan sees nothing here then she can post nothing in
reply, but to post no interest is to do a direct contradiction.

If she wants to be political and convince others then she can make it
one of her jobs to do so for the NEXT time that I start a thread but I
wonder what payment she believes she will get for the effort?

Talk to people on the sci.math newsgroups: it can be a full-time job
over a period of years.

I know you Patricia because I've faced people like you before in the
math field.

If you are not interested then behave like a person who is goddamn not
interested.

If you are politician here then accept it and then accept your new job
replying to me and settle in for the years it may require from your
life.


James Harris

 

[JSH]

I've never done a 1.0 release on any project, mostly because I've never
planned out any of my personal projects before starting them and I
change my mind so many times the code's unbearable. I do have several
0.* releases: a Java decompiler that I'm about to start a bottom-to-top
rewrite (with planning this time!), a TB extension that integrates
mailing lists as a new account type, as well as a python TextTwist clone.

I have also produced a full read-only database library where I had to
completely reverse engineer the database specification based on existing
code and, at one point, decompile my own code because I discovered an
undocumented "feature" of hg. How long did that take me? Not even half a
year, most of which is because I have a limited amount of time to work
on stuff and cycle all my projects. If you want to see that code, it's
here: <https://bugzilla.mozilla.org/show_bug.cgi?id=424446> (don't let
the diff part throw you off. I wrote it by starting new files and then
replacing the old ones).


1,453 lines for my database reader, 1,072 for my WIP listarchive
extension, and 6,082 for my WIP decompiler, all of which I have been
working on in the past year alone (disclaimer: this is total file size,
although much of my code is on the sparser side of comments).

A 5K LOC project should be able to make a 1.0 release within a year if
it is well laid-out beforehand, even if only one person is working on it.


If you search for "mork reader", you will find a posting I have on the
subject as the second entry. Not bad for a project which currently only
exists as a patch to existing code.

"listarchive" brings my page up as the first result and my blog post on
the subject as the second result. Total age of project? Three months.

But something else to note is that Google results are somewhat biased.
I'm sure that hosting a project on sourceforge will put it on higher
results that hosting it on xxxfreehosting.com.

If I have an extremely WIP project and an internal library show up at
the top of the results, does that mean they're "world class"? No. It
just means that they are more visible than other projects of the same name.


Does gutting entire modules of major programs and replacing them with
working code count? 'Cause I have that covered fairly well.

Sorry, no. What counts in the real world is use. Putting something
out there that's yours that other people use, like Google has their
search engine, Microsoft has Windows.

I have to admit I don't know how many people around the world are
using Class Viewer and I don't know why Google and Yahoo! agree that
my webpage should come up #1 when you search on Class Viewer.

But reality of our world today is that does mean something even if you
think it doesn't, and I have some statistics to know that, say, my
blog related to the project this year so far has hits from 73
countries, though not a lot of hits, and I'd give you the country
count for my Class Viewer webpage but I didn't bother putting
analytics software on it.

My blogs across the board have hits so far according to Google
Analytics from 86 countries.

I've seen my little blurb about my project I wrote years ago when I
put it on SourceForge, never knowing it'd be it, translated into
languages around the world.

I get people from newsgroups who push the idea that I'm a crackpot as
I've bothered to argue on newsgroups for years and it's an easy thing
for people to do who can't comprehend the world I live in as I'm some
guy they reply to on newsgroups. You think you know you're on my
level. But you're not.

You don't want to hear about other people who listen to me and in what
places or know what in your world has to do with me, or what you might
not have if I hadn't done certain things years ago.

All I have to do is argue with you and you see yourself as above me,
not even my equal, but above me, so people like that Erik Max Francis
page without even knowing who he is.

Nope. You don't get credit in the real world for anything but
demonstrable results where you can say, yeah, people use what you
made, and it's not about recognition either.

Do you know who the people who engineered LCD TV's? Maybe you do. I
don't.

Know who came up with that new lightbulb that saves energy? I don't.

Thomas Edison may have been the last really known inventor.

Our brave new world doesn't care about the people who invent things.

It only cares about the inventions and you don't need the inventor
once you have the invention, now do you?

You have no idea how much of your world has been impacted by me. No
clue, and that is the reality of the new world.

So yeah people. There are no accolades for you down the line. No
great prize for building things.

Your best bet is to build something you can sell to some big company
like Google or Microsoft (and no I haven't) as you will never be
famous from what you make. Never. Those days have died.

Society has evolved beyond celebrating inventors and discoverers.


James Harris

 

[Joshua Cranmer]

One feature I think many would find helpful is the ability to input the
graph via a GUI editor.

I decided to make this feature myself. The code is here (it's a single
file): <http://www.prism.gatech.edu/~jcranmer3/TSPTest.java>.

As a quick hack session, it has very few comments. Unfortunately, Java
6.0 only comes with the Rhino scripting engine, forcing you to put your
custom engines in JavaScript for the custom algorithm editor. If I feel
up to it, and you ask nicely, I'll put together a JAR that allows you to
use bsh (i.e., actual Java code, although I don't know how much Java 5.0
bsh can do), or at least some source code that allows you to choose from
the available languages.

The brute force algorithm is Patricia's, slightly modified to be usable
in the context of my code (i.e., the nodes is passed in as a List, not
an array). I originally copied some of the code from the Scribble.java
example, but most of that has probably been ripped out over the last few
hours, as I didn't like how it did stuff.

By the way, click the Done button in the second editor frame; do not
close it by clicking the X in the window manager decoration. Another bug
I know of is don't run stuff without any nodes in the display. You'll
get an unrecoverable error somewhere.

And yes, I am having an anonymous inner class fetish today.

 

[Patricia Shanahan]

Sounds ok to me...

I don't mind dis-interest, but it'd kind of be nice if you
demonstrated it more, by posting less, which may sound rude, but it's
about consistency.

What disinterest? A polynomial time algorithm for an NP-complete problem
would be *very* interesting, though statistically unlikely.

I've studied mathematical fallacies since I was a teenager, and ways
software can be wrong for decades, so a not quite correct attempt at an
algorithm could also be somewhat interesting, and much more likely.

Cool. I'll Google you. I'm curious now.

You won't find much, other than my newsgroup postings and a couple of
papers on ubiquitous computing. All my production programming and
computer architecture work has been as an employee of various computer
manufacturers.

You could try the US patent database. I'm the Patricia Shanahan who
lives in California. That does reflect a couple of the computer systems
I helped design, the Celerity C1200 and the Sun Fire 15K.

Patricia

 

[Joshua Cranmer]

Oh, yeah. You're right! I gave the wrong algorithm.

So I decided to try to see how gullible this algorithm was. This is the
JS version, as best as I can tell (copy+paste into editor):
function distance(a, b) {
var dx = a.x - b.x; var dy = a.y - b.y;
return Math.sqrt(dx * dx + dy * dy);
}

var left, leftHist = [], right, rightHist = [];
var nodes = {};
function TSP(args) {
var start = args[0].id;
left = right = args.shift();
for each (var arg in args) {
nodes[arg.id] = arg;
}

num = args.length;
while (num >= 2) {
var bestLeft, bestRight, best = 10000*10000;
for (var leftNext in nodes) {
for (var rightNext in nodes) {
if (leftNext == rightNext) continue;
if (distance(nodes[leftNext], nodes[rightNext]) < best) {
bestLeft = leftNext; bestRight = rightNext;
best = distance(nodes[leftNext], nodes[rightNext]);
}
}
}
leftHist.push(bestLeft); rightHist.push(bestRight);
delete nodes[bestLeft]; delete nodes[bestRight];
num -= 2;
}

var last = false;
for (var arg in nodes) {
last = arg;
}
var output = [start];
for each (var onLeft in leftHist)
output.push(onLeft);
if (last) output.push(last);
rightHist.reverse();
for each (var onRight in rightHist)
output.push(onRight);
return output;
}

I drew a graph that looked roughly like a diamond, with two nearby nodes
at each vertex.

Brute force produced something looking like a diamond, with a length of
666.661.

JSH's current algorithm looks like an hour glass with a length of
1375.509, or roughly twice the best path, which is what I predicted in
an earlier post.

Besides, programming in JS isn't hard, especially when one has all the
features of Java accessible from JS if you work hard enough. Having JS
experience myself, I eschewed the Java features.

 

[JSH]

What disinterest? A polynomial time algorithm for an NP-complete problem
would be *very* interesting, though statistically unlikely.

I've studied mathematical fallacies since I was a teenager, and ways
software can be wrong for decades, so a not quite correct attempt at an
algorithm could also be somewhat interesting, and much more likely.
Oh.




You won't find much, other than my newsgroup postings and a couple of
papers on ubiquitous computing. All my production programming and
computer architecture work has been as an employee of various computer
manufacturers.

Not surprising to me. The modern system buries the individual.

Maybe that's part of why I quit working for others as a programmer.
You can't really brag about your code or really even say a lot about
what you did.

I will say that code I worked on if it's still part of a certain
system is helping to save lives.

You could try the US patent database. I'm the Patricia Shanahan who
lives in California. That does reflect a couple of the computer systems
I helped design, the Celerity C1200 and the Sun Fire 15K.

Patricia

Cool. That you have patents. I already did a search in Google and
Yahoo! and kind of satisfied my curiosity.

I'm fascinated now about how corporations bury the individual, but I
think it's also the world.

One of my ongoing projects is figuring out how popular my open source
project is, and so far I've had very little success, but it would seem
to me there are people out there using it, or Google and Yahoo! just
really like putting my app at #1 for its name just for fun, oh well.
It's a weird world. Takes playing with some things, inventing some
things, to figure out just how weird and how opposite this world is to
what it claims it is, or does.

I'm in no hurry to code this algorithm, and the world has given me no
reason to speed things up.

Unlike you I don't believe in this world's quick acceptance of
innovation, as I know that it works the opposite.

It can take decades for innovations to work their way through, so no
matter what any program I wrote might show, nothing would happen.
Nothing.

Over 6 years ago back when I was naive like you and was still working
at mathematical research I was working on an algorithm to count prime
numbers and after making a change, my screen filled up with primes,
and I got this indescribable thrill.

I was certain it was this huge moment that would end any debate about
my research as that algorithm did then what nothing else does to this
day in its search for primes which it declared in a way by those
primes that filled my screen.

And it didn't matter.

6 years ago. I have 6 years of experience of how the real world
works.

Social forces against innovation are too strong. Only time matters.

There really is no reason for me to code my algorithm because it DOES
I believe work.

And because it is so huge and proves that P=NP it may be decades
before it is accepted, no matter what I or anyone else does because
that is the way it works in the real world.

If you think otherwise it is because you believe in things no true
because you've never had the opportunity to test those beliefs.

I have.


James Harris

 

[Daniele Futtorovic]

Yeah, if I do it half-way, and say, do a proof of concept program to
just tackle Euclidean TSP, but what if I did so, and had code that
showed tremendous promise?

Might I not have a herd of people suddenly interested?

I don't like herds.

I'm interested now in the people who might be interested even though
they think it's all crap, and have no evidence from me but the
algorithm and these discussions.

If none exists and I do it myself then it is mine alone.

I get to be the solo genius and share nothing.

From the herd. I don't care about the herd as I see them as losers.

If no one wants in, fine. Eventually, down the line, I probably will
code my ideas, but if it's going to be me then it is going to be mine,
like my math and all my other research.

Part of what I've been doing is kind of checking as I was so
disappointed with my Class Viewer project which I see now as a
prototype which became a final version because I ended up by myself
for all the coding.

As an experiment I'm seeing if I can recruit with another idea and
mainly be an architect on the project, but if no, then, big deal, you
know?

I CAN do it all myself so what do I lose now by floating out the idea
in this way?

Nothing.

I get to discuss. Hang out. Have fun, and lose nothing.

I still wonder why you continue to discuss when our positions are
clear and your stated position is one of dis-interest in what you see
as something that must be flawed.

I, on the other hand, am perfectly consistent.

The solitary and angry maybe "mad" genius who stands against the world
and does things my way, and no other.

It is all my way.

James Harris

@¬OP: I would like to seize this opportunity to recommend a wonderful book:
"A confederacy of dunces" by John Kennedy Toole.

PS: this post is on-topic.

 

[willo_thewisp]

Right now, I'm trying to figure out if you believe the algorithm you
most recently posted really solves P=NP, because I quite clearly gave a
counterexample.

The problem with your counterexample is that James is too stupid to
understand it.

 

[Rotwang]

Yeah right. Newton revolutionized science itself. During his time
people at universities had thoughtful discussions but didn't
experiment, trying to figure out the world based on what they just
thought was reasonable.

Where did you learn this crap, the back of a cereal box? This is
nonsense. On my shelf at home, for example, I have a copy of /Priestly
on Electricity/ (4th ed., 1775) in which the author discusses at
length many experiments with electrostatics which were carried out
before the time of Newton.

[...]

You have no concept of how they thought as you have no frame of
reference.

ALL of them envisioned themselves as revolutionizing their fields.

Newton especially was hated as an arrogant puss who had a vindictive
streak, as he got his enemies.

He was not a person to cross.

In his later years he was in charge I think it was the Mint? So he
quite likely had counterfeiters executed, and at that time it would
have been by beheading.

You have no clue about the reality of these people, just some
romanticized notion of who and what they were, and no comprehension of
what it took, how many battles and wars they had to fight, to get
things done.

someone to claim that they are in the process of reinventing something
strikes me as being extremely haughty, narcissist, and an indicator that
the work is more likely to be flawed.

Which would work against every person you've mentioned.

You'd hate all of them in person, even Einstein if you had gotten to
know him closely versus the public persona he learned to create.

Like you did, right?

It takes a certain attitude to make great discoveries and more of it
to get them known.

It's not a job for a nice guy.

Have you ever considered that the time you spent reading about great
discoverers might have been better spent learning about their actual
work, rather than just learning about their personalities so that you
could attempt to imitate their behaviour (except for the bit where
they actually, y'know, *learnt something* about the fields they went
on to revolutionise)?

 

[Lits O'Hate]

Like, why should I? The future is my greater judge. And there my
place in history is already set.

"The war on terror will determine my legacy and how Iraq fits
into that will determine my legacy." -- George W. Bush

 

[JSH]

Where did you learn this crap, the back of a cereal box? This is
nonsense. On my shelf at home, for example, I have a copy of /Priestly
on Electricity/ (4th ed., 1775) in which the author discusses at
length many experiments with electrostatics which were carried out
before the time of Newton.

Guess he published the book much later then...

<quote>
Sir Isaac Newton, FRS (pronounced /ˈnjuËtÉ™n/; 4 January 1643 – 31
March 1727 [OS: 25 December 1642 – 20 March 1726])[1] was an English
physicist, mathematician, astronomer, natural philosopher, alchemist
and theologian. His Philosophiæ Naturalis Principia Mathematica,
published in 1687, is considered to be the most influential book in
the history of science.
</quote>

http://en.wikipedia.org/wiki/Isaac_Newton

So Sir Isaac was already dead before the publication you mention.

Didn't you say you have a degree in physics?

And from WHAT country? Oh yeah, wasn't it some place in Great
Britain? Cambridge was it?

Care to explain yourself Mr. "Rotwang"?

[...]

You have no concept of how they thought as you have no frame of
reference.

ALL of them envisioned themselves as revolutionizing their fields.

Newton especially was hated as an arrogant puss who had a vindictive
streak, as he got his enemies.

He was not a person to cross.

In his later years he was in charge I think it was the Mint?  So he
quite likely had counterfeiters executed, and at that time it would
have been by beheading.

You have no clue about the reality of these people, just some
romanticized notion of who and what they were, and no comprehension of
what it took, how many battles and wars they had to fight, to get
things done.

Which would work against every person you've mentioned.

You'd hate all of them in person, even Einstein if you had gotten to
know him closely versus the public persona he learned to create.

Like you did, right?

It takes a certain attitude to make great discoveries and more of it
to get them known.

It's not a job for a nice guy.

Have you ever considered that the time you spent reading about great
discoverers might have been better spent learning about their actual
work, rather than just learning about their personalities so that you
could attempt to imitate their behaviour (except for the bit where
they actually, y'know, *learnt something* about the fields they went
on to revolutionise)?

I did most of my reading as a child, decades ago.

Seems I retained more than you, however, whenever you learned whatever
it is that you think you know.


James Harris

 

[Joshua Cranmer]

Guess he published the book much later then...

Rotwang never implied that Newton wrote said book. He was pointing out
that science was already in the midst of change well before Newton came
around.