Wenn ich Sudoku lösen kann, kann ich das Travelling Salesman Problem (TSP) lösen? Wenn das so ist, wie?

Nehmen wir an, es gibt ein Programm, bei dem Sie, wenn Sie ein teilweise gefülltes Sudoku einer beliebigen Größe geben, das entsprechende fertige Sudoku erhalten.

Können Sie dieses Programm als Black Box behandeln und damit TSP lösen? Ich meine, gibt es eine Möglichkeit, das TSP-Problem als teilweise gefülltes Sudoku darzustellen, sodass Sie, wenn ich Ihnen die Antwort auf dieses Sudoku gebe, die Lösung für TSP in polynomialer Zeit ermitteln können?

Wenn ja, wie? Wie wird TSP als teilweise gefülltes Sudoku dargestellt und das entsprechende gefüllte Sudoku für das Ergebnis interpretiert?

algorithms np-complete reductions traveling-salesman sudoku Chakrapani N Rao
quelle

In diesem

Artikel wird

@ C.Windolf Die Frage fragt nach der anderen Richtung. (In der Tat gibt es eine gelöschte Antwort, die den gleichen Fehler gemacht und das gleiche Papier zitiert hat.)

David Richerby

Antworten:

Für 9x9 Sudoku, nein. Es ist endlich und kann in $O(1)$ gelöst werden.

Aber wenn Sie einen Löser für $n^2 \times n^2$ Sudoku hatten, der für alle $n$ und alle möglichen Teilkarten funktionierte und in Polynomzeit lief, dann könnte dies verwendet werden, um TSP in Polynomzeit zu lösen, indem ein $n^2 \times n^2$ vervollständigt wird Sudoku ist NP-vollständig.

Der Beweis der NP-Vollständigkeit funktioniert durch Reduzieren von einem NP-vollständigen Problem R auf Sudoku; dann können Sie, weil R NP-vollständig ist, von TSP auf R reduzieren (was sich aus der Definition der NP-Vollständigkeit ergibt); Wenn Sie diese Reduzierungen verketten, können Sie den Sudoku-Löser verwenden, um TSP zu lösen.

DW
quelle

Könnten Sie bitte erklären, wie? Ja, nehmen wir an, ich habe einen allgemeinen Sudoku-Löser, der als Black Box fungiert. Wie können Sie es verwenden? Wie vertritt man TSP als teilweise gefülltes Sudoku

Chakrapani N Rao

@ChakrapaniNRao, siehe aktualisierte Antwort. Ja, ich verstehe, es ist eine Blackbox. Um die Details herauszufinden, suchen Sie den Nachweis der NP-Vollständigkeit für Sudoku und verstehen Sie, wie die Reduzierung funktioniert.

n^{2} \times n^{2}

$n^2\times n^2$

@ChakrapaniNRao Sie fragen, wie Sie Problem X mit einer Blackbox für Problem Y lösen können. Das ist buchstäblich eine Reduzierung. Das ist, was "Reduktion" bedeutet. Und wie diese Antwort erklärt, lautet die Antwort auf Ihre Ja / Nein-Frage Ja.

David Richerby

@SolomonUcko, na ja, nein, nicht unbedingt. Die Frage lautet: Wenn wir einen Sudoku-Löser haben, können wir ihn zur Lösung von TSP verwenden? Die Antwort lautet: Ja, wir können. Ich erkläre wie. Auf diese Weise können Sie TSP ungefähr so schnell lösen, wie der Sudoku-Löser Sudoku löst. Wenn der Sudoku-Löser in Polynomialzeit ausgeführt wird, können Sie TSP in Polynomialzeit lösen. Wenn der Sudoku-Löser in subexponentieller Zeit ausgeführt wird, haben Sie die Möglichkeit, TSP in subexponentieller Zeit zu lösen. Und so weiter.

Es ist in der Tat möglich, einen allgemeinen Sudoku-Löser zum Lösen von TSP-Instanzen zu verwenden. Wenn dieser Löser Polynomzeit benötigt, wird auch der gesamte Prozess ausgeführt (in der Komplexitätsterminologie wird die Polynomzeit von TSP auf Sudoku reduziert). Dies liegt daran, dass Sudoku NP-vollständig ist und TSP in NP ist. Aber wie es in diesem Bereich normalerweise der Fall ist, ist es nicht besonders aufschlussreich, die Details der Reduzierung zu betrachten. Wenn Sie möchten, können Sie es zusammensetzen, indem die einfache Reduktion von lateinisches Quadrat Abschluss zu Sudoku mit hier , die Reduktion von Triangulation einheitliche tripartite Graphen lateinisches Quadrat Abschluss hier , die Reduktion von 3SAT auf Triangulation hierund eine Formulierung von TSP als 3SAT-Problem. Wenn Sie jedoch die Idee hinter der Reduktion von Sudoku auf TSP verstehen möchten, sollten Sie Cooks Theorem (das zeigt, dass SAT NP-vollständig ist) und einige einfache Reduktionen von 3SAT (z. B. auf 3-dimensionales Matching) studieren. und mit dem Wissen zufrieden zu sein, dass die TSP-Sudoku-Reduzierung genauso ist, aber länger und fummeliger.

rlms
quelle