Jeśli mogę rozwiązać Sudoku, czy mogę rozwiązać problem Traveling Salesman (TSP)? Jeśli tak to jak?

Powiedzmy, że istnieje program taki, że jeśli podasz częściowo wypełnione Sudoku o dowolnym rozmiarze, otrzymasz odpowiednie wypełnione Sudoku.

Czy możesz potraktować ten program jako czarną skrzynkę i użyć go do rozwiązania TSP? Mam na myśli, czy istnieje sposób na przedstawienie problemu TSP jako częściowo wypełnionego Sudoku, więc jeśli dam ci odpowiedź na to Sudoku, możesz podać rozwiązanie TSP w czasie wielomianowym?

Jeśli tak to jak? jak reprezentujesz TSP jako częściowo wypełnione Sudoku i interpretujesz odpowiadające wypełnione Sudoku dla wyniku.

algorithms np-complete reductions traveling-salesman sudoku Chakrapani N Rao
źródło

Ten dokument roszczenia dać konstruktywną redukcji z Sudoku do Hamiltona problemu cyklu: sciencedirect.com/science/article/pii/S097286001630038X

cwindolf

@ C.Windolf Pytanie dotyczy innego kierunku. (Rzeczywiście istnieje usunięta odpowiedź, która popełniła ten sam błąd i zacytowała ten sam artykuł.)

David Richerby

Odpowiedzi:

W przypadku Sudoku 9x9, nie. Jest skończony, więc można go rozwiązać w czasie . $O(1)$

Ale jeśli miałeś solver dla Sudoku , który działał dla wszystkich i wszystkich możliwych tablic częściowych i działał w czasie wielomianowym, to tak, można go użyć do rozwiązania TSP w czasie wielomianowym, jako ukończenie a Sudoku jest NP-kompletne. $n^2 \times n^2$ $n$ $n^2 \times n^2$

Dowód kompletności NP działa poprzez zredukowanie problemu NP-zupełnego R do Sudoku; następnie ponieważ R jest NP-kompletny, możesz zmniejszyć z TSP do R (wynika z definicji kompletności NP); a łączenie tych obniżek umożliwia wykorzystanie solwera Sudoku do rozwiązania TSP.

DW
źródło

Czy mógłbyś wyjaśnić jak? Tak, załóżmy, że mam ogólny solver sudoku, który działa jak czarna skrzynka. Jak więc możesz tego użyć? Jak reprezentujesz TSP jako częściowo wypełnione Sudoku

Chakrapani N Rao

@ChakrapaniNRao, patrz zaktualizowana odpowiedź. Tak, rozumiem, że to czarna skrzynka. Aby wypracować szczegóły, znajdź dowód kompletności NP dla Sudoku i dowiedz się, jak działa redukcja.

@ChakrapaniNRao To nie odpowiada całkowicie na pytanie, ale pełna odpowiedź byłaby absurdalnie długa, pełna skomplikowanych szczegółów i nie dałaby ci więcej oświecenia niż szkic tutaj. Możliwe, że redukcja jakiegoś problemu z uzupełnieniem NP do sudoku może być interesująca, ale, chyba że dowód na to, że sudoku jest NP- ukończony, był w rzeczywistości przez redukcję z TSP (mało prawdopodobne), odpowiedź wciąż będzie zakończyć „a następnie połączyć te dwie redukcje razem”.

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

$n^2\times n^2$

David Richerby

@ChakrapaniNRao Pytasz, jak rozwiązać problem X za pomocą czarnej skrzynki dla problemu Y. To dosłownie prośba o zmniejszenie. To właśnie oznacza „redukcja”. Jak wyjaśnia ta odpowiedź, odpowiedź na twoje pytanie tak / nie brzmi „tak”.

David Richerby

@ SolomonUcko, cóż, nie, niekoniecznie. Pytanie brzmi: jeśli mamy solver Sudoku, czy możemy go użyć do rozwiązania TSP? Odpowiedź brzmi: tak, możemy. Wyjaśniam jak. To da ci sposób rozwiązania TSP tak szybko, jak solver Sudoku rozwiąże Sudoku. Jeśli solver Sudoku działa w czasie wielomianowym, da ci to sposób rozwiązania TSP w czasie wielomianowym. Jeśli solver Sudoku działa w podwykładniczym czasie, da ci to sposób rozwiązania TSP w podwykładniczym czasie. I tak dalej.

Rzeczywiście możliwe jest użycie ogólnego solvera Sudoku do rozwiązywania instancji TSP, a jeśli ten solver zajmuje czas wielomianowy, wówczas również cały proces (w terminologii złożoności występuje redukcja czasu wielomianowego z TSP do Sudoku). Wynika to z faktu, że Sudoku jest NP-kompletne, a TSP jest w NP. Ale jak to zwykle bywa w tej dziedzinie, patrzenie na szczegóły redukcji nie jest szczególnie pouczające. Jeśli chcesz, możesz go poskładać, używając prostej redukcji z uzupełnienia kwadratu łacińskiego do Sudoku tutaj , redukcji z triangulacji jednolitych trójstronnych wykresów do uzupełnienia kwadratu łacińskiego tutaj , zmniejszenia z 3SAT do triangulacji tutajoraz sformułowanie TSP jako problemu 3SAT. Jeśli jednak chcesz zrozumieć pomysł przejścia z Sudoku do TSP, myślę, że lepiej byłoby przestudiować twierdzenie Cooka (pokazujące, że SAT jest NP-kompletny) i kilka prostych redukcji z 3SAT (np. Do dopasowania trójwymiarowego) i będąc zadowolonym ze świadomości, że redukcja TSP-Sudoku jest po prostu tym samym, ale dłuższym i bardziej niespokojnym.

rlms
źródło