Complexity Theory
Complexity theory is the study of how hard problems are to solve. It allows mathematicians to classify problems in terms of how difficult they are, because some problems are intrinsically harder than others.
How intrinsically difficult a problem is can be measured using "Big-O notation," which denotes the average requirements of the algorithm to solve the problem in terms of running time or computer memory usage, as a function of the size of the input. Algorithms are often described--in order of intrinsic complexity or difficulty--as having "constant," "n log n," "linear," "logarithmic," "polynomial," "exponential," or "factorial" complexity. For example, multiplication has polynomial complexity, denoted O(n2); solving crosswords has exponential complexity, O(26n). Big-O notation classifies problems by their "size," which for numerical problems is usually the number of digits or bits.
An "instance" of a problem is a particular case of a general problem. Sometimes it is the case that the algorithm used to solve a particular instance of a complex problem is not necessarily applicable as a solution to the general problem.
A polynomial-time algorithm, said to be "of class P," or just P, is one that solves any instance of a given problem in time O(p(n)), where p is a polynomial of the input length. A polynomial is a mathematical expression comprising a sum of terms in which each term includes a variable raised to a power and multiplied by a constant. The highest exponent in the polynomial is called the "order" or degree" of the polynomial
An exponential-time algorithm, or "class E," is one that has a solution time determined by the size of the input raised to a constant power, or O(nk), where n is the size of the input and k is a constant.
A non-deterministic polynomial-time algorithm, denoted by "class NP," is one for which any guess at the solution of an instance of the problem may be checked for validity in polynomial time. In other words, the problem has only an exponential (or even more complex) solution, but the algorithm to check if a purported solution is correct or not is an algorithm of class P.
NP-Complete problems are a subclass of NP problems. It is known that if any NP-Complete problem has a solution of complexity P, then all NP problems have polynomial solutions. These are thus the hardest NP problems. It is not known if NP=NP-Complete. In other words, it is not known if all NP problems are also NP-Complete problems. It is also not known if NP=P, but most mathematicians think that it is not.
Another complexity class is "class Co-NP." This class is similar to NP but has the added difficulty of having checking algorithms that are also not of class P. It is possible that to check a claimed solution to a Co-NP problem could require an exhaustive search of all possible solutions.
Complexity theory is inextricably entwined with modern communications and computers. This is because complexity theory is fundamental to "cryptography," the science of keeping data away from the eyes of people who are not authorized to see it. A cryptographic algorithm is used to transform data from its normal form to its encrypted form under the control of a key. The mathematical properties of a strong cryptographic algorithm make performing the transformation without the key very difficult, even if the details of how the algorithm works are common knowledge. Put another way: encryption and decryption must be must be easy when you know the key, but hard when you do not.
This means that by definition cryptography is an NP-class problem, because it is easy to check the answer when the key is known but very hard when it is not. Several cryptographic algorithms are known to be NP-Complete, which means if one of these algorithms is solved by an attacker, then all the NP-Complete algorithms are solved. And that, of course, would have grave consequences for data security.
This is the complete article, containing 644 words
(approx. 2 pages at 300 words per page).
