Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A P vs NP Guessing and process of elimination

Tags:
  1. Jun 1, 2017 #1
    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!
     
  2. jcsd
  3. Jun 1, 2017 #2

    jedishrfu

    Staff: Mentor

    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
     
  4. Jun 1, 2017 #3
    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.
     
  5. Jun 1, 2017 #4
    Thank you for your reply (and sorry for my lack of vocabulary - English is not my first language)
     
  6. Jun 1, 2017 #5

    fresh_42

    Staff: Mentor

    ##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 travelling 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.
     
  7. Jun 1, 2017 #6

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Are you referring to "proper puzzles" , i.e., those having a unique solution, or to general ones?
     
  8. Jun 1, 2017 #7
    Those with just one solution.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: P vs NP Guessing and process of elimination
  1. P vs NP and factoring (Replies: 3)

  2. NP = P and P (3-SAT) (Replies: 9)

Loading...