Posted 22 October 2012

Maths

Hard problems at OR54

At OR54, this year’s annual conference held 4-6 September in Edinburgh, NP hard problems were very much in evidence.  One of the papers was given by Guido Diepen who has used a constraint programming approach to the problem which is apparently particularly good at solving Sudoku type problems. 

A problem is classified as “P” (or P-hard) if it can be solved quickly.  There is another group which have the property that if one is given the solution then one can quickly verify that the answer is true or false.  This group is known as “NP” (or NP-hard).  Note, if one can solve a problem quickly then one can verify the solution quickly so a P-hard problem is also an NP-hard problem.  The literary million dollar question is whether the reverse is true; can all problems whose solutions can be verified quickly also be solved quickly?  The Cray Foundation offered one million dollars in 2000 to the first person to prove this one way or the other – so far there have been no takers.  There is a third category called NP-complete – these are the key to “life, the universe and everything”.

Not only does Guido Diepen’s solution solve problems quickly, provided there is a feasible solution, it does so in a way which makes it relatively easy for the user to describe in terms of the constraints.  An example is that one can simply state that all values in row j have to be different (for rows j = 1, 9) similarly for columns and for the 3x3 boxes.  These constraints require quite of a lot of coding to achieve the same in a linear or integer programming model.  Although this approach greatly simplifies the problem in terms of setting up the constraints, it still uses a heuristic approach so does not reduce the problem from NP to P.