If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?When can a greedy algorithm solve the coin change problem?Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ timeCan Euclidean TSP be exactly solved in time better than (sym)metric TSP?How to find partition set of a Partition Problem using its decision problemHow can we design an efficient warehouse management program?Finding vertices of a maximum clique in polynomial timeIs this an instance of a well-known problem?Is any sudoku solver an SAT solver?Applying a permutation on a sequence with multiplicationSolve this integer program (problem: Travelling salesman problem)
Bach's Toccata and Fugue in D minor breaks the "no parallel octaves" rule?
How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?
Can a druid choose the size of its wild shape beast?
How do I change two letters closest to a string and one letter immediately after a string using Notepad++?
What is the adequate fee for a reveal operation?
Why does a Star of David appear at a rally with Francisco Franco?
Is "upgrade" the right word to use in this context?
What options are left, if Britain cannot decide?
Tikz diagrams and node placements
Why is the President allowed to veto a cancellation of emergency powers?
Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?
How do you talk to someone whose loved one is dying?
My adviser wants to be the first author
how to draw this figure in latex
Employee lack of ownership
Can a one-dimensional blade cut everything ? (chainsaw) (Sword)
Violin - Can double stops be played when the strings are not next to each other?
PTIJ: Who should I vote for? (21st Knesset Edition)
et qui - how do you really understand that kind of phraseology?
What did Alexander Pope mean by "Expletives their feeble Aid do join"?
How could a scammer know the apps on my phone / iTunes account?
Why Choose Less Effective Armour Types?
Was Shankara a bhakta of Saguna Brahman Narayana or did he consider Nirguna Brahman to be supreme?
This word with a lot of past tenses
If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?
When can a greedy algorithm solve the coin change problem?Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ timeCan Euclidean TSP be exactly solved in time better than (sym)metric TSP?How to find partition set of a Partition Problem using its decision problemHow can we design an efficient warehouse management program?Finding vertices of a maximum clique in polynomial timeIs this an instance of a well-known problem?Is any sudoku solver an SAT solver?Applying a permutation on a sequence with multiplicationSolve this integer program (problem: Travelling salesman problem)
$begingroup$
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.
Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?
If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.
algorithms np-complete reductions traveling-salesman sudoku
edited 2 hours ago
Rodrigo de Azevedo
700615
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 4 more comments
$begingroup$
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.
Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?
If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.
algorithms np-complete reductions traveling-salesman sudoku
edited 2 hours ago
Rodrigo de Azevedo
700615
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
6
$begingroup$
Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
$endgroup$
– Wildcard
yesterday
$begingroup$
@Wildcard done.
$endgroup$
– Chakrapani N Rao
yesterday
11
$begingroup$
@Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
$endgroup$
– David Richerby
23 hours ago
4
$begingroup$
@DavidRicherby, I am quite familiar with the traveling salesman problem but have never encountered it by that acronym. Perhaps a better analogy than "PC" would be "IE." There are plenty of Windows users who use Internet Explorer who may never have encountered that acronym.
$endgroup$
– Wildcard
22 hours ago
5
$begingroup$
@DavidRicherby Just because someone isn't familiar with an acronym doesn't mean that they wouldn't get anything out of the question. And having it spelled out in the title helps searching.
$endgroup$
– Acccumulation
21 hours ago
|
show 4 more comments
$begingroup$
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.
Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?
If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.
algorithms np-complete reductions traveling-salesman sudoku
edited 2 hours ago
Rodrigo de Azevedo
700615
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.
Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?
If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.
algorithms np-complete reductions traveling-salesman sudoku
algorithms np-complete reductions traveling-salesman sudoku
edited 2 hours ago
Rodrigo de Azevedo
700615
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 hours ago
Rodrigo de Azevedo
700615
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 hours ago
Rodrigo de Azevedo
700615
edited 2 hours ago
Rodrigo de Azevedo
700615
edited 2 hours ago
Rodrigo de Azevedo
700615
700615
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
asked yesterday
Chakrapani N RaoChakrapani N Rao
6918
6918
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Chakrapani N Rao is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
6
$begingroup$
Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
$endgroup$
– Wildcard
yesterday
$begingroup$
@Wildcard done.
$endgroup$
– Chakrapani N Rao
yesterday
11
$begingroup$
@Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
$endgroup$
– David Richerby
23 hours ago
4
$begingroup$
@DavidRicherby, I am quite familiar with the traveling salesman problem but have never encountered it by that acronym. Perhaps a better analogy than "PC" would be "IE." There are plenty of Windows users who use Internet Explorer who may never have encountered that acronym.
$endgroup$
– Wildcard
22 hours ago
5
$begingroup$
@DavidRicherby Just because someone isn't familiar with an acronym doesn't mean that they wouldn't get anything out of the question. And having it spelled out in the title helps searching.
$endgroup$
– Acccumulation
21 hours ago
|
show 4 more comments
6
$begingroup$
Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
$endgroup$
– Wildcard
yesterday
$begingroup$
@Wildcard done.
$endgroup$
– Chakrapani N Rao
yesterday
11
$begingroup$
@Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
$endgroup$
– David Richerby
23 hours ago
4
$begingroup$
@DavidRicherby, I am quite familiar with the traveling salesman problem but have never encountered it by that acronym. Perhaps a better analogy than "PC" would be "IE." There are plenty of Windows users who use Internet Explorer who may never have encountered that acronym.
$endgroup$
– Wildcard
22 hours ago
5
$begingroup$
@DavidRicherby Just because someone isn't familiar with an acronym doesn't mean that they wouldn't get anything out of the question. And having it spelled out in the title helps searching.
$endgroup$
– Acccumulation
21 hours ago
6
6
$begingroup$
Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
$endgroup$
– Wildcard
yesterday
$begingroup$
Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
$endgroup$
– Wildcard
yesterday
$begingroup$
@Wildcard done.
$endgroup$
– Chakrapani N Rao
yesterday
$begingroup$
@Wildcard done.
$endgroup$
– Chakrapani N Rao
yesterday
11
11
$begingroup$
@Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
$endgroup$
– David Richerby
23 hours ago
$begingroup$
@Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
$endgroup$
– David Richerby
23 hours ago
4
4
$begingroup$
@DavidRicherby, I am quite familiar with the traveling salesman problem but have never encountered it by that acronym. Perhaps a better analogy than "PC" would be "IE." There are plenty of Windows users who use Internet Explorer who may never have encountered that acronym.
$endgroup$
– Wildcard
22 hours ago
$begingroup$
@DavidRicherby, I am quite familiar with the traveling salesman problem but have never encountered it by that acronym. Perhaps a better analogy than "PC" would be "IE." There are plenty of Windows users who use Internet Explorer who may never have encountered that acronym.
$endgroup$
– Wildcard
22 hours ago
5
5
$begingroup$
@DavidRicherby Just because someone isn't familiar with an acronym doesn't mean that they wouldn't get anything out of the question. And having it spelled out in the title helps searching.
$endgroup$
– Acccumulation
21 hours ago
$begingroup$
@DavidRicherby Just because someone isn't familiar with an acronym doesn't mean that they wouldn't get anything out of the question. And having it spelled out in the title helps searching.
$endgroup$
– Acccumulation
21 hours ago
|
show 4 more comments
2 Answers
2
active
oldest
votes
$begingroup$
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, 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 works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.
answered yesterday
D.W.♦D.W.
101k12125289
$endgroup$
1
$begingroup$
Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
$endgroup$
– Chakrapani N Rao
yesterday
2
$begingroup$
@ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
$endgroup$
– D.W.♦
yesterday
5
$begingroup$
@ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
$endgroup$
– David Richerby
yesterday
$begingroup$
OK, so we do not have a working solution for the above question then?
$endgroup$
– Chakrapani N Rao
yesterday
4
$begingroup$
@ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
$endgroup$
– David Richerby
23 hours ago
|
show 1 more comment
$begingroup$
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 details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.
answered 22 hours ago
rlmsrlms
23114
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Chakrapani N Rao is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105618%2fif-i-can-solve-sudoku-can-i-solve-the-travelling-salesman-problem-tsp-if-so%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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, 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 works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.
answered yesterday
D.W.♦D.W.
101k12125289
$endgroup$
1
$begingroup$
Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
$endgroup$
– Chakrapani N Rao
yesterday
2
$begingroup$
@ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
$endgroup$
– D.W.♦
yesterday
5
$begingroup$
@ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
$endgroup$
– David Richerby
yesterday
$begingroup$
OK, so we do not have a working solution for the above question then?
$endgroup$
– Chakrapani N Rao
yesterday
4
$begingroup$
@ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
$endgroup$
– David Richerby
23 hours ago
|
show 1 more comment
$begingroup$
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, 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 works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.
answered yesterday
D.W.♦D.W.
101k12125289
$endgroup$
1
$begingroup$
Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
$endgroup$
– Chakrapani N Rao
yesterday
2
$begingroup$
@ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
$endgroup$
– D.W.♦
yesterday
5
$begingroup$
@ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
$endgroup$
– David Richerby
yesterday
$begingroup$
OK, so we do not have a working solution for the above question then?
$endgroup$
– Chakrapani N Rao
yesterday
4
$begingroup$
@ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
$endgroup$
– David Richerby
23 hours ago
|
show 1 more comment
$begingroup$
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, 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 works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.
answered yesterday
D.W.♦D.W.
101k12125289
$endgroup$
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, 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 works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.
answered yesterday
D.W.♦D.W.
101k12125289
edited yesterday
answered yesterday
D.W.♦D.W.
101k12125289
answered yesterday
D.W.♦D.W.
101k12125289
answered yesterday
D.W.♦D.W.
101k12125289
101k12125289
1
$begingroup$
Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
$endgroup$
– Chakrapani N Rao
yesterday
2
$begingroup$
@ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
$endgroup$
– D.W.♦
yesterday
5
$begingroup$
@ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
$endgroup$
– David Richerby
yesterday
$begingroup$
OK, so we do not have a working solution for the above question then?
$endgroup$
– Chakrapani N Rao
yesterday
4
$begingroup$
@ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
$endgroup$
– David Richerby
23 hours ago
|
show 1 more comment
1
$begingroup$
Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
$endgroup$
– Chakrapani N Rao
yesterday
2
$begingroup$
@ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
$endgroup$
– D.W.♦
yesterday
5
$begingroup$
@ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
$endgroup$
– David Richerby
yesterday
$begingroup$
OK, so we do not have a working solution for the above question then?
$endgroup$
– Chakrapani N Rao
yesterday
4
$begingroup$
@ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
$endgroup$
– David Richerby
23 hours ago
1
1
$begingroup$
Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
$endgroup$
– Chakrapani N Rao
yesterday
$begingroup$
Could you please explain how? Yes lets assume I have general sudoku solver which acts as a black box. So how can you use it? How do you represent TSP as a partially filled Sudoku
$endgroup$
– Chakrapani N Rao
yesterday
2
2
$begingroup$
@ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
$endgroup$
– D.W.♦
yesterday
$begingroup$
@ChakrapaniNRao, see updated answer. Yes, I understand it is a black box. To work out the details, find the proof of NP-completeness for Sudoku and understand how the reduction works.
$endgroup$
– D.W.♦
yesterday
5
5
$begingroup$
@ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
$endgroup$
– David Richerby
yesterday
$begingroup$
@ChakrapaniNRao It doesn't answer the question completely but the full answer would be ridiculously long, be full of intricate details and wouldn't give you any more enlightenment than the sketch here. It's possible that a reduction of some NP-complete problem to $n^2times n^2$ sudoku might be interesting but, unless the proof that sudoku is NP-complete was actually by reduction from TSP (unlikely), the answer is still going to end "and then chain those two reductions together".
$endgroup$
– David Richerby
yesterday
$begingroup$
OK, so we do not have a working solution for the above question then?
$endgroup$
– Chakrapani N Rao
yesterday
$begingroup$
OK, so we do not have a working solution for the above question then?
$endgroup$
– Chakrapani N Rao
yesterday
4
4
$begingroup$
@ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
$endgroup$
– David Richerby
23 hours ago
$begingroup$
@ChakrapaniNRao You are asking how to solve problem X using a black box for problem Y. That is literally asking for a reduction. That's what "reduction" means. And, as this answer explains, the answer to your yes/no question is yes.
$endgroup$
– David Richerby
23 hours ago
|
show 1 more comment
$begingroup$
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 details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.
answered 22 hours ago
rlmsrlms
23114
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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 details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.
answered 22 hours ago
rlmsrlms
23114
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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 details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.
answered 22 hours ago
rlmsrlms
23114
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
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 details of the reduction isn't particularly illuminating. If you want, you can piece it together by using the simple reduction from Latin square completion to Sudoku here, the reduction from triangulating uniform tripartite graphs to Latin square completion here, the reduction from 3SAT to triangulation here, and a formulation of TSP as a 3SAT problem. However, if you want to understand the idea behind reducing from Sudoku to TSP I think you would be better off studying Cook's theorem (showing that SAT is NP-complete) and a couple of simple reductions from 3SAT (e.g. to 3-dimensional matching) and being satisfied in the knowledge that the TSP-Sudoku reduction is just the same kind of thing but longer and more fiddly.
answered 22 hours ago
rlmsrlms
23114
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 22 hours ago
rlmsrlms
23114
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 22 hours ago
rlmsrlms
23114
answered 22 hours ago
rlmsrlms
23114
23114
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
rlms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
Chakrapani N Rao is a new contributor. Be nice, and check out our Code of Conduct.
Chakrapani N Rao is a new contributor. Be nice, and check out our Code of Conduct.
Chakrapani N Rao is a new contributor. Be nice, and check out our Code of Conduct.
Chakrapani N Rao is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105618%2fif-i-can-solve-sudoku-can-i-solve-the-travelling-salesman-problem-tsp-if-so%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
6
$begingroup$
Nowhere on this page (in the question or either answer or comments) is "TSP" defined. Especially since this question is now on the Hot Network Questions list, a definition for outsiders would be a very nice addition.
$endgroup$
– Wildcard
yesterday
$begingroup$
@Wildcard done.
$endgroup$
– Chakrapani N Rao
yesterday
11
$begingroup$
@Wildcard Within computer science, it's so widely understood that TSP means "travelling salesman problem" that asking somebody to expand the abbreviation it is a bit like asking them to define "PC" on Super User. Sure, adding the definition doesn't hurt, but somebody who doesn't know the definition probably isn't going to get anything out of the question, anyway.
$endgroup$
– David Richerby
23 hours ago
4
$begingroup$
@DavidRicherby, I am quite familiar with the traveling salesman problem but have never encountered it by that acronym. Perhaps a better analogy than "PC" would be "IE." There are plenty of Windows users who use Internet Explorer who may never have encountered that acronym.
$endgroup$
– Wildcard
22 hours ago
5
$begingroup$
@DavidRicherby Just because someone isn't familiar with an acronym doesn't mean that they wouldn't get anything out of the question. And having it spelled out in the title helps searching.
$endgroup$
– Acccumulation
21 hours ago