>>12456998P= > If you have an input X and want an output Y, then the number of logical steps to solving the problem follows some polynomial:
Example: suppose you want to figure out how many pepperonis will fit on your pizza. You are given the radius of the pizza and the size of the pepperoni. Then you can code in your computer:
f(radius, area of pepperoni) = (pi * radius^2 ) / (area of pepperoni)
Since the most complex operation (the one that requires the most "steps" to solve) is a square, the amount of time it takes for a computer to solve this problem depends on how quickly it can square a number. So the problem is said to be solvable in polynomial time.
NP => If you have an input X and you can VERIFY whether Y is an output in polynomial time then the problem is said to be NP.
Example: I give you an unfinished sudoku grid, and also the finished version. Our input is the size of the sudoku grid and a few numbers and our output is the finished sudoku. In order to verify the solution works you just need to check every square and whether it follows the sudoku rules. This can be done very quickly and easily in polynomial time.
Now obviously all P problems are NP, at worst you can just do the steps backwards and check that it is correct. The question is do ALL NP problems have a way to reduce them to P problems? In other words, if you can check a solution in polynomial time, does that mean it was originally solvable in polynomial time?
Going back to the sudoku grid, as the size of the sudoku grid grows, it requires more and more steps to solve by hand the way you normally would. The number of steps grows so quickly that if you were to solve it the "normal" way there is no way you could solve it in polynomial time. The question is, is there some "trick" or "shortcut" that can reduce the calculations so that at worst all you have to calculate is a square/cube/5th power, etc. of one of your inputs.
