A Turing machine M is said to operate within time f n , if the time required by M on each input of length n is at most f n. A decision problem A can be solved in time f n if there exists a Turing machine operating in time f n that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f n on a deterministic Turing machine is then denoted by DTIME f n.
Analogous definitions can be made for space requirements.
- Particle Physics Experiments at High Energy Colliders.
Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory include communication complexity , circuit complexity , and decision tree complexity. The complexity of an algorithm is often expressed using big O notation. The best, worst and average case complexity refer to three different ways of measuring the time complexity or any other complexity measure of different inputs of the same size.
Since some inputs of size n may be faster to solve than others, we define the following complexities:. The order from cheap to costly is: Best, average of discrete uniform distribution , amortized, worst. For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the input is sorted or sorted in reverse order, and the algorithm takes time O n 2 for this case.
If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O n log n. The best case occurs when each pivoting divides the list in half, also needing O n log n time. To classify the computation time or similar resources, such as space consumption , one is interested in proving upper and lower bounds on the maximum amount of time required by the most efficient algorithm solving a given problem.
The complexity of an algorithm is usually taken to be its worst-case complexity, unless specified otherwise. Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound T n on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T n. However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem.
The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of T n for a problem requires showing that no algorithm can have time complexity lower than T n. Upper and lower bounds are usually stated using the big O notation , which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used.
A complexity class is a set of problems of related complexity. Simpler complexity classes are defined by the following factors:. Some complexity classes have complicated definitions that do not fit into this framework. Thus, a typical complexity class has a definition like the following:.
But bounding the computation time above by some concrete function f n often yields complexity classes that depend on the chosen machine model. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" Goldreich , Chapter 1.
This forms the basis for the complexity class P , which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP. Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:. The logarithmic-space classes necessarily do not take into account the space needed to represent the problem.
P is an important complexity class of counting problems not decision problems. ALL is the class of all decision problems. For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on say computation time indeed defines a bigger set of problems.
For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other.
Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved. More precisely, the time hierarchy theorem states that. The space hierarchy theorem states that. The time and space hierarchy theorems form the basis for most separation results of complexity classes. Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at most as difficult as another problem.
CMSC 652 --- Complexity Theory
For instance, if a problem X can be solved using an algorithm for Y , X is no more difficult than Y , and we say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions. The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time.
For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X , since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used.
SIGACT news complexity theory column 80 - Semantic Scholar
For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems. This means that X is the hardest problem in C. Since many problems could be equally hard, one might say that X is one of the hardest problems in C. Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm.
This hypothesis is called the Cobham—Edmonds thesis. The complexity class NP , on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem , the Hamiltonian path problem and the vertex cover problem. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.
The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution. These include various types of integer programming problems in operations research , many problems in logistics , protein structure prediction in biology ,  and the ability to find formal proofs of pure mathematics theorems. The graph isomorphism problem , the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
Introduction to Complexity
An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P , NP-complete , or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. The integer factorization problem is the computational problem of determining the prime factorization of a given integer.
Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. If the problem is NP-complete , the polynomial time hierarchy will collapse to its first level i. However, the best known quantum algorithm for this problem, Shor's algorithm , does run in polynomial time.
Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.
Many known complexity classes are suspected to be unequal, but this has not been proved. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.
Along the same lines, co-NP is the class containing the complement problems i. It is believed  that NP is not equal to co-NP ; however, it has not yet been proven. Similarly, it is not known if L the set of all problems that can be solved in logarithmic space is strictly contained in P or equal to P. Again, there are many complexity classes between the two, such as NL and NC , and it is not known if they are distinct or equal classes.