# Tag Info

36

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances. The class of problems where you can verify "no" instances in polynomial time is co-NP. Any language in co-NP is the complement of some language in NP, and vice-versa. Examples include things like non-3-colourability. The problem you ...

32

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time. But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial time, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 \times n^2$ Sudoku is NP-complete. The proof of NP-completeness ...

26

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the ...

16

Full details are in Robert L. Karg and James L. Thompson, A Heuristic Approach to Solving Traveling Salesman Problems (Management Science, 10(2):225–248, 1964). The PDF is available from JStor and Informs.org (both paywalled). This is the paper that produced the optimal tour of 10,861 miles. It also includes the full distance table but I'll not ...

11

TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem. When you reduce one NP-complete problem to another one, the size of the problem usually grows polynomially. For example, when you reduce a HAMPATH on a graph with $n$ nodes to SAT, the resulting formula has size of $\Theta(n^... 11 If vertices can be visited more than once, then yes: you can create$n+1$copies of the graph, with each vertex$v$in the original graph becoming the$n+1$vertices$v_1, \dots, v_{n+1}$and each edge$uv$in the original graph becoming the set of edges$u_iv_{i+1}$for all$1 \le i \le n$; now run Dijkstra on the resulting graph with start vertex$A_1$and ... 11 First, it's important to recognize the gravity of what you are proposing. If correct, your algorithm is worth$1 Million USD. Secondly, many many people have tried and failed to solve this problem. So it's important to approach this with the assumption that you are wrong, and to exhaustively try to disprove yourself. The next step is to prove two things: ...

10

There are exponentially many such routes. Think of a sequence of $n$ diamonds. At each diamond, you can go either left or right, independently of what you do at all other diamonds. This leads to $2^n$ paths, each of which is non-intersecting. Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on ...

8

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a ...

7

Consider a ladder a----b----c | | | d----e----f Say length of a-b is $2$ and length of a-d is $1$. The optimal route is a-b-c-f-e-d-a, $10$ units long. Starting at a, NN would produce a-d-e-b-c-f-a which is $7 + \sqrt{17} > 11$ units long. There is actually a four node example, a rhombus A /|\ B-+-C \|/ D Say length of B-C is $10$, length ...

7

there are many papers on using artificial neural networks to solve TSP including recurrent and Hopfield networks, and they "succeed" in a rough sense, but so far there does not seem to be any evidence that the techniques are in any way (strongly?) superior to other algorithmic approaches, so its something more like a research curiosity at the moment. the use ...

7

We may reason in a combinatorial way. There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on any of the $n$ nodes, and we may choose the direction in $2$ ways. Therefore, each tour was counted a total of $2n$ times. This yields the desired result.

7

No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)

7

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...

6

You missed the footnote — these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations in $S_3$ without fixed points (also known as derangements), namely $(123)$ and $(132)$. More generally, for a $k$-opt move it is enough to consider permutations without fixed points, since those with $... 6 This Medium post lists the latest (not a full list of course) studies in the combinatorial optimization domain. All three papers use Deep Reinforcement Learning, which does not need any training set but learns completely from its own experience. I have been working on the first paper for some time and inference time is on milliseconds level. According to ... 6 What Fiorini et al. show is the following: The TSP polytope$P_n$over$n$points is a polytope in$\binom{n}{2}$dimensions whose vertices correspond to all Hamiltonian cycles in$K_n$(the complete graph on$n$vertices). (That is, it is the convex hull of the indicator vectors of all Hamiltonian cycles.) Suppose that$X_n$is a polytope whose projection ... 6 I suggest you read more about the Traveling Salesman Problem. All of your questions are answered in other standard references (such as the Wikipedia link I gave). No, the greedy algorithm is not optimal. You may be interested in the Euclidean TSP, which remains NP-hard. The greedy algorithm is not optimal for that case, either. No efficient algorithm is ... 6 This mostly comes down to what makes an interesting problem, and what can be easily analyzed. The restriction of visiting each vertex once is common in these sorts of problems. A traversal that visits each vertex no more than once is called a "path", and these are well-studied in graph theory, so there are quite a few existing theorems based on them. The ... 5 If$optTSP$is in$NP$, then$coNP = NP$. The latter is unresolved currently. Proof: if$optTSP$is in$NP$, then$coTSP$is in$coNP$(the certificate being whatever certificate was provided to verify a solution to$optTSP$was minimal, and then comparing the value of that solution to the desired bound). And because$TSP$is$NP$-complete then this ... 5 Here is what these lecture notes have to say. We can reduce HAMILTONIAN-PATH to MIN-TSP-TOUR in the following way: give the weight$1$for edges in the original graph, and$B$(for some$B > 1$to be chosen later) for edges not in the original graph. If the original graph had a Hamiltonian path, then the new path has a tour of length at most$n$, and ... 5 The following answer is to give an intuition of how a situation can look that fails. Karolis Juodelė's answer is much better than this, but I find the following example to give a nice intuition. Let's say that we look for shortest TSP path, and not cycle, with predefined starting vertex, consider the graph below with X being the starting vertex, one dash ... 5 As a simple method, you can use the roulette wheel selection. The idea is that every individual has a chance to be selected as a parent, but the more fit an individual is, the more likely it is to be selected. Let$f_i$be the fitness of the individual$i$. The probability$p_i$of choosing$i$as a parent for the next round is$p_i = f_i / \sum_{j=1}^{N}$, ... 5 I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better. 5 What you're proposing isn't "a linear program for TSP", so it doesn't come into the scope of the proof. You've observed that, if$\mathrm{P=NP}$, then TSP can be reduced to polynomial-sized linear programs. You're using a polynomial-time Turing machine to perform a slightly more complicated version of the following reduction: if the input graph$G$... 4 Hint: Every TSP tour has the same number of edges. Use this to modify the weights in the graph in a way which affects all TSP tours in the same way. 4 If the edges don't satisfy the triangle inequality then the problem becomes harder. In your case the non-edges have infinite weight (since you want never to use them), so you can't expect Christofides' algorithm to be useful as such. 4 When we say that TSP is hard to approximate up to a factor$\alpha$, this means that if there was an algorithm for TSP which always outputs a number in$[OPT,\alpha OPT]$then P=NP (here OPT is the length of the minimal tour). The algorithm doesn't have to find a tour of this length. Even more formally, what these results (probably) show is that there is a ... 4 One can exploit planar separator structures in a geometric setting and thus solve Euclidean TSP exactly in$O(n^{c \sqrt{n}})$time, where$c$is some small constant greater than 1. There's at least three simultaneous results for this; Smith's PhD thesis [1], Kann's PhD thesis [2], and Hwang et al. [3]. Each algorithm has a running time of$O^*(c^{\sqrt{n} \...

4

The worst case running time of Concorde or any other known method is exponential in the size of the input. However, sometimes heuristics or other pruning techniques are effective and you are able to solve some, even large, instances pretty quickly. You should define exactly what you mean by TSP as there are many variants, and many algorithms with different ...

Only top voted, non community-wiki answers of a minimum length are eligible