View previous topic :: View next topic |
Author |
Message |
| Bonfyre
| Joined: 16 Jun 2005 | Posts: 1 | : | | Items |
|
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? |
|
Back to top |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
|
Back to top |
|
|
| scrose
| Joined: 01 Jun 2005 | Posts: 23 | : | | Items |
|
Posted: Thu Jun 16, 2005 5:37 pm Post subject: |
|
|
Here is a proof of NP-completeness. |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Jul 14, 2005 8:39 am Post subject: |
|
|
scrose wrote: | Here is a proof of NP-completeness. |
thanks ! |
|
Back to top |
|
|
| puffinry
| Joined: 09 Aug 2005 | Posts: 4 | : | Location: London | Items |
|
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] |
|
Back to top |
|
|
| puffinry
| Joined: 09 Aug 2005 | Posts: 4 | : | Location: London | Items |
|
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. |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
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. |
|
Back to top |
|
|
|