Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other. A computational problem is understood to be a task that is in principle amenable to being solved by a computer, which is equivalent to stating that the problem may be solved by mechanical application of mathematical steps, such as an algorithm.

Definition

Computational complexity theory is all about scaling. More specifically, it is about how the resource requirements of a problem scale, measured as a function of the size of the input to the problem, using big O notation. The resources could be anything from the time taken to the space used, or even the amount of parallelism required. The theory formalizes this into the notion of complexity classes, sets of the computational problems that can be solved using a certain amount of resources, and often, the 'class' part of 'complexity class' is taken quite literally, with complexity classes being arranged into a hierarchy.

Complexity Classes

The most well-known complexity classes are P and NP. The class P consists of those problems that are solvable in polynomial time, i.e., the time required grows polynomially with the size of the input. The class NP consists of problems whose solutions can be verified in polynomial time. A major unsolved question in computer science is the P vs NP problem, which asks whether every problem whose solution can be quickly checked can also be quickly solved.

P vs NP Problem

The P vs NP problem is one of the seven "Millennium Prize Problems" for which the Clay Mathematics Institute offers a $1,000,000 prize for a correct solution. The informal term quickly used above means the existence of an algorithm for the task that runs in polynomial time. The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be checked in polynomial time is called NP.

Applications

Computational complexity theory has far-reaching applications in artificial intelligence, algorithmic design, network computing, cryptography, and various other fields within computer science.

See Also

• Algorithmic complexity
• Big O notation
• Turing machine
• Decision problem
• NP-complete
• NP-hard

{{{1}}} Template:Theoretical computer science-stub