Computational Complexity Theory

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
From: claymath.org

The Clay Mathematics Institute announced in the year 2000 that they would pay a $1,000,000 USD prize for the first person to prove a solution.

Computational complexity theory describes the difficulty in providing answers to specific computational problems. That is, the theory answers the question, "As the size of the problem increases, how does the running time and memory requirements to solve the problem change?" The theory places practical limits on what computers can accomplish.

Complexity classes

A complexity class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource (time, memory, etc).

Vocab: A computer is deterministic if that, given the computer's present state and any inputs, there is only one possible action that the computer might take (in sequential steps), then it performs those actions one after the other. Non-deterministic computational models allow the computer to branch out to check many different possibilities at once.

The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an idea of the problems which can be effectively solved in the worst cases.

So if we have a problem (question), Q, and the time it takes to solve the problem is proportional to the length of the problem, N, then it is said that the answer can be found in polynomial time. The time (or the number steps ) to solve any Q is: t(Q)=R(times)N^K, where R and K are positive constants.

The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. This class contains many problems that people would like to be able to solve effectively. All the problems in this class have the property that their solutions can be checked effectively.

Now suppose there is an algorithm A(w,C) which takes two arguments, a string w which is an input string to our decision (yes/no) problem, and a string C which is a "proposed certificate/answer", and such that A produces a YES/NO answer in at most c(n^k) steps (where n is the length of w and neither c nor k depend on w). Suppose furthermore that: w is a YES instance of the decision problem if and only if there exists C such that A(w,C) returns YES. Then we say that the problem can be solved in non-deterministic polynomial time and we place it in the class NP. We think of the algorithm A as a verifier of proposed certificates which runs reasonably fast. (Note that the abbreviation NP stands for "Non-deterministic Polynomial" and not for "Non-Polynomial".)

Now, c(n^k) is the time to check a proposed answer, but the time it takes to find the answer may be "exponential time:" c(k^BN) where c, k, B are constants

Consequences of proof

The question is whether every problem that is hard (Hard means that the time to solve the problem rises exponentially to the length of the problem, but it is fast to check to see if a solution is correct.) to find a solution for can be reduced through crazy, magical, and advance mathematics so that the time to solve the original problem is easy (Easy as in the time to solve the problem rises according to a power function of the length of the problem: can every hard problem be shown to be easy? Does P=NP ?

Restating the above: the question of whether NP is the same set as P (that is whether problems that can be solved in non-deterministic polynomial time can be solved in deterministic polynomial time) is one of the most important open questions in theoretical computer science due to the wide implications a solution would present. One negative impact is that many forms of cryptography, would become easy to "crack" and would therefore be useless. However, there are also enormous positive consequences that would follow - as many important problems would be shown to have efficient solutions. These include various types of programming, protein structure prediction in biology, and very importantly even in pure mathematics where it would mean that it would be possible to find formal proofs of theorems efficiently using computers.

Computational Complexity Theory

P versus NP

Abstract: P vs NP Problem