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, NPHard or NPComplete. 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 NPcompleteness. 

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 NPcompleteness. 
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 NPcomplete". There is an NPcomplete 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 NPhard 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 


