Complexity Theory
Introduction
Complexity theory is a central part of computer science and information theory that deals with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).
Computational Complexity Theory
Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is said to be 'solvable' if there exists an algorithm that can solve the problem.
Classes of Problems
In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a problem-solving algorithm. For example, consider the problem of primality testing. The problem is abstract and general. An instance of this problem is a number like 15, which can be plugged into the primality testing algorithm.
Problems can be categorized into classes. These classes are sets of problems which can be solved by the same type of computational resource. The two most commonly used classes are P and NP.
Class P
Class P is the set of problems that can be solved in polynomial time, that is, for which an algorithm exists that can find a solution in polynomial time. Polynomial time is defined by the equation O(n^k), where n is the size of the input and k is a constant.
Class NP
Class NP is the set of problems for which a solution can be verified in polynomial time. This means that if we are given a 'certificate', or a solution to the problem, we can check that the solution is correct in polynomial time. However, it is not known whether a solution can be found in polynomial time.
P vs NP Problem
The P vs NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly checked by a computer can also be quickly solved by a computer. It was first introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" and is considered as one of the seven "Millennium Prize Problems" for which the Clay Mathematics Institute offers a $1,000,000 prize for a correct solution.
Other Complexity Classes
There are many other complexity classes of interest in complexity theory, beyond P and NP. These include the class of problems that can be solved in polynomial time on a quantum computer (BQP), the class of problems that can be solved in polynomial time on a probabilistic Turing machine (BPP), and the class of problems that can be solved in polynomial time on a non-deterministic Turing machine (NP), among others.
Applications of Complexity Theory
Complexity theory has a wide range of applications in computer science, from data structures and algorithms to machine learning and cryptography. It is used to determine what can be computed, how efficiently it can be computed, and what cannot be computed at all.
