Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Sudoku Revisited

Expand Messages
  • Lance
    Robin Houston writes Although I m not a complexity theorist, I very much enjoy reading your weblog. I also enjoy solving the Sudoku puzzles published in the
    Message 1 of 1 , Aug 11, 2005
    • 0 Attachment
      Robin Houston writes
      Although I'm not a complexity theorist, I very much enjoy reading your weblog. I also enjoy solving the Sudoku puzzles published in the British press, so it was doubly nice to see your May 25 post about the complexity of Sudoku!

      As far as I can tell, it follows from Yato's work that the problem:

      1. Given a partially completed grid, find a valid completion if there is one; otherwise report that there isn't one.

        is solvable in polynomial time iff P=NP.

        That's interesting of course, and it's a problem that faces those who set the puzzles; but the problem that we solvers are faced with is not quite (1). It's:

      2. Given a partially completed grid that has a unique valid completion, find that completion.

      Can anything be said about problem (2)? If there were a polynomial- time algorithm for (2), would it follow that P=NP? If not, would there be any other significant consequences for complexity theory?

      Good question. Since Yato's reductions preserve solutions the problem is equivalent to finding a satisfying assignment of a Boolean formula that has exactly one satisfying assignment (Unique SAT).

      We don't know if Unique SAT is NP-complete in the traditional sense. However Valiant and Vazirani have a nice paper that shows how to randomly reduce SAT to Unique SAT. Putting it together we get the following equivalence:

      • Given a partially completed grid that has a unique valid completion, probabilistically find that completion in polynomial time.
      • NP=RP (i.e. all NP problems have efficient probabilistic solutions).
      Since we don't believe that NP has fast probabilistic algorithms, we expect that there are no efficient procedures to completing a generalized Sudoku grid, even if there is only one such completion.

      --
      Posted by Lance to Computational Complexity at 8/11/2005 07:33:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.