Reputation: 0 Apprentice
- New Members
- Active Posts:
- 5 (0.02 per day)
- 16-December 13
- Profile Views:
- Last Active:
- Dec 24 2013 02:56 AM
- Dream Kudos:
Posts I've Made
Posted 19 Dec 2013Ok thanks again mojo for your advice. And also thanks to jon.kiparsky for even reading my insane ideas. There is just so much more work to do. And my findings seem crazy to me. That's why I doubt them myself. It is good to discuss such crazy stuff with some people who even care to reply to my ideas. I will continue to try to find the flaws in my program, which I still do not beleive to be 100% accurate, but it still is surprising to me that it seems to be better than all I know.
quote by mojo666
QuoteWhat if the vertices form a circle?
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 2-Dimensional 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 NP-HARD optimization problem (STSP-OPTIMIZE). 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 NP-HARD problem, which would somehow,strangely mean that I can veryfy if a route is the shortest without knowing how to traverse the vertices.
Posted 19 Dec 2013Ok,...jon was right... :-)
It seems to me that I am talking about NP-Hard Problems that are not in NP, and you are talking about NP (and or NP-Complete problems).
Quote by jon.kiparsky
QuoteDon'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 worst-case 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 worst-case instance - and much easier, and much more interesting.
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:
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 bogo-bogo sort, and your last item is identical my superior bogo sort, my bogo-bogosort takes longer. And then you can do a quantum-bogo-bogo sort and colapse our universe.... that just does not lead anywhere.
By the way: Bogosort on a non-deterministic turing machine is faster than quick sort on a deterministic turing machine.
[...but back to reality...]
So let's take a 3-vertex 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 (2-Dimensional 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 off-topic. But its ok, because I am a lunatic by indirectly implying that P could possibly equal NP.
Yost trying to create some non-deterministic fun reading in this post of mine. Lets continue tomorrow.
Posted 19 Dec 2013Ok, great
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 TSP-OPTIMIZE? 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 TSP-Optimize, how could there be? If you disagree with me then post an image of the worst case STSP-OPTIMIZE PROBLEM right here, for let's say 5-10 vertices, or any "n" vertices. Sure there is an upper bound, but how does it look like. Post an image of lets say 5-10 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 NP-HARD 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 NP-complete or not. We know, it is in NP ( and we think it is NP-Intermediate), because we do beleive it is neither NP-Complete nor NP-Easy. It might be NP-Easy though....:-)
Integer factorisation!!!! Or to be more accurate:
!!!Decide if a natural number is prime or not (PRIMENUMBER-DECIDE)
Worst case is: A natural number, that consists of exactly 2 prime factors! (semiprime-number, 2-almost 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 PRIMENUMBER-DECIDE 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 TSP-OPTIMIZE...
....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.
Posted 18 Dec 2013Thanks for your replies,
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 TSP-DECIDE and TSP-OPTIMIZE 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 TSP-DECIDE, we know that it is NP-Complete, but for symmetric TSP-OPTIMIZE we just know that it is NP-Hard. Since it is not a decision problem it can't be in NP anyways. TSP-OPTIMIZE seems to be harder than TSP-DECIDE, right? In order to veryfy a proposed optimal route/result we still need to brute force it right? Now what if my algorithm (STSP-OPTIMIZE 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 TSP-optimize is a NP-Hard 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 NP-complete 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 STSP-OPTIMIZE 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?
- Member Title:
- New D.I.C Head
- Age Unknown
- Birthday Unknown
unobtainable hasn't added any friends yet.