New answers tagged

3

Metric TSP is NP-complete - hence yes, assuming you can solve the metric TSP in $6(n^{12})$, this is good enough to prove $P=NP$. Giving a blackbox that can do that, would be a quite strong evidence (if it actually works). But there are some considerations one should take into account: it actually could be somewhat dangerous, as someone else could figure ...


0

I find it most easy to understand by using the 3-SAT NP-complete problem: There are $n$ boolean variables and you can decide for each of them either to be set the $true$ or $false$ value and you are given $k$ clauses. Each of the clauses contains 3 variables and the constraints to them, like $(true OR false OR true)$, so the clauese would be satisfied if ...


1

NP is all about decision problems - problems where the answer is "yes" or "no". A problem is in NP if for every instance where the answer is "yes", there is a hint that let's you easily prove that the answer is "yes". It doesn't say anything about instances where the answer is "no". They can be hard to solve. The classical Travelling Salesman problem is: ...


6

$P$ and $NP$ are classes of decision problems. The result of an algorithm for a decision problem is either "YES" or "NO". Even for a problem in $P$, such an answer cannot lead to a quick verification. An instance of the decision problem version of TSP is "Given a collection of cities and intercity distances, is there a tour with total length less than $k$?...


15

There is a lot of decent answers here but none clear up a couple fairly important misunderstandings you seem to have. Both P and NP are classes of what are called "decision problems." These are problems whose answer is YES or NO. (More formally they are all questions of given a string and a language, is the string in the language but that isn't an ...


43

Your version of the TSP is actually NP-hard, exactly for the reasons you state. It is hard to check that it is the correct solution. The version of the TSP that is NP-complete is the decision version of the problem (quoting Wikipedia): The decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) ...


Top 50 recent answers are included