When bored I've been working on the travelling salesman problem. I'll admit that I have not got very far but i didn't expect to solve it in just 3 days (one day). So I figure I'd let some other people join in the fun. Elementary graph theory knowledge necessary.

The traveling salesman problem is; given a graph with weighted arcs, is there a polynomial time algorithm that finds the shortest path, starting and finishing at the same vertex, that visits every vertex at least once.

I want someone to prove or dissprove this theorem.

Jim's Theorem
A weighted graph with weighted arcs , has a optimal solution (path visiting every vertex, starting and finishing at the same vertex), say.

This solution, , is contained in the set of optimal solutions for the graph where the inequalities are not strict.

I lost the formalness towards the end. I cant remember enough latex.

If anyone doesn't undertand the problem reply.

Note: This makes 3 millon dollar prize problems in the first 3 topics of the maths banter area of the forums. A bit much?

This doesn't make sense to me. The weights are assigned to the graph at the beginning and the optimal solution depends on the assigned weights. The inequalities not being strict is a condition on the type of graph but changes nothing for the graph you've set and found a solution for (besides, that graph is trivially of the second type as well).

P.S. A statement that isn't proven or disproven is a conjecture, not a theorem. :p By the way, I don't think solving the travelling salesman is a good way to try to solve since just about everyone expects that and thus that the travelling salesman has no polynomial time solution (since it's complete). Also, your statement of the problem is a bit wrong: it's not the shortest path but the one with the lowest cost (adding the weights of the edges that you go through). I think it's been proven that the problem has the same complexity if you require it to end at the starting vertex or not, so you don't necessarily need to pay attention to that part.

O(1) solution found for Travelling Salesman:

http://xkcd.com/399/

Ok my conjecture is that;

we have any weighted graph s.t. none of the arc weights are equal. We can therefore order them by weight. Label arcs . With <

If we then have a graph with the same ORDERING of arc weights (with different weighted arcs) ...

s.t

and are on the same arc when superimposing the 2 graphs of the same shape (i'm thinking in complete graphs anyway so you can ignore this)

These 2 graphs have the same travelling salesman solution (you can swap the labels on the second graph where equal).

Any closer to understanding the problem?

Also forget P=NP this is the travelling salesman. Let the logicians think about P=NP.

Lowest cost; your right but you knew what I meant.

Just because somthing is as complex as the problem doesn't mean it's the same problem. Or even has a similar solution. Though I'm not exactly sure what the proof said.

It is very easy to prove that, on a given graph, the solution is independant of the starting node.

Also I axed your rickrolling because it did somthing to my "where's the beef?" computer at home. It crashed. Thank you for that.

Have fun.

This formulation makes more a bit more sense (though I still don't see the point of it). The conjecture is false though. Consider two labelings of , one with edges labeled 1,2,3 and 100 and another with edges all labeled 1. Clearly the optimal path for the first (starting at any vertex) is not optimal for the second and the first obeys your first set of inequalities while the second is in accordance with the non-strict ones.

My point about P=NP was that it's very much linked to the travelling salesman since TS is NP-complete. As such, since there's practically no chance of P=NP holding, there's practically no chance that anyone will ever find a polynomial algorithm for TS, which is what you're trying to do (since of course this is equivalent to solving P=NP).

Also, when I said complexity I meant computational complexity of course. As such the problem is provably the same since a polynomial algorithm for "TS not ending at the starting vertex" automatically yields a polynomial algorithm for TS (by that proof).

P.S. You actually deleted one of my posts... This means rickroll war. It also means you're uber lame.

"These 2 graphs have the same travelling salesman solution (you can swap the labels on the second graph where equal)."

I could have thought of that obvious example. It's why i phrased it in the complicated way first. Pay special attention to the second part. The conjecture holds trivially in this case as you can set the solution for the second graph to whatever you want.

With this conjecture it means you can ignore large numbers of graphs, which makes things simpler. Which is always good. I'm not necessarily trying to find a polynomial time algorithm for travelling salesman, I just want to find the fastest. In fact i'm not trying to even do that. I just want to waste some time on some poorly documented graph theory.

PS you broke a small families home computer for half an hour, shame on you.

I agree, that hijack site is lame and you were lame for posting it :P

"These 2 graphs have the same travelling salesman solution (you can swap the labels on the second graph where equal)." I could have thought of that obvious example. It's why i phrased it in the complicated way first. Pay special attention to the second part. The conjecture holds trivially in this case as you can set the solution for the second graph to whatever you want.

No, you said "optimal solution" so you can't set the solution to "whatever you want". Swapping the labels on the second graph does nothing since the labels are all equal. On the first graph though, the optimal solution requires you to go through a certain edge multiple times, which is not the same as when the labels are all changed to 1s.

If you want to be formal about it, pick a vertex on , say , and name the others (clockwise). Go clockwise from it and assign the following weights: . We've got and the optimal solution is with cost 12. Now for the second one assign the following weights , replacing with . Clearly but in this case the optimal solution is a cycle from back to itself, with cost 4. But this same solution is not in the set of optimal solutions for the strict inequalities case since it has cost 106 then. Similarly the solution for the first graph in the second case has cost 6 and is not optimal. I don't see how your conjecture holds.

P.S. Half an hour?? Rebooting only takes about 2 mins max :p. Besides the thing lets you close it when you get to the end of the lyrics. :D

Good point my bad, conjecture disproved. Onto the next one!

PS Yes, half an hour, my computer is very slow nearly dead and 39% virus free since 1989

edit: one more post orry join the 4 club.

Rebooting? 2 minutes max? What kind of crazy robot computer from the future do you have?

I'll time it next time I reboot, I'm sure it takes even less than that. :P

edit: one more post orry join the 4 club.

I had 666 four posts ago but I didn't see it and posted again. Damn. (hmm, I could delete some of my old posts :D)

Edit: I just realised I'm now the member with the most posts on the forum. I officially have no life.

There's nothing too bad about having the most posts on teh website, but realising it IS sad. It means you either checked (uber lame) or you thought about wether you were (also lame). It's not about quantity it's about quality. Which is why im a terrible poster.

New TSM related conjecture coming soon. I'm concentrating on counting things to do with complete graphs right now...

I'm not sure what's worse - having the most posts on the maths forum, caring enough to check (or indeed think of checking), or discussing this fact in later posts trying to weigh up which is the saddest. Maybe we should agree that anyone who posts regularly on this forum has way too much time on their hands.

Well, I never checked, I just noticed my post count when you mentionned the 4 club thing and then saw Steven's on another thread (and I knew he had the most). It was a perfectly unintentional realisation. Plus, I don't care about the post count at all and never try to get it higher on puropose (except once or twice as a joke :p).

I think that trying to find a polynomial-time algorithm for this is going to be tough since we have no reason to believe that this is even an NP problem. For those who know as little as I do, this basicly means that what we ought to find first is an algorithm that, given some route, can efficiently work out whether it is optimal or not. If no such algorithm can be found then there is NO WAY that the best route could be efficiently found.

We'll theoretically that would be really easy, we brute force the answer and see if it's the same as what we've got. Easy algorithm for testing.

Right now when i've got free time i'm trying to build up some theory regarding it. I'm finding n=4 too difficult. Im counting how many distinct graphs there are. It's proving very difficult to even do case analysis.

Cosmin also easily disproved my conjecture to make things really simpler.

Wrong, that is not an "easy" test in terms of running time. My point is that if you take the set of all problems that can be solved with a polynomial-time algorithm, and the set of all problem whose answers can be checked with a polynomial time algorithm, then clearly , but we do not yet know whether . The TSP may not even be in , since you can only check a solution by brute-forcing it.

To give an example of an problem that may or may not be in , take an arbitrary finite subset S of the integers, and work out if there exists a subset such that . If someone gives you a subset and claims that it does the job, it is easy to check. However, to the best of my knowledge, no polynomial-time algorithm has been found that will actually FIND the subset .

My goal isn't actually to find a polynomial time algorithm, or anything to do with P=NP. I want to find a faster algorithm than the fastest one now. Not much. In a long time of course. Anyone know any TSM related theorems? (not to do with P=NP or a different problem?

Constructing my test is very easy, just the algorithm itself is not very fast or efficient.

I'm pretty sure there's better than brute force for checking a solution though. Also, TS is NP-Hard (this is what I meant to say when I said NP-complete above, sorry about that), which means that there's at least an NP-complete problem which is reducible to TS in polynomial time.

Travelling Salesperson is in NP isn't it? Or at least (since NP is a class of decision problems) the corresponding decision problem (does there exist a path with weight less than W) is certainly NP since checking the length of a path is addition which can be done in quadratic time.

The decision problem is, yes, but TS itself is not known to be in NP. It's still NP-hard though, so a polynomial solution to it solves P=NP.

You know what else is NP-hard? points to crotch

Computability-five!

Only 5?

**** im spamming my own thread