One of the "great" outstanding problems in computer science is the question of P vs NP. In layman's terms, P represents all problems whose solution can be found in polynomial time. NP represents all problems whose solutions can be verified in polynomial time. Polynomial time just means that the time to find the solution has a polynomial relationship with the size of the problem. For instance, a particularly terrible sorting algorithm may take n^2 seconds to sort an arbitrary list of names, where n is the number of names in the list. This is a second-order polynomial of the form a+b*n+c*n^2, where a = b = 0, and c = 1.
The question, does N = NP? asks whether all problems which can be solved in polynomial time, can also be verified in polynomial time. Back to the list sorting example, verifying that a list is indeed sorted properly may only take n seconds, so this is also polynomial. In this single example, the problem was solvable in polynomial time, and its solution was verified in polynomial time.
For further reading, take a look at Wikipedia's entry on this topic. It also addresses the topics of NP-hard and NP-complete.
No comments:
Post a Comment