Non-deterministic Polynomial Time Decidable Problem – Intro to Algorithms

Non-deterministic Polynomial Time Decidable Problem – Intro to Algorithms

Articles, Blog , , , , , , , , 1 Comment


Formerly the class NP is the set of non-deterministic polynomial time decidable problems– that is to say that it’s a problem that can be dissolved by a program that runs in polynomial time that has non-deterministic elements in it. Now, I’m going to explain what that is in just a moment, but first what I’d like to do is give you a handle on intuitively what this means. I’d like to say the NP stands for nice puzzle problems, so let me explain what I mean by that. Think of a problem like solving a Sudoku problem. You might phrase this as a decision problem by saying here is a grid, can this be filled in to complete the Sudoku problem. It has to satisfy that if you don’t know this is a very popular newspaper puzzle that involves– you’re given a bunch of numbers in a 9×9 grid and you have to fill in more numbers, you have to fill in all the grid cells and ultimately, the solution that you fill in has to have the property that every row in every column has the number 1 through 9 and each block into these dark blocks also has the numbers 1 through 9. So I can give you a Sudoku like this and it could be very, very challenging to know whether or not this can be completed to satisfy the Sudoku constraints, but the next day in the newspaper or if it’s a puzzle magazine, may be at the back of the puzzle magazine. It’s very easy to convince you if the answer is yes, so if the answer is yes, then i can prove it you by simply giving you a small what’s called accepting certificate, which in this case just means a filled in Sudoku board. So if I filled in Sudoku board, you can very quickly do two things–check to see if it’s correct, if all the rows and columns have the number 1 through 9– that’s a polynomial time decision problem that you can write very easily, and also check if the cells that you’re given match what was given in the original puzzle and that also is a very fast thing to be able to check. All you have to do is run through the cells of the original puzzle and each time there was something that was filled in, check if it matches in the answer. So even though it maybe very difficult to answer the question if you’re given the right kind of information you can check it very fast.

One thought on “Non-deterministic Polynomial Time Decidable Problem – Intro to Algorithms

Leave a Reply

Your email address will not be published. Required fields are marked *