To animate Maths Week, your teachers are offering one story a day about an aspect of Maths you probably do not know…yet!
Wednesday’s story
Classified Ad
Today “P = NP?”: is finding the solution to a problem necessarily more difficult than checking whether or not a solution is correct?
P = NP ?
Everyone knows Sudoku: Fill a 9-square box with the numbers 1 to 9 in such a way that each number appears only once in each row, each column and in each “sub-square”. I find this game a bit complicated. So, I invented a new one: the unidoku. It’s the same thing but with only one line. It is more at my level…
The unidoku is easy to solve. It is said to be a class P problem. Sudoku is difficult to solve. But if you are given a solution, it is easy to check that this solution is valid. It is said to be a NP class problem.
This classification is due to computer scientist Stephen Cook and actually refers to the computational time required for a computer to find or verify a solution. Cook noticed that the discovery of more efficient algorithms made it possible to reclassify some problems from class NP to class P. He then asked himself: “Do all NP problems admit an algorithm that makes it possible to reclassify it as P? This is the “P=NP?” problem, which is one of the Millennium Prize Problems.
Nobody has yet found the answer to this question. If this answer is “yes”, it would mean that sudoku is in fact not more difficult than unidoku, at least for a computer. Another small detail: cracking the code that protects all passwords on the internet is a NP-class problem…
Let’s continue with a little video (click on the images)
That makes me laugh.
(but I am a Maths teacher…)
