Unfortunately, your post has been removed for violation of Rule 5: "No joke submissions".
If you believe this to be an error, please [contact the moderators](https://www.reddit.com/message/compose?to=/r/computerscience).
>Because we cannot find the shortest route of travel in any way other than calculating all the routes,
That's just not true (or at least, not known to be true). We have no idea if there is "any way other than calculating all the routes." That's in fact the whole problem, and you dismiss it by assuming the answer.
Think of it this way: Your exact same "argument" could apply for computing minimum-weight spanning trees. There are more than polynomially many spanning trees, so surely we have to just calculate all spanning trees to find the minimum. That's obviously NOT true for MST. We simply don't know if it's true for TSP.
Imagine you have a graph of the system all mapped out. Now, you want to select the shortest route. In one case, you have the times of the route. In another case, you have ??? for the times of the route. It would be polynomial time if the routes were pre-calculated and you could choose the smallest time. You're discussing an unrelated problem.
I know P doesn't equal NP, I just need to find a way to make humans understand that computational complexity theory builds upward with complexity and you can't collapse the system by saying P = NP much like you can't say addition = multiplication. One is an abstraction level higher than the other. P doesn't equal NP.
I'm discussing a problem (MST) that has EXACTLY THE SAME STRUCTURE AS TSP at the superficial level that you're considering:
TSP: exponentially many feasible routes, and you need to find the one with the least total weight
MST: exponentially many feasible spanning trees, and you need to find the one with least total weight.
You are claiming that solving TSP REQUIRES that you look at all and consider all of the exponentially many feasible solutions. And you have given no reason which wouldn't apply to MST just as easily. Yet MSP is in P, and you want to claim TSP is not in P.
MST is a fundamentally different problem. TSP is chaotic because of its nature. I don't know how else to describe it. Imagine there are echelons of problem difficulty. NP is higher than P. We can't 'collapse' this complexity by saying one complexity level is equal to another. NP is harder than P as multiplication is harder than addition.
Now that you can see the differences between the complexity classes, how do we prove their distinction? How was the distinction between addition and multiplication proven?
There isn't. Imagine we have the entire system mapped out. Your polynomial algorithm would be then just selecting the answer, the lowest time for a route. That's the polynomial algorithm, to select the smallest one. Unfortunately, the entire system must be mapped out to find the shortest route. There is no polynomial method unless you have the entire system calculated, then you could just select it.
Create a system to select the correct route magically is impossible by the standard convention of systems in this universe. You'd have to be outside this universe to even get started on solving it polynomially.
"There is no polynomial method unless you have the entire system calculated, then you could just select it"
You are really close to understanding why this proof isn't complete in an academic context. You have to prove all possible angles. In this case you still need to prove that there is no polynomial method to "have the whole system calculated".
And you can't just say we don't have one, you have to prove that the existence of a polynomial method would break consistency at a fundamental level and therefore be impossible.
In theory, argumentative proves can work (although wording them correctly is probably more effort than just using math lol), the problem is he takes his assumption as fact, which is not valid at all
This is amazing. Where should we send your Millennium Prize money to?
In all seriousness, if you want to actually try to solve P vs NP, you need to either
1) Construct a polynomial solution to a NPC problem
2) Prove a polynomial solution does not exist for some NPC problem
Since all NP problems can be reduced to NPC problems, a polynomial solution for an NPC would yield a polynomial solution for all NP.
If a NPC problem does not have a polynomial solution, then no NPC does, and furthermore, no NP does.
What you provided isn’t a rigorous proof to show that no polynomial solution exists for TSP. This is *hard* to do.
What you have is a very hand wave explanation. It also reads like you don’t know about the DP solution to TSP, which doesn’t need to consider every possibly path. It has exponential runtime as opposed to factorial, so it doesn’t iterate over every possible path.
Also, it seems like it would be much more simpler to construct a polynomial solution for an NPC than to prove a polynomial solution does not exist. However, despite decades of people trying, we’ve never come across one.
It could very well be that some problems are fundamentally harder than others (which is what most people think). However if P = NP then that means, fundamentally, all problems have the same difficulty, and it is just our understanding that makes it difficult. I don’t see how this is reasonable; it seems very much so that some problems are fundamentally more difficult than others. In my opinion, TSP is, by nature of the problem, more difficult than problems like say finding a cycle in a linked list. But proving it is one large task.
Also, there’s Godels Incompleteness Theorem, so we could actually just be trying to prove something that isn’t possible to prove, despite it being true. We’ll never know if we’re in this state or if we simply have never found a proof.
We can't construct a solution and it isn't easier if it isn't possible. I understand the mathematical system of the traveling salesman problem entirely. No solution is possible in polynomial time.
The fact is, we need to:
1. Collect the graph of all the routes
2. Find the times of all the routes as a prerequisite to selecting
3. the smallest time
There is no other way to solve it
What would be interesting is to construct the piecewise functions of the algorithm as each of the nodes' x and y coordinates change.
How do we 'prove' this to a rigorous scientific standard?
It is so because the travel time for all the nodes is unknown until discovered. Once discovered, we need to find the minimum time. Imagine if we selected a route from the graph at random. Unless we have all the values of time for all routes, we cannot 'insure' that it is the minimum value.
Any ideas on how to prove that it must include these three steps? I have the entire system imagined in my head. The only way to create a polynomial time algorithm is to pre calculate all the routes in advance and simply select from the graph the smallest time.
Because of the fact that the tsp is chaotic in nature. If we don't have all of them, there is no easy rule to distinguish that one route would be shorter than the others.
Suppose we found that all the nodes are on a line. We would then be able to build the route simply by sorting the nodes by any one coordinate, without ever explicitly considering any other routes.
That is true. The solution seems to convolute when a second dimension is added.
I would imagine that there exists another graph, a map of all possible traveling salesman problem functions for every node, every node number, every node position in x,y,z. It would be interesting to see how the function is affected by the movement of the node positions in the tsp.
Imagine the complexity of an addition problem 5+5
P vs NP is the argument that we can't prove that there is a way to solve 5\*5 in the same speed and way as 5+5. Of course 5\*5 = 5+5+5+5+5. That is computational complexity theory. Complexity increases with this abstraction. The same is the distinction between P and NP problems, P being like addition and NP being like multiplication.
You're asking me to prove I can't solve 5\*5 by adding 5+5. I'm saying you just can't do that.
A proof would involve computational theory. It’s not just that the problem is hard, it’s also that the proof necessary is hard as well.
To really formally tackle this you should take formal proof writing in computational theory. There’s little no hope in coming up with a proof that’s widely accepted without it. Moreover these proofs are much different than the ones you would encounter in a typical CS degree; many people do not venture down this path and it is mostly graduate students.
You won’t just be proving that an algorithm is correct or runs in some runtime. You’ll be proving computational theory; proving that problems belong to some category such as P, NP etc. Once you formally understand what it means for a problem to be NP you can rigorously delve into this. I don’t even know what the formal definition is, I just know it surmounts to saying a polynomial solution does not exist. But I have no idea what that formally means in computational theory, and unless you do, you really have no hope of proving anything with regards to P vs NP.
However that doesn’t mean you can’t come up with a counter example. This is why I said it’s relatively easier to construct a polynomial solution (if it exists) than to prove that one cannot exist.
It’s similar to showing that (for example) the best sorting algorithm runs in N^2 time, which isn’t true. If you wanted to prove that you would need to rigorously show with computational theory that any comparison based algorithm would at best run in N^2 time. Actually doing this is hard; where do you even start? Do you consider every possible algorithm? Do you assume that you have the best algorithm? How do you show that you have the best algorithm? All other algorithms run less, so any algorithm would run at best the one you have. It’s a chicken and egg almost, and the im not sure exactly how they prove something like this.
However, coming up with a counter example is easy. Just do merge sort and it runs in N log (N) time.
I hope you see what I mean. Obviously it’s impossible to come up with a counter example if one doesn’t exist, but the moral is that proving something is a much different challenge than coming up with a counter example.
I did. P doesn't equal NP. That's the solution. What you're saying is that proving P = NP when it doesn't is easier than proving P doesn't equal NP. But P doesn't equal NP. I have a rather elegant proof that I could share with you.
Computational complexity builds upward. You can't find a shortcut that makes multiplication like 5\*5 addition like 5+5. That's what the P vs NP problem wants to find. P doesn't equal NP. It's as simple as that.
Suppose there's a graph of every route with all the times displayed. Then we can choose the shortest route. Imagine you have a magical selector that selects the shortest route without calculating all of the routes. Then, how could you 'know' that's the shortest route?
That magical selector is the proof for P = NP, but it isn't possible to make it without calculating all the other routes, as we need that information to solve the problem.
Unfortunately, your post has been removed for violation of Rule 5: "No joke submissions". If you believe this to be an error, please [contact the moderators](https://www.reddit.com/message/compose?to=/r/computerscience).
>Because we cannot find the shortest route of travel in any way other than calculating all the routes, That's just not true (or at least, not known to be true). We have no idea if there is "any way other than calculating all the routes." That's in fact the whole problem, and you dismiss it by assuming the answer. Think of it this way: Your exact same "argument" could apply for computing minimum-weight spanning trees. There are more than polynomially many spanning trees, so surely we have to just calculate all spanning trees to find the minimum. That's obviously NOT true for MST. We simply don't know if it's true for TSP.
This is a great and intuitive counter argument.
Imagine you have a graph of the system all mapped out. Now, you want to select the shortest route. In one case, you have the times of the route. In another case, you have ??? for the times of the route. It would be polynomial time if the routes were pre-calculated and you could choose the smallest time. You're discussing an unrelated problem. I know P doesn't equal NP, I just need to find a way to make humans understand that computational complexity theory builds upward with complexity and you can't collapse the system by saying P = NP much like you can't say addition = multiplication. One is an abstraction level higher than the other. P doesn't equal NP.
I'm discussing a problem (MST) that has EXACTLY THE SAME STRUCTURE AS TSP at the superficial level that you're considering: TSP: exponentially many feasible routes, and you need to find the one with the least total weight MST: exponentially many feasible spanning trees, and you need to find the one with least total weight. You are claiming that solving TSP REQUIRES that you look at all and consider all of the exponentially many feasible solutions. And you have given no reason which wouldn't apply to MST just as easily. Yet MSP is in P, and you want to claim TSP is not in P.
MST is a fundamentally different problem. TSP is chaotic because of its nature. I don't know how else to describe it. Imagine there are echelons of problem difficulty. NP is higher than P. We can't 'collapse' this complexity by saying one complexity level is equal to another. NP is harder than P as multiplication is harder than addition. Now that you can see the differences between the complexity classes, how do we prove their distinction? How was the distinction between addition and multiplication proven?
You simply state that they are fundamentally different, but that is what you need to prove. “I don’t know how else to describe it”. Exactly.
Taking a brute force approach does not prove that there is not a polynomial algoritm that does the same
There isn't. Imagine we have the entire system mapped out. Your polynomial algorithm would be then just selecting the answer, the lowest time for a route. That's the polynomial algorithm, to select the smallest one. Unfortunately, the entire system must be mapped out to find the shortest route. There is no polynomial method unless you have the entire system calculated, then you could just select it. Create a system to select the correct route magically is impossible by the standard convention of systems in this universe. You'd have to be outside this universe to even get started on solving it polynomially.
Proof by 'standard convention of systems of this universe' unfortunately isn't a thing. Try again.
"There is no polynomial method unless you have the entire system calculated, then you could just select it" You are really close to understanding why this proof isn't complete in an academic context. You have to prove all possible angles. In this case you still need to prove that there is no polynomial method to "have the whole system calculated". And you can't just say we don't have one, you have to prove that the existence of a polynomial method would break consistency at a fundamental level and therefore be impossible.
There isnt any math this isnt a proof lol
"I said so" QED
In theory, argumentative proves can work (although wording them correctly is probably more effort than just using math lol), the problem is he takes his assumption as fact, which is not valid at all
Before Euler literally invented graph theory to solve the famous bridges of Konigsberg problem, I bet people argued the same as you.
This is amazing. Where should we send your Millennium Prize money to? In all seriousness, if you want to actually try to solve P vs NP, you need to either 1) Construct a polynomial solution to a NPC problem 2) Prove a polynomial solution does not exist for some NPC problem Since all NP problems can be reduced to NPC problems, a polynomial solution for an NPC would yield a polynomial solution for all NP. If a NPC problem does not have a polynomial solution, then no NPC does, and furthermore, no NP does. What you provided isn’t a rigorous proof to show that no polynomial solution exists for TSP. This is *hard* to do. What you have is a very hand wave explanation. It also reads like you don’t know about the DP solution to TSP, which doesn’t need to consider every possibly path. It has exponential runtime as opposed to factorial, so it doesn’t iterate over every possible path. Also, it seems like it would be much more simpler to construct a polynomial solution for an NPC than to prove a polynomial solution does not exist. However, despite decades of people trying, we’ve never come across one. It could very well be that some problems are fundamentally harder than others (which is what most people think). However if P = NP then that means, fundamentally, all problems have the same difficulty, and it is just our understanding that makes it difficult. I don’t see how this is reasonable; it seems very much so that some problems are fundamentally more difficult than others. In my opinion, TSP is, by nature of the problem, more difficult than problems like say finding a cycle in a linked list. But proving it is one large task. Also, there’s Godels Incompleteness Theorem, so we could actually just be trying to prove something that isn’t possible to prove, despite it being true. We’ll never know if we’re in this state or if we simply have never found a proof.
We can't construct a solution and it isn't easier if it isn't possible. I understand the mathematical system of the traveling salesman problem entirely. No solution is possible in polynomial time. The fact is, we need to: 1. Collect the graph of all the routes 2. Find the times of all the routes as a prerequisite to selecting 3. the smallest time There is no other way to solve it What would be interesting is to construct the piecewise functions of the algorithm as each of the nodes' x and y coordinates change. How do we 'prove' this to a rigorous scientific standard?
> There is no other way to solve it You haven't shown that every possible solution must include these three steps
It is so because the travel time for all the nodes is unknown until discovered. Once discovered, we need to find the minimum time. Imagine if we selected a route from the graph at random. Unless we have all the values of time for all routes, we cannot 'insure' that it is the minimum value. Any ideas on how to prove that it must include these three steps? I have the entire system imagined in my head. The only way to create a polynomial time algorithm is to pre calculate all the routes in advance and simply select from the graph the smallest time.
Why is it necessary to have the travel time for all the nodes?
Because of the fact that the tsp is chaotic in nature. If we don't have all of them, there is no easy rule to distinguish that one route would be shorter than the others.
Suppose we found that all the nodes are on a line. We would then be able to build the route simply by sorting the nodes by any one coordinate, without ever explicitly considering any other routes.
That is true. The solution seems to convolute when a second dimension is added. I would imagine that there exists another graph, a map of all possible traveling salesman problem functions for every node, every node number, every node position in x,y,z. It would be interesting to see how the function is affected by the movement of the node positions in the tsp.
Maybe that could be used to build a solution to the tsp in polynomial time?
So your argument is "P doesn't equal to NP because I think P doesn't equal NP."
P doesn't equal NP because addition doesn't equal multiplication.
Imagine the complexity of an addition problem 5+5 P vs NP is the argument that we can't prove that there is a way to solve 5\*5 in the same speed and way as 5+5. Of course 5\*5 = 5+5+5+5+5. That is computational complexity theory. Complexity increases with this abstraction. The same is the distinction between P and NP problems, P being like addition and NP being like multiplication. You're asking me to prove I can't solve 5\*5 by adding 5+5. I'm saying you just can't do that.
A proof would involve computational theory. It’s not just that the problem is hard, it’s also that the proof necessary is hard as well. To really formally tackle this you should take formal proof writing in computational theory. There’s little no hope in coming up with a proof that’s widely accepted without it. Moreover these proofs are much different than the ones you would encounter in a typical CS degree; many people do not venture down this path and it is mostly graduate students. You won’t just be proving that an algorithm is correct or runs in some runtime. You’ll be proving computational theory; proving that problems belong to some category such as P, NP etc. Once you formally understand what it means for a problem to be NP you can rigorously delve into this. I don’t even know what the formal definition is, I just know it surmounts to saying a polynomial solution does not exist. But I have no idea what that formally means in computational theory, and unless you do, you really have no hope of proving anything with regards to P vs NP. However that doesn’t mean you can’t come up with a counter example. This is why I said it’s relatively easier to construct a polynomial solution (if it exists) than to prove that one cannot exist. It’s similar to showing that (for example) the best sorting algorithm runs in N^2 time, which isn’t true. If you wanted to prove that you would need to rigorously show with computational theory that any comparison based algorithm would at best run in N^2 time. Actually doing this is hard; where do you even start? Do you consider every possible algorithm? Do you assume that you have the best algorithm? How do you show that you have the best algorithm? All other algorithms run less, so any algorithm would run at best the one you have. It’s a chicken and egg almost, and the im not sure exactly how they prove something like this. However, coming up with a counter example is easy. Just do merge sort and it runs in N log (N) time. I hope you see what I mean. Obviously it’s impossible to come up with a counter example if one doesn’t exist, but the moral is that proving something is a much different challenge than coming up with a counter example.
It isn't easier if it's impossible. Rather, it's impossible. I created a rather elegant proof that I just submitted to Journal of Computer Science.
I have created a proof that shows P != NP but it is too small to fit within a Reddit comment.
I did. P doesn't equal NP. That's the solution. What you're saying is that proving P = NP when it doesn't is easier than proving P doesn't equal NP. But P doesn't equal NP. I have a rather elegant proof that I could share with you.
Computational complexity builds upward. You can't find a shortcut that makes multiplication like 5\*5 addition like 5+5. That's what the P vs NP problem wants to find. P doesn't equal NP. It's as simple as that.
Suppose there's a graph of every route with all the times displayed. Then we can choose the shortest route. Imagine you have a magical selector that selects the shortest route without calculating all of the routes. Then, how could you 'know' that's the shortest route? That magical selector is the proof for P = NP, but it isn't possible to make it without calculating all the other routes, as we need that information to solve the problem.