# On Philosophy

## December 8, 2007

### P=NP

Filed under: Epistemology — Peter @ 12:00 am

Obviously solving some problems takes longer than others, for example you can’t put a list of 10 items in order as fast as you can put a list of 2 items in order, simply because you have to look at more items in first case to put it in order. But problems can take different lengths of time for reasons beside the fact that they are dealing with different sized inputs. Some problems might be able to be solved within a time strictly proportional to the size the input, while others might take time proportional to the square or the cube of the size of the input. This kind of difference is called a difference in the computational complexity of the problem. Computational complexity covers a great deal of territory, but one famous unsolved problem within it is whether a certain class of hard to solve problems, designated NP, can be reduced to faster to solve problems, designated by P. NP problems are characterized by the fact that the fastest known solutions to them take time proportional to an exponential function, say 2n. Often this comes about because there are an exponential number of possible solutions, and, while a solution can be checked for correctness relatively quickly, there is no easy way to narrow in on the correct solution. Thus even the best algorithms for solving the problem essentially reduce to trying one solution after another until a correct answer is found or all the possibilities are exhausted. If we could reduce NP problems to P problems that it would entail that we would have a way to solve these problems in polynomial time (time proportional to some polynomial function of the input), meaning that we aren’t going through the possible solutions one after another in sequence.