Complexity class of Sudoku

Bonfyre · Posted: Thu Jun 16, 2005 2:15 am Post subject: Complexity class of Sudoku

Browsing through the posts here, I've seen Sudoku referred to as NP, NP-Hard or NP-Complete. Which one is it?

Simes · Posted: Thu Jun 16, 2005 8:46 am Post subject:

According to wikipedia (http://en.wikipedia.org/wiki/Sudoku#Mathematics_of_Sudoku) it's NP Complete.
_________________
Simes
www.sadmansoftware.com/sudoku

scrose · Posted: Thu Jun 16, 2005 5:37 pm Post subject:

Here is a proof of NP-completeness.

dukuso · Posted: Thu Jul 14, 2005 8:39 am Post subject:

puffinry · Posted: Tue Aug 09, 2005 12:34 pm Post subject:

It's mildly misleading to say "Sudoku is NP-complete". There is an NP-complete problem related to Sudoku: given a partially completed grid, determine whether it has a solution. But this is a problem that faces the setter, rather than the solver.

The problem faced by the solver is: given a partially completed grid which has a unique completion, find the completion. That's not a decision problem, so it doesn't even make sense to ask whether it's NP-hard or whatever.

Most of computational complexity theory focusses on decision problems. It's often argued (e.g. here) that the restriction is inessential, since you can turn any problem into a decision problem by supplying a purported solution and asking whether or not it's correct. If you do that to Sudoku, the resulting problem is in P.

(This example shows that converting a problem into a decision problem can change its character in an essential way, hence that this particular justification for focussing on decision problems is rather dubious.)[/url][/i]

puffinry · Posted: Fri Aug 12, 2005 10:43 pm Post subject:

I emailed Lance Fortnow about this, and he posted the question and answer on his weblog, here.

dukuso · Posted: Fri Aug 12, 2005 11:37 pm Post subject:

I see no difference here.
Knowing that there is a solution doesn't really help,
you have to work through the whole searchspace anyway.

You could make a decision problem by asking:
in the solution, does cell xy contain symbol s ?

The corresponding problem for latin squares is
called "quasigroup with holes"-problem (QWH).
Although, there you are simply given, that there is a solution,
not that it is unique.

Guenter.