Introduction
Complexity
The Art-Gallery
The Proofs
Conclusions
References
Complexity: What are P and NP?
The Problems
In the field of complexity theory, there is a monolothic question that has baffled computer scientists for some time now. The question is whether or not P = NP? In fact, an answer to that question will get you a million dollars from the Clay Mathematics Institute. The following is a simplified introduction to complexity theory and the study of complexity classes. It is not strongly rigorous, so that any mathematically literate person can understand it. As a result, there are subtleties that are glazed over. For a more mathematical treatment, see "Computers and Intractability" by Garey and Johnson. Still, this may prove somewhat confusing and the rest of the tutorial does not rely on strong knowledge of that which is contained below.
When dealing with problems and their complexity, often, it is better to view the problem as a language and use what we call a Turing machine to help us gauge the problem's complexity. The Turing machine's structure is computationaly equivalent to our modern computers and so, the complexity questions answered theoretically are actually useful in the real world.
Aside: As is the way in the field of complexity theory, all the problems we will deal with are decision problems (i.e. those that can be answered with a 'yes' or 'no').
When a problem is defined, the problem is actually a set of instances of that problem. For example, in the problem of deciding whether all the numbers in a set are even, {1, 2, 3, 7} and {2, 16, 648, 20, 0} could be considered instances. The instances are similar in that they are only different occurences of the same problem. From an abstract standpoint, they are not fundamentally different problems. When dealing with decision problems, as we are, each instance is either one that is a 'yes' or one that is a 'no' (in the above example, the first set is a 'no' and the second set is a 'yes').
Next, we assume that we can encode these problems in a reasonable manner. By 'reasonable', we mean concise and expressible in binary. The latter consideration could be any base conversion greater than 1. The reason for this is to ensure that larger numbers can be expressed concisely. So, for a given problem and an encoding, we get a set of strings representing the instances of the original problem. That set of strings will be the language we want to recognize.
Basically: So, if anything, we know that we can express any problem as a decision problem. We can then turn that problem into a language. Now, all we have to do is accept the words that belong to that language if they were 'yes' instances of the original problem.
The Classes
Definition 1: P is the set of all languages, L, such that there exists a deterministic Turing machine, M, that accepts all 'yes' instances of L where M runs in polynomial time.
'P' which stands for 'polynomial time' will represent the set of problems that can be computed quickly. We are taught quite early on in computer science that fast algorithms are linear or quadratic. It seems strange that some general polynomial would be considered 'fast'. To address that, consider the fact that if NP is not contained in P, the best we can do for many problems will be exponential time; this would be unpleasant.
Definition 2: NP is the set of all languages, L, such that there exists a non-deterministic Turing machine, M, such that M can accept every instance of L in polynomial time.
'NP' which stands for 'non-deterministic polynomial time' and NOT 'non-polynomial time' is the set of languages where every instance of a language can be computed quickly. More often, this is better expressed by saying that a solution to the problem can be verified in polynomial time.
Basically: We have the pictures below:
The picture on the left is definetely correct. The one on the right may or may not be correct, if it is though, it is much more accurate. For now, we'll assume the picture on the left.