0
$\begingroup$

I am going to show you a proof for P=NP, please tell me where I am wrong.

  • Working space: Symmetric(the distance from AB is equal to BA) Graph with N nodes and M edges.
  • Goal: find a Hamilton path.

In order to solve this problem I first would like to convert it to Symmetric TSP. I am doing this by setting all the edges that belong to M with the weight of 2 and all the rest with the weight of 3. Now if I be able to find a Hamilton path with the weight of 2M then it will be also the solution of UHP.

I will start explaining my idea with 2 examples, and then I show you the general case.

Example 1: Lets take a converted UHP to TSP graph where the node B have only two edges with the weight of 2, lets call them AB and BC. Because we know that the optimal solution will only have nodes with the weight of 2 we can tell that those two node will defiantly be part of the optimal tour. Now I am doing the interesting thing. I am removing the node B from the graph and all its edges and I am adding new edge AC with the weight of 1. This way I "force" the optimal tour to use it, just as I knew it would be used before.

Now I have a new TSP problem that is easier to solve, that I can give to another TSP solver to solve it for me. When I find the solution for this "easy" TSP problem, I can return the B node back to the graph with the edges AB and BC and it will be the optimal tour for my graph.

Edit: Example 2:

Lets take a converted UHP to TSP graph where the node E have only 3 edges with the weight of 2, lets call them AE,CE,DE. From the same reasons as in example 1 we can tell for sure that two of E edges will be part of the optimal route, there could be only 3 options for that:

  • AE + ED
  • AE + EB
  • BE + ED

So lets remove the node E from the graph and "cut" each of the options to one edge and add it with the weight of 1:

  • AE + ED -> AD
  • AE + EB -> AB
  • BE + ED -> BD

enter image description here

Its easy to see that the optimal tour is ABCD so there are more then one way to return E to the graph, we can do it from AD or AB because they are both on the optimal tour. We need to exam all the options and choose the one with shortest route, in this case AD.

Using this idea I want to remove a node that have more then just 2 edges with the weight of 2. Unlike the previous example I can't just add one edge after removing the node. Lets call our node E and the number of edges with the weight of two connected to this node K. I will have to add $\binom{K}{2}$ nodes. Than when I find my optimal tour it may contain more than one option, so I will choose the best of it.

This way I can "clean" the graph until there are only 3 nodes left and restore it, using the nodes/edges map that we created while removing edges and nodes.

This solution should take $O(N^2)$ time and $O(N)$ space.

*This solution will not work when the answer to USP is: There is no such path.

$\endgroup$
18
  • 9
    $\begingroup$ Claiming a solution and then having a disclaimer that there may not be a solution is very close to saying you don't actually have a solution... $\endgroup$
    – abiessu
    Nov 7 '13 at 13:39
  • 2
    $\begingroup$ This is not an announcement site, it is a question and answers site. We'd love it if you had a solution to P=NP, but this is not the place to announce it. $\endgroup$ Nov 7 '13 at 13:48
  • 2
    $\begingroup$ @ThomasAndrews What if I am not sure if I got it or not, where would you suggest me to seek for help? $\endgroup$ Nov 7 '13 at 13:49
  • 1
    $\begingroup$ Can you give an example of how you change the graph when $K=4$? And explain why in the new problem the solution won't take all four edges? $\endgroup$
    – user7530
    Nov 7 '13 at 13:53
  • 5
    $\begingroup$ I didn't downvote it, but the problem is the subject, which does not imply a question, but rather is an announcement. The fact that it announces the solution to an unsolved problem, with no humility, just smelled to me like crankery. If the subject was, "What is wrong with this proof that $P=NP$?" it would not have set off my "crank" alarm bells. $\endgroup$ Nov 7 '13 at 14:15
3
$\begingroup$

The way I see it (and the way I understand your approach), you have problems turning solutions of the reduced problem back into solutions of the original problem, because the solution of the subproblem may use more than one of the newly inserted edges. Take for example the following graph, which obviously does not have a Hamiltonian path:

A---B---F
       /|
      / |
     /  |
E---D   C

If you remove node F, and only show edges with a wight less than 3, you obtain the reduced problem

A---B
    |\
    | \
    |  \
E---D---C

since you add new edges for every pair of nodes which were connected to the removed node. This problem has a solution, namely ABCDE.

But turning that solution back into a solution for the original problem has to fail, since that original problem had no solution. In particular, the found solution will include more than one of the newly added edges, namely BC and CD in this case. Either edge would work if you were to reinsert F into the graph, but you can't reinsert F into both edges at the same time. And without inserting F into it, neither edge is valid in the original graph.

$\endgroup$
0
$\begingroup$

The way I see it is that you cannot assume that the optimal tour of TSP would somehow use the edge AC. Consider a graph of 5 vertices ABCDE where if you look at the subgraph of ACDE the edge AC is missing from an otherwise complete graph; and B is only connected to just A and C. Now once you remove B from the graph and replaced that with edge AC, then an optimal cycle would be AECD, which does not use AC edge at all.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.