11 Replies  2721 Views  Last Post: 19 December 2013  12:12 PM
#1
Truly polynomial algorithm for solving symmetric TSP accurately
Posted 17 December 2013  01:27 AM
I,m 32. Found this forum via google, and would like to ask a probably stupid question to a nonstupid idea. I am a computer freak (grew up with computers since i was 7) , but not a certified computer scientist. That is just for information about me. I am not in the computer/hacker sceene, nor member of any club. I am a loner, in reality and virtuality, to put it simple.
I am working on a a proof of one of the major conjectures in computer science, mathemathics), and I think that I have made a breakthrough last night. I know the probability is very low, that the proof is really correct, but it is of major importance, at least it could go from conjecture to hypothesis, with wich I could live or die happyliy. What I can say is that: If my proof is only true for some (not all) decision problems then it would probably prove that there are no polynomial solutions to (some or maybe even all) nonpolynomial problems. And if my proof is entirely true it would probably either prove that there are solutions to some, NPHARD PROBLEMS!!!!, which can be reduced to geometric problems that are exactly of the form of 2D, (two dimensional, and not less, they cannot be vertices on a straight line). Or it (my attempt) would imply that no (none of all) nonpolynomial problems can be solved in polynomial time. It is hard to explain in sentences, but my hypothesis has similar characteristics to the continuum hypothesis. And yes I am aware of goedels incompletness theorem and the existence of tautologies....but...sorry I am going of topic.
Basicly what I say is that the idea that if any, NPcomplete problem can be solved, that all of them can be solved IS FALSE! That is if my proof is only applicable to the TSP and other 2D problems. But if it is true for all descision problems that can be reduced to exactly 2D geometric problems, it would prove that some (some , not all) NPhard problems can be solved in polynomial time, which would lead to the same conclusion. Namely that complexity theory needs to be reworked.
Fact: is that I can solve symmetric TSP (travelling salesman problem) on my computer for 10'000 (ten thousand) vertices within 24 hours, for nonspecific inputs (many times), inputs generated via a pseudo random number generator and translated into a 2D (S)TSP. I verified the results for small random vertices via brute force, and they were all 100% accurate. I am not sure if my results for 10'000 (tenthousand) vertices are 100% accurate (100% optimal), but I assume they are, looking at the code which is very long and complicated and not beautiful, and reliing on my results from small inputs. Maybe someone can make a nonprobabalistic program that tests my algorithm for deterministicness. :) Hmm...Halting problem...sorry off topic again, my head is spinning, sorry, sleep deprivation.
I do not use random bits for solving the TSP. I know that my solution runs much much faster than concorde TSP solver and I know that Lin–Kernighan and derivates are less accurate than my solution (for small and moderate inputs). I would need google servers to veryfy my results for large and huge inputs, but that will not happen in the near future. Also I do not want to reveal to much information about my algorithm for obvious reasons. I dont want anyone to use it for bad things, and I don't want anyone to steal my idea.
You probably do not beleive me, but assuming you do, here is my real question, and the reason why I have registered on this foruum:
I do not know about publishing proofs, and about how the format has to be. I am a language teacher, not a computer scientist. All I know is that my algorithm works, and it works better and faster than anything I know of, allthough it is quite long. I am afraid of the consequences, if I decide to publish. I need someone to read my code, someone I can trust, and someone who can put himself into my mind, and understand the thought process. The idea is actually quite simple, but the algorithm is long and ugly. I am sure it can be improved. But I just do not know who to talk to. Also I live in an isolated place in the world that barely has internet. What would you do in my position, who would you contact? I really need some help to those trivial questions as I am unable to answer them by myself. I know that some people do not want fast solutions to integer factorisation, for obvious reasons, but I do not think that my idea is applicable to integer factorisation, which is beleived to be easier than TSP. All I have is an algorithem that can solve 2D symmetric TSP faster than anything I know and heard of. I think that my idea could improve some aspects of the world we live in (like pollution and maybe weather prediction). Also I think that encryption does not rely on integer factorisation and similar problems. My idea has nothing to do with that. And as I said in the beginning, I do not beleive that if one/any NP problem can be solved that all of them can be. I would not know how to apply my idea to integer factorisation or even to 3Sat. Anyhow, public key encryption can be based on other stuff, which I will not go into at this moment. All I have is what I have discovered, and I know that it works much much better than anything I know of. All I don't know is what to do with it now.
regards and thank you
Replies To: Truly polynomial algorithm for solving symmetric TSP accurately
#2
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 17 December 2013  06:23 PM
Quote
This is a false conjecture. An NP Complete language is defined that all languages in the class NP can be reduced to an NP Complete language in polynomial time. Thus, NP Complete languages can be reduced to each other. This is the definition (ie., your starting point), not a result.
Quote
You want to look at the complexity of the algorithm; and for this, you want proof of such complexity. Even if your program scales well for relatively small cases, how will it scale for larger cases? I think judging by your questions, you are not ready to submit your findings, nor do I think your findings are interesting/worthwhile. I don't mean to be rude by saying that, but example is not proof (which cases up to 10k vertices are just examples).
Quote
I am not sure about publishing proofs either. Hopefully you at least know how to write proofs. Is there a community college or some sort of university within reasonable distance of your location? If so, I would talk with a professor that does research in the area of combinatorics and graph theory, or theoretical computer science. I think if you are serious about pursuing research, you need mentorship. I take the same rule for findings as the security community does for cryptography. If your findings don't stand up to peer review, they're not worth anything.
You may also consider copyrighting your findings and submitting them to the AMS.
#3
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 17 December 2013  07:32 PM
You may be very good with computers, but this is a question about math. It sounds to me like you need to do a bit of work on the math part of this, to understand just what "P" and "NP" mean. I would suggest that you might get something useful from Jeff Ullman's course on Automata, which will take you right up to the formal definitions you need to talk about these things. The most recent run of the course has just finished up on Coursera, but you can watch the lectures and get the material any time.
I suggest this because most programmers don't actually know what NP is. There's nothing wrong with being one of them, except it means that you're not going to make good arguments about P and NP. If you want to be able to do that, you need the formal definition, and Ullman's course is a good way to get really familiar with that material.
#4
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 18 December 2013  04:34 AM
I know, I still got a ton of work to do. Thanks for the AMS link.
About P and NP etc., hmm... After rereading my post I can see that I have expressed myself vaguely because I mixed TSPDECIDE and TSPOPTIMIZE in the same paragraph. Sorry for that, I was very tired and exhausted.
To me the definition of NP is something like this:
Decision problems, that can be checked/verified in polynomial time.
Now for symmetric TSPDECIDE, we know that it is NPComplete, but for symmetric TSPOPTIMIZE we just know that it is NPHard. Since it is not a decision problem it can't be in NP anyways. TSPOPTIMIZE seems to be harder than TSPDECIDE, right? In order to veryfy a proposed optimal route/result we still need to brute force it right? Now what if my algorithm (STSPOPTIMIZE solver) works for any "n" vertices 100% optimal in polynomial time, which is very unlikely, and even if it were, there would be no way of proving it, because the brute force verification of the result runs in factorial time.
We could run my algorithm against other algorithms and see which one runs faster and/or more accurate. Would we then have a contradiction inside of complexity theory or not, if we see that for every n vertices my algorithm is superior to other algorithm(s). Would we then have to assume that my algorithm is allways 100% accurate if it beats all other algorithms for huge n's? Or would we have to say it is simply undecidable if my algorithm is allways 100% accurate/optimal for any "n". Since my observations show that it is 100% accurate for small n's, must I not then assume that it stays accurate for large n's?
Now, since TSPoptimize is a NPHard problem of which we know that it is not in NP, because it is not a decision problem can we say it is theoretically possible that it runs 100% accurate in polynomial time? And what would the consequences be? Since it is not NPcomplete it can be theoretically solved in polynomial time, right?
Just to explain a bit about the algotithm without giving out to much information:
I basically convert STSPOPTIMIZE into a "mechanical problem", then I run my engine which basically just emulates the laws of nature (laws of physics) to solve the problem. BUT, It does NOT work like ACO or similar stuff. Now it is known that nature somehow, mysteriously is able to solve really hard problems like protein folding in polynomial time. Now sure, it could be that the inputs are special, but since I use a pseudo random generator to create the inputs, this seems highly unlikely.
Is there any flaw in my thought process?
regards
#5
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 18 December 2013  09:29 AM
InputSize n*lg(n) n^2 10 30 100 100 700 10000 1000 10000 1000000 10000 130000 100000000
It is really hard to see the slower times when using random input because these times are usually achieved when the input is already sorted. However, since the case does exist, the slower runtime determines the complexity. For your program, you need to determine the function that represents the slowest your program will run for an input of size n. This is done by analyzing the code, not running the algorithm against test cases. If you can show that your program
1) Always produces the correct result
2) Always runs in polynomial time
Then it is in P. Otherwise, it is an approximator or NPHARD.
#6
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 18 December 2013  04:11 PM
Quote
Decision problems, that can be checked/verified in polynomial time.
That's half the definition. The part you're missing, which is very important, is that if given a language L in NP and some string, if the string is not in the language, the Turing Machine that accepts L may not halt. If it does halt, it may not do so in polynomial time.
I agree with mojo666 you need to focus on proving correctness, halting, and O(p(n)), where p(n) is a polynomial with respect to n. Remember that example is not proof.
#7
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 19 December 2013  08:46 AM
I can see that this is going somewhere. Thanks again for all the replies and criticism, actually I need even more criticism.
Ok, but please don't throw big O notations at me, as if I don't know what I am talking about, but don't get me wrong , thanks for any input really. Especially mojo's reply has been really helpful.
Look guys, I am not a computer scientist, nor a mathematician, and that is exactly the reason why I need your feedback.
I studied philosophy and physics, thus I assume that I know what logic is. I am just trying to think outside of the box here, and that was essentially what led me to creating my program. Yes and I do not just accept stuff, I want to understand it and therefore I question everything. Btw...I do that just for or against my self, not for anyone else.
Call me the devils advocate for my own statements if you want. This is what science is all about.
enough of that anyways...
Ok, so my results just reflect the average case and best case, but how could it possibly reflect the worst case for TSPOPTIMIZE? I mean... hmm how shall i put it..assumingly there is only 1 worst case, and if there is not, they are equivalent.
There is no worst case for TSPOptimize, how could there be? If you disagree with me then post an image of the worst case STSPOPTIMIZE PROBLEM right here, for let's say 510 vertices, or any "n" vertices. Sure there is an upper bound, but how does it look like. Post an image of lets say 510 vertices arranged the worst possible way, and prove that it is the worst case. This fricking problem is not a descision problem, so how can there be a worst case?!?
I am talking about a NPHARD problem that is assumed not to be in NP.
Now for problems in NP, sure you can name worst and best case scenarios. EXAMPLE: Just to be silly I will pick a NP problem, of which it is NOT known if it is NPcomplete or not. We know, it is in NP ( and we think it is NPIntermediate), because we do beleive it is neither NPComplete nor NPEasy. It might be NPEasy though....:)
Integer factorisation!!!! Or to be more accurate:
!!!Decide if a natural number is prime or not (PRIMENUMBERDECIDE)
Worst case is: A natural number, that consists of exactly 2 prime factors! (semiprimenumber, 2almost prime) Example: the number: 121103=347*349 ) This takes the longest time to factorize. On the other hand an even number is the best case, because it is devisible by 2, just by looking at the last digit, one can determine that.
But the best algorithms known for PRIMENUMBERDECIDE work much faster if the two primefactors are close to eachother (like the twin primes in my example). So, for encrypting data, you do NOT want to use twin primes to create a semiprime, which we said is the worst case (best for encryption). So looking at the algorithms that are known to mankind, which would be truly the strongest way to create a semiprime, which way should we chose our primes to create the hardest posssible semiprime to factorize?
It is also undecidable. Or yes, it might be decidable, but not in polynomial time, or not on a deterministic turing machine. I mean tell me the best way of creating a semiprime, in order that it is the hardest to factorize. It is just not possible, to do that.
fricking halting problem, messes it all up......
....and thats the same for TSPOPTIMIZE...
....and is it even important to define complexity by the worst case, if the worst or best case never happens within the universe we live in? Well it can theoretically happen, but it does not in practice.
And I know the theory, I am just asking you tou consider forgeting what you have learned, for soem cases. In some cases, there just does not exist a best or worst case, or to put it in other words: It is undecidable wether there exists a worst case or a best case for some really hard problems, all we know is that there exist best and worst cases for some problems.
#8
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 19 December 2013  10:00 AM
unobtainable, on 19 December 2013  10:46 AM, said:
I imagine you'll have it.
Quote
Don't worry about finding an instance of the worst case. Solving the worst case is just solving one more instance, and solving instances is not solving the problem. In any case you don't have to produce a concrete "worst case" to talk about the worstcase analysis. The "worst case" is simply "how bad can it get?" and for interesting problems, the description of "how bad it can get" is usually independent of the problem of producing an actual worstcase instance  and much easier, and much more interesting.
Quote
!!!Decide if a natural number is prime or not (PRIMENUMBERDECIDE)
Worst case is: A natural number, that consists of exactly 2 prime factors! (semiprimenumber, 2almost prime) Example: the number: 121103=347*349 ) This takes the longest time to factorize. On the other hand an even number is the best case, because it is devisible by 2, just by looking at the last digit, one can determine that.
This is a very good example of why instances of the worst case are completely uninteresting except as illustrations of the problem at hand and how they are worked by a particular algorithm for that problem.
So "exactly two prime factors" is not going to produce a worst case on its own. There is an infinite list of such numbers which the most naive approach factors immediately: the numbers described by 2*p_{i} where p is the list of all prime numbers.
The worst case for any particular algorithm will be "the product of the last two primes we look at". So what is the worstcase for factorizing integers? Depends on the algorithm. And for any algorithm A that you produce, I can take your worstcase number and produce A', where A's worstcase is A's bestcase. (simply by checking that one first)
Quote
There's no point forgetting what you've learned. You might replace it with something better, but that something must first be shown to be better. You haven't provided that yet.
Quote
Again: don't get hung up on actual best and worst cases. These are facts about algorithms, not about problems. That is, they're interesting when you're implementing an algorithm, not when you're determining whether a particular problem is solvable.
This post has been edited by jon.kiparsky: 19 December 2013  10:00 AM
#9
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 19 December 2013  11:16 AM
It seems to me that I am talking about NPHard Problems that are not in NP, and you are talking about NP (and or NPComplete problems).
Quote by jon.kiparsky
Quote
Sure you know, that:
The sum of solving all instances is equal to solving the problem itself. And of course you have to produce the worst case in order to truly define the time it takes to solve the worst case for any given algorithm. Sure you can average it but...sorry seriously...are you kidding me? Yes you can program a bogo algorithm for anything, but...... I dont get the point of your last post, maybe I have to sleep over it.
I fail to se the logic in this:
I paraphrase:
You (not you explicitly, but math itself) are somehow contradicting yourself/itself by saying that the worst case is unlistable, but allthough it is unlistable, it is still important.....makes no sense. Further you say that the worst case is just one more instance of the problem, and I agree, who would not agree with that.
Well how bad can it get? Yust as bad as the worst case! And you do not know the worst case until you have listed it in relation to the algorithm. Of course you can do a bogosort algorithm, and just say it is the worst sort possible, without telling anyone the last item in your set, but then I can say: Well even if I do a bogobogo sort, and your last item is identical my superior bogo sort, my bogobogosort takes longer. And then you can do a quantumbogobogo sort and colapse our universe.... that just does not lead anywhere.
By the way: Bogosort on a nondeterministic turing machine is faster than quick sort on a deterministic turing machine.
[...but back to reality...]
So let's take a 3vertex euclidean STSP. Due to the triangle inequality, the best, or if multiplied by 1, worst case approaches a limit of infinity or infinitessimal respectively, you can't list or paint it, like you said, but this is totally irrelevant for real life applications. Infinity does not exist within our universe. It is just an abstract idea. In order to clarify that from the very beginning, I defined my idea, in my opening post. I said that it does not work for vertices on a straight line. It has to be with in a plain (2Dimensional Space).
But I need to sleep and reflect over your suggestions. Also this last post of mine was written to induce some kind of entertaining.
So let me dream in code for another night, and then we can continue this truly creative dispute. Allthough we might have gone a bit offtopic. But its ok, because I am a lunatic by indirectly implying that P could possibly equal NP.
Yost trying to create some nondeterministic fun reading in this post of mine. Lets continue tomorrow.
Cheers
#10
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 19 December 2013  11:35 AM
Quote
I am talking about a NPHARD problem that is assumed not to be in NP.
The worst case you are looking for is going to depend on the algorithm. Since you were using random inputs, the 100 or so vertices were probably pretty uniformly spaced, so your algorithm is probably pretty good at solving such cases. Is it still good if the result is more "splotchy" and the vertices seem to form groups? What if the vertices form a circle? The general way to go about finding this worst case is to manually work through the algorithm identify features that make the algorithm efficient and chose inputs that try to make such features irrelevant or incorrect. For something like quicksort this is pretty straight forward. The efficiency comes from splitting the set into two groups, so the elements in each group never have to interact with each other. However, how it is separated into the groups depends on the pivot that is selected. I simply construct an input such that the pivot chosen is the smallest element of the group. This way the group cannot be split up so all elements still have to interact with each other and quicksort loses the feature that made it efficient. Even if the algorithm chooses the pivot randomly, as the "oppose" I can just say "I randomly choose the smallest available element for the pivot".
//ideal run quicksort {253140} step 1: choose pivot=3 {210}{3}{54} pivot compared to 5 elements step 2: choose pivot=1 {0}{1}{2}{3}{54} pivot compared to 2 elements step 3: choose pivot=5 {0}{1}{2}{3}{4}{5} pivot compared to 1 element Total compares: 8 //Opposing run quicksort {253140} step 1: choose pivot=0 {0}{25314} pivot compared to 5 elements step 2: choose pivot=1 {0}{1}{2534} pivot compared to 4 elements step 3: choose pivot=2 {0}{1}{2}{534} pivot compared to 3 elements step 4: choose pivot=3 {0}{1}{2}{3}{54} pivot compared to 2 elements step 5: choose pivot=4 {0}{1}{2}{3}{4}{5} pivot compared to 1 elements Total compares: 15
Again, such methods are more straight forward with simpler algorithms. I imagine it is a lot harder to do for your TSP solver. Not only is it work intensive, but it is also easier to make a mistake in your analysis and fail to identify the worst case scenario. I would start researching algorithm analysis techniques, as the opposer method isn't the only way to analyze an algorithm. I don't know anything about publishing, but ultimately you will need someone to check your algorithm. Once you have done the work and are still satisfied with your algorithm, I would recommend reaching out to an academic institution for advice. They can better inform you than we can.
This post has been edited by mojo666: 19 December 2013  01:15 PM
#11
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 19 December 2013  11:39 AM
Quote
This doesn't make sense. There are an infinite number of lists that you could sort, so this implies that the solution to sorting a list is infinite (the sum of solving all instances). This is clearly not the case.
Quote
Of course you do not have to produce any case at all. Consider the standard recursive addition algorithm
+(x,y) => (x==0) ? y : +(x, ++y)
Do you need a "worst case of addition" to prove that this requires x recursive calls? No, you simply do the induction on x.
Quote
But you don't care about the particular case that you designate as "worst". That's the point. The point of math is to abstract away from particular cases to get general solutions.
Quote
Not at all, that is an open question. Nobody has yet proved that P!=NP. And in fact, the practical work that is being done is bringing the two classes closer together, so it may well end up that P~=NP very soon.
(remember, NP just means we need exponential time, it says nothing about the value of the exponent. Suppose the value of the exponent is 1.0000000000[...]1  what then does it mean that the problem is exponential?)
#12
Re: Truly polynomial algorithm for solving symmetric TSP accurately
Posted 19 December 2013  12:12 PM
quote by mojo666
Quote
Thanks guys. Just one thing for mojo, if the vertices form a circle, then it would be solved anyways. There is no more optimal route than a circle within a hamiltonian circuit. If all cities/vertices/nodes on a map form a perfect circle, then the optimum is reached, and that is basically how my program works. It makes a perfect circle out of all vertices but I can not (yet) tell you how I convert random nodes into a average circle of their own values within a 2Dimensional coordinate system and then revert them into the original problem.
Put in another way: My breakthrough mentioned in my first post, was just, that it seems that I somehow can calculate the optimal distance (shortest route), but I dont know how to traverse through the nodes/vertices.
Or put in yet another way: I think I can tell you the shortest route through a hamiltonian cycle, but I do NOT know in which order to traverse the vertices. I am very sure that I have created a verifyer in polynomial time for a NPHARD optimization problem (STSPOPTIMIZE). But my algorithm can NOT print the graph. It can just tell the shortest distance. And this would mean, that I have created a verifyer, that runs in polynomial time for a NPHARD problem, which would somehow,strangely mean that I can veryfy if a route is the shortest without knowing how to traverse the vertices.
regards
