Interestingly the shortest route question of the salesman problem (which is what everyone associates it with) is NP-hard and thus not necessarily even within NP. P vs NP is specifically about P vs NP complete whereas NP-hard is problems that are at least as hard as NP-complete but need not be in NP nor decision problems. So make sure you give the “is there a route <= k” version because the much more common “find the shortest route version” is not NP.
Somebody really should come up with better names. I know for a fact I knew the difference once, but right now I cannot even remember what it was without clicking the link. Surely many people who heard about this problem (and that's a lot of people, it's about as pop-mathy as it gets) don't even suspect these aren't synonymous.
Yes. A maximal value of k can be calculated as (largest weight in the graph) times (number of nodes in the graph). At that point you can do binary search to find the smallest k for which a solution exists.
Under the assumption that the <= question can be answered in polynomial time, this entire algorithm will also complete in polynomial time.
It’s indeed NP-complete if edge lengths are integers or otherwise discretized. But the general traveling salesman problem has no such restriction, so you can’t finitely enumerate in the general case.
In the general case, you just have a big list of edge weights, which means you have to be able to write the edge weights down.
If you want to represent the problem as a bunch of points in a Euclidean plane with free travel, that's a different (and easier) problem.
And even then, while it might take an infinite number of steps to specify the answer at infinite resolution, it will only take a finite number of steps to specify the answer at any level you're capable of writing down.
> it will only take a finite number of steps to specify the answer at any level you're capable of writing down.
That’s basically the good old “everything is O(1) because int64/float64 has 2^64 possibilities” misconception. It’s not how complexity theory works. For any N, 2^N is still finite, we’re obviously not talking about undecidable problems.
Edit: I see that you may be responding to the “finitely enumerate” part of my comment. Sure, it wasn’t phrased well. Replace with “enumerate in P”.
What are you fixing? Suppose you want to know the answer to within one part in 10¹⁰⁰. That will take you 333 questions.
Suppose you don't actually need 100 decimal places of the answer, or more likely that even if you had them you'd be unable to use them, and you can only represent the answer to 20 decimal places. That will take you 67 questions.
You can easily enumerate this answer in P. The problem in your argument isn't that float64 only has 2^64 values. Use as many bits to hold the answer as you want. No matter how many that is, it will be a finite number, and you'll be able to specify them all in a polynomial amount of time. Each question takes polynomial time to answer and fills one bit of the solution.
Okay apparently my complexity theory is rusty and I’m remembering results but not remembering the reasons for those results, so sorry about that. Determining optimal path length to a certain degree is indeed in the same class as the decision problem. It’s finding that optimal path (optimization problem) that’s not NP-complete.
> It’s finding that optimal path (optimization problem) that’s not NP-complete.
I'm having some trouble with this. As far as I can see, finding a path of a given maximum length must be in NP, because it's very easy to deterministically verify that a given path has length no more than the maximum.
If determining the optimal path length is in NP, and identifying a path of that length is also in NP, how can determining an optimal path fail to be in NP?
In this case np-complete and np-hard are closely linked: the optimization problem can be reduced to the decision version. Not all decision problems are like that (e.g. happy net problem), but for this one I don’t see the point making the distinction.
You can always reduce anything to anything, but in this case, the reduction is relevant because it only adds a polynomial factor. Showing that a problem can be reduced to another one in polynomial time is core to proving np-completeness.
That means that tsp and tso-opt are in the same ballpark of complexity. The reason tsp-opt isn't called np-complete isn't related to its complexity, but to the fact that only decision problems get to be called that.
As I said, there are problems where the decision problem and the optimization problem are completely unrelated in terms of complexity, but tsp isn't one of those.
Nope, the usual way of reducing optimization problem is to ask the corresponding yes/no question - for some fixed value x, is the optimal value greater than x?
If you can solve the decision problem, you can solve the optimization problem by doing a binary search on the x.
> Not all decision problems are like that (e.g. happy net problem)
Assuming you have an oracle for any question that you know how to verify, this is very easy to reduce:
Is there a solution in which vertices {1, 4, 6} are all positive?
First, let's establish that the question is legal: presented with a working solution, we can calculate the defining constraint of the problem, and we can check the polarity of vertices 1, 4, and 6. If this problem is in NP, verifying the constraint will take at most polynomial time. If not, not, but our question can be verified in however much time it takes to calculate the constraint.
The complexity of determining a solution by getting answers to questions of this form is interesting.
Case 1: The answer is "no" for all single-vertex sets. All vertices must be negative. This cannot actually happen, because all vertices being negative is the same thing as all vertices being positive.
Case 2: All vertices may be simultaneously positive. In this case, the answer to every question will be "yes", and we'll ask one question for every vertex in the input graph, solving the problem in sublinear time.
Case 3: We need some positive and some negative vertices. By asking about single-vertex sets, we can quickly identify a vertex that can be positive, vertex A.
We will include that vertex in every subsequent question. By the time we get there, we will have already asked about zero or more other vertices and been answered "no". We need never ask about those vertices again; they have to be negative and if we include them in any set, we'll get another "no".
So, let's ask about a never-before-examined vertex, vertex B. Can {A, B} be simultaneously positive?
If not, we can toss B into the "must be negative" pile, since we know A can be positive.
If so, we can include it in our developing solution; future questions will include vertices A and B. We still never need to reexamine any vertex that has ever been included in any of our questions.
So, unless I'm missing something, in this case we'll also produce a solution using one question per vertex in the graph.
> but for this one I don’t see the point making the distinction.
The distinction between NP-complete and NP-hard has nothing to do with the distinction between yes/no questions and open-ended questions. Those are unrelated concepts.
An NP-hard problem is at least as hard as any NP problem. It might be much harder.
An NP-complete problem is NP-hard, but it's also guaranteed to be an NP problem. That's the distinction.
> An NP-complete problem is NP-hard, but it's also guaranteed to be an NP problem. That's the distinction.
My point being that transforming tsp-opt to tsp only adds a polynomial factor. So in the case of tsp-opt, it's called NP-hard rather than NP-complete because it's not a decision problem, not because it's not equivalent in terms of time complexity as a problem in NP.
People simply call it NP-hard because that term is better known than NPO or NP-equivalent.
No, NP-Complete is only defined for decision problems. As OP specifically and correctly points out, NP hard applies to decision problems as well as search and optimization problems (and others as well).
You may review the following to clarify the distinction between the various NP complexity classes:
I for one have no idea about topology in general. I had to look up what a nice shape was... I thought it was some mathematical term.
The only thing I remember about is topology is someone telling me how it would be easier for me to untangle cables if I knew topology but alas I never learned.
Edit: presenting the problem with inverting functions is an unusual approach tho.