A P vs NP Guessing and process of elimination

[Anders Serup Poulsen]

If we suppose there is an algorithm for P vs NP, would it have to be able to find solutions where we now use trial and error? In harder Sudokus, for example, there are times when you have two or more possible numbers and need to guess whereafter you work the rest of the numbers through to see if what you guessed is right. There is a distinction between problems where the solution is given by the process of elimination and problems where you have to guess. Does P vs NP concern the former only or also the latter? An answer would be very much appreciated!

 

[jedishrfu]

Its not that you have to guess but rather you must consider possible numbers in multiple blank squares in the sudoku before determining the correct number for the square of interest. This is like selecting a move in chess where you must forecast a few moves ahead to decide if the current move is a good choice.

https://en.wikipedia.org/wiki/Mathematics_of_Sudoku

and this paper describes the general class of sudoku puzzles as NP-complete:

http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf

and a discussion here at Math Stack Exchange:

https://math.stackexchange.com/questions/445540/is-the-sudoku-puzzle-np-complete

 

[Anders Serup Poulsen]

Okay, "guessing" is not the right word then. In a lot of sudokus, you can find the solution by eliminating possible numbers but in the harder ones you get stuck and need to think several steps ahead like you said. Does the P vs NP problem contain both "types"? I feel like the problem gets much more complicated when you need to think steps ahead than when you don't.

From what I understand chess is in a more complex class of problems than sudoku.

 

[Anders Serup Poulsen]

Thank you for your reply (and sorry for my lack of vocabulary - English is not my first language)

 

[fresh_42]

$NP$ means that a guess is possible. $N$ stands for non-deterministic. If I remember correctly, one can model it by a Turing machine with an oracle tape. Important is, that a guessed or whatever achieved solution can be verified in polynomial time $P \subseteq NP$. $NP$ completeness of Sudoku means, that if we had a polynomial time algorithm for any Sudoku riddle, we could also decide all other problems in $NP$ in polynomial time, because there is a polynomial time translation from Sudoku into all other problems, e.g. the traveling salesman problem or the Boolean satisfiability problem. The general question behind $NP=P$, that is $NP \subseteq P$, is, whether there is a way to solve such problems without a guess, or an oracle tape.

 

[WWGD]

If we suppose there is an algorithm for P vs NP, would it have to be able to find solutions where we now use trial and error? In harder Sudokus, for example, there are times when you have two or more possible numbers and need to guess whereafter you work the rest of the numbers through to see if what you guessed is right. There is a distinction between problems where the solution is given by the process of elimination and problems where you have to guess. Does P vs NP concern the former only or also the latter? An answer would be very much appreciated!

Are you referring to "proper puzzles" , i.e., those having a unique solution, or to general ones?

 

[Anders Serup Poulsen]

Those with just one solution.