Investigating P vs. NP and its effects
Mete Iyiguyn
My sister loves to solve jigsaw puzzles. Mixing and matching hundreds or even thousands of pieces together to form an image. It seems like a trivial task really, even kids enjoy them. But, if you were to give someone a bag of jigsaw pieces and ask them then and there whether it was solvable, then the problem goes from trivial to extremely difficult. In fact, how to solve a jigsaw puzzle gives rise to one of the most difficult problems in computer science. There is a type of problems I will class as A. Problems in A are easy to solve and easy to verify. In this class we have problems, such as checking two numbers, greatest common denominators (GCD) and checking if a number is prime. On the other hand, we have problems which may or may not be easy to solve, but which are easy to verify if a solution is correct, like our jigsaw puzzle. For now, these problems with unknown difficulty we class as B. Let’s go back to our jigsaw example. If I claimed I had solved a jigsaw puzzle , it would be pretty easy for you to verify if I were telling the truth. All you would have to do is go through each puzzle piece and make sure that it is properly connected to its neighbours. But if I gave you a bag of pieces and asked you whether it is possible to use all of the pieces to create a complete puzzle, it would be difficult to figure out if this jigsaw puzzle is even solvable. One possible solution, although very long, is to try all possibilities and say it is not solvable if no configuration produces a complete picture. This solution takes an enormous amount of time. This is where our problem comes from. Let us put our jigsaw example aside for now. Imagine I give you an n x n square where n is any positive integer. Now if it takes you A seconds to count one 1 x 1 square, then it should take you An seconds to count one side of the square, and An 2 seconds to count how many 1 x 1 squares are in the n x n square. So, for a square of side n, it takes you An 2 seconds to count how many 1 x 1 squares are in the larger square. Big O notation is a method to convey this. In Big O notation one would say for a square with side n, the time complexity to count the 1 x 1 squares is O(n 2 ). In Big O any constants like A are removed. Other areas where Big O appears is in sorting algorithms. Say you want to sort a set of data S in ascending order. Using the simplest algorithm, the bubble sort, you check each element in S in order and, if it is larger than the next element, you switch them around, and so on. This algorithm has a worst- case time complexity of O(n 2 ), namely, polynomial time complexity. This means that for some k,C > 0, its running time on inputs of size n is at most Cn k , or equivalently, O(n k ). 1 Any task done in polynomial time complexity adheres to this principle. Back to our jigsaw example. The method described earlier to find a working solution for the jigsaw by checking all possibilities is very long. This task has time complexity of O(4 n ·n!) where n! is the product of all positive integers up to and including n. Note how this task does not have polynomial time complexity. One might think: is there any faster way? The problem is: we don’t know. If you remember
1 Aaronson, S. (n.d.). P ? = NP . [online] . Available at: https://www.scottaaronson.com/papers/pnp.pdf.
157
Made with FlippingBook interactive PDF creator