P-NP problem, TSP
category: offtopic [glöplog]
Since I believe that such big open problems are primarily open because people who would be capable of solving them believe they aren't capable, I have tried to give it a go.
P = NP could be proven by finding an algorithm for an NP-complete problem that has polynomial runtime. Although I don't believe I'll have success with the following approach, since I guess many people have already investigated this problem instance, I'll try to find a polynomial runtime algorithm for the traveling salesperson problem (TSP).
1. First idea: At the beginning I select one edge per node, preferably the shortest one. Then I count the number of edges incident with each node. If this number is 2 for each node, we're done - in this case the algorithm only needed polynomial time indeed. But probably the initial construction heuristic will yield to nodes incident with 3 or more edges. I must correct each of these nodes. I do this by removing the longest edge and adding the shortest possible edge to the neighbouring node which was connected by the edge I removed. If a new node with 3 or more edges is created this way, I repeat the procedure (but I won't remove the edge I just inserted). The algorithm probably works. The open question is: How many iterations per node do I need in the worst case?
2. Second idea: I have no idea if just general TSP is NP-complete, or whether the special variant of TSP in which there is an edge between any two nodes u and v and the edge lengths correspond to Euclidean distances is NP-complete as well. If it is, then we could investigate this particular problem instead of the general TSP. It is interesting because we could compute the convex hull to obtain a part of the solution, which is possible in polynomial time. If three nodes A, B, C appear in the convex hull in this exact order, then they will appear in this order in the solution as well. The open question is how to determine the order of the remaining nodes, and whether this is possible in polynomial time.
P = NP could be proven by finding an algorithm for an NP-complete problem that has polynomial runtime. Although I don't believe I'll have success with the following approach, since I guess many people have already investigated this problem instance, I'll try to find a polynomial runtime algorithm for the traveling salesperson problem (TSP).
1. First idea: At the beginning I select one edge per node, preferably the shortest one. Then I count the number of edges incident with each node. If this number is 2 for each node, we're done - in this case the algorithm only needed polynomial time indeed. But probably the initial construction heuristic will yield to nodes incident with 3 or more edges. I must correct each of these nodes. I do this by removing the longest edge and adding the shortest possible edge to the neighbouring node which was connected by the edge I removed. If a new node with 3 or more edges is created this way, I repeat the procedure (but I won't remove the edge I just inserted). The algorithm probably works. The open question is: How many iterations per node do I need in the worst case?
2. Second idea: I have no idea if just general TSP is NP-complete, or whether the special variant of TSP in which there is an edge between any two nodes u and v and the edge lengths correspond to Euclidean distances is NP-complete as well. If it is, then we could investigate this particular problem instead of the general TSP. It is interesting because we could compute the convex hull to obtain a part of the solution, which is possible in polynomial time. If three nodes A, B, C appear in the convex hull in this exact order, then they will appear in this order in the solution as well. The open question is how to determine the order of the remaining nodes, and whether this is possible in polynomial time.
Interesting. You're smart.
The general TSP is NP-hard, the cost-based decision version is NP-complete.
...
NP-complete/NP-hard problems are that because you can embed "the" NP-complete problem in them, namely, the boolean satisfiability problem (ie. whether you can make a boolean expression involving a number of variables return true by assigning values to them). So I suggest solving that instead. It probably saves quite a few steps from you.
NP-complete/NP-hard problems are that because you can embed "the" NP-complete problem in them, namely, the boolean satisfiability problem (ie. whether you can make a boolean expression involving a number of variables return true by assigning values to them). So I suggest solving that instead. It probably saves quite a few steps from you.
*ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ*
Maali is apparently not smart.
We should make two separate communities. One for smart people, the other for the Maalis of this world.
We should make two separate communities. One for smart people, the other for the Maalis of this world.
Last time I gave a sarcastic reply the guy left pouet so I figured this time I'd try to be helpful:(
My approach to SAT, assuming only the operators - (not), & (and) and + (or) appear in the formula:
The formula I have to check may be simple or complex to a certain degree. A simple formula A can be one of the following:
*) a: The atomic formula. It is always satisfiable.
*) -a: Negation of an atomic formula. It is always satisfiable, as well.
*) a + b: Disjunction of two atomic formulae. This is always satisfiable! The same goes for -a + b, a + -b and -a + -b.
*) a & b: Conjunction of two atomic formulae. Conjunction is satisfiable most of the time. The only exception is a & -a, which is not satisfiable.
So far, so easy. A first-degree complex formula A' is a combination of two simple formulae. There are two possibilities for complex formulae:
*) A + B: This is satisfiable if at least one of the two, A or B, is satisfiable.
*) A & B: This case is more complicated. We should make use of the commutative law, i.e. A & B = B & A, if B is a conjunction because it is necessary to evaluate conjunctions first. If both A and B are disjunctions, we just have to check if both of them are satisfiable; if so, A' is satisfiable as well. But if one of them is a conjunction, we have to check and store what values the variables have to take (e.g. if A = a & b, then a = 1, b = 1, or if A = -a & b, then a = 0, b = 1, etc.). When we evaluate the other subformula then, we have to check whether it is satisfiable given these preset values. If that subformula is a conjunction, then all of the variables must match the preset values. If it is a disjunction, it is enough if one variable matches its preset value.
A second-degree complex formula A'' is an analog combination of two first-degree complex formulae, and so on.
This algorithm works. What is its run-time complexity?
The complexity is measured by n being the number of variables. As one can read on Wikipedia it is possible to solve SAT by simply trying all possible combinations of 0's and 1's for all variables, which works in run-time 2^n (exponential). My algorithm checks any occurrence of a variable only once. Of course a variable may appear two or more times, but still, the complexity is polynomial in terms of the number of variables.
I wonder what I have done wrong? It can't be that easy after all!
The formula I have to check may be simple or complex to a certain degree. A simple formula A can be one of the following:
*) a: The atomic formula. It is always satisfiable.
*) -a: Negation of an atomic formula. It is always satisfiable, as well.
*) a + b: Disjunction of two atomic formulae. This is always satisfiable! The same goes for -a + b, a + -b and -a + -b.
*) a & b: Conjunction of two atomic formulae. Conjunction is satisfiable most of the time. The only exception is a & -a, which is not satisfiable.
So far, so easy. A first-degree complex formula A' is a combination of two simple formulae. There are two possibilities for complex formulae:
*) A + B: This is satisfiable if at least one of the two, A or B, is satisfiable.
*) A & B: This case is more complicated. We should make use of the commutative law, i.e. A & B = B & A, if B is a conjunction because it is necessary to evaluate conjunctions first. If both A and B are disjunctions, we just have to check if both of them are satisfiable; if so, A' is satisfiable as well. But if one of them is a conjunction, we have to check and store what values the variables have to take (e.g. if A = a & b, then a = 1, b = 1, or if A = -a & b, then a = 0, b = 1, etc.). When we evaluate the other subformula then, we have to check whether it is satisfiable given these preset values. If that subformula is a conjunction, then all of the variables must match the preset values. If it is a disjunction, it is enough if one variable matches its preset value.
A second-degree complex formula A'' is an analog combination of two first-degree complex formulae, and so on.
This algorithm works. What is its run-time complexity?
The complexity is measured by n being the number of variables. As one can read on Wikipedia it is possible to solve SAT by simply trying all possible combinations of 0's and 1's for all variables, which works in run-time 2^n (exponential). My algorithm checks any occurrence of a variable only once. Of course a variable may appear two or more times, but still, the complexity is polynomial in terms of the number of variables.
I wonder what I have done wrong? It can't be that easy after all!
Quote:
See? It's tricky, isn't it?The open question is: [...]
Adok: Your algorithm has to go though the whole expression. It's easy to generate an expression in conjunctive normal form that has an exponential variable->clause ratio (see the example below "Conversion into CNF" at http://en.wikipedia.org/wiki/Conjunctive_normal_form) - the algo you did wouldn't even be able to _verify_ that in polynomial time, let alone solve.
Evidently each and every academic person who's done some research in theoretic computer science, specifically algorithm complexity, is an idiot. But wait, now Adok comes and shows the world how it's done properly.
Quote:
At the beginning I select one edge per node, preferably the shortest one. Then I count the number of edges incident with each node. If this number is 2 for each node, we're done
That's not necessarily true. You could have found two or more disjunct cycles, in which case you would not have solved the TSP at all.
Adok is a very talented troll. :]
come back when you proved P=NP and enlighten us then please.
lemme rephrase
*ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ*
*ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ*
Pffft, everybody knows that N=NP because of soap
http://www.tjhsst.edu/~rlatimer/techlab06/Students/OuyangPaper06F.pdf
http://www.tjhsst.edu/~rlatimer/techlab06/Students/OuyangPaper06F.pdf
http://www.youtube.com/watch?v=GSIodz9GWxc
P = NP xD
I don't think I'll ever learn german just so I can keep watching Hitler and his first world problems.
@adok @2:
even if the edge lengths correspond to euclidean distances, it is unclear how to obtain a realization of the graph in the plane, i.e. how to obtain coordinates (xv, yv) for each vertex v such that length(v,w) = euclideandistance((xv,yv), (xw,yw)) for each pair of nodes (v,w). even if it was possible to find such a realization within a polynomial runtime bound, in don't understand in what sense the convex hull of the vertices (where I suppose you mean the convex hull polygon instead of the convex hull itself) is part of the solution.
even if the edge lengths correspond to euclidean distances, it is unclear how to obtain a realization of the graph in the plane, i.e. how to obtain coordinates (xv, yv) for each vertex v such that length(v,w) = euclideandistance((xv,yv), (xw,yw)) for each pair of nodes (v,w). even if it was possible to find such a realization within a polynomial runtime bound, in don't understand in what sense the convex hull of the vertices (where I suppose you mean the convex hull polygon instead of the convex hull itself) is part of the solution.
rac: It seems straightforward enough to me: take any three nodes* from the set, place them in a triangle oriented any way you like (all rotations/reflections are valid solutions), then add all remaining nodes one by one, by referring to the distances to the three original points. (Given a distance from two other points, there are two possible candidates; the third distance makes the solution unique.)
But yes, I don't see how the convex hull helps. As a counter-example, consider a "string of pearls" shaped graph, laid out in some convoluted curve; there's one very obvious path through them, and it has very little in common with the convex hull.
* there are probably some edge cases to be specified there, like "non-zero distance apart", but those are left as an exercise to the reader :-)
But yes, I don't see how the convex hull helps. As a counter-example, consider a "string of pearls" shaped graph, laid out in some convoluted curve; there's one very obvious path through them, and it has very little in common with the convex hull.
* there are probably some edge cases to be specified there, like "non-zero distance apart", but those are left as an exercise to the reader :-)
ham is right.
for the record, someone already made a movie about it: http://www.youtube.com/watch?v=6ybd5rbQ5rU
what?
