![comparison computational complexity](https://upload.wikimedia.org/wikipedia/commons/7/7e/Comparison_computational_complexity.svg)
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the time complexity is the
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
that describes the amount of computer time it takes to run an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a
constant factor
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
.
Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the
worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the
average-case complexity
In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case comp ...
, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
of the size of the input.
Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the
asymptotic behavior
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as beco ...
of the complexity. Therefore, the time complexity is commonly expressed using
big O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
, typically etc., where is the size in units of
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s needed to represent the input.
Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity
is a ''linear time algorithm'' and an algorithm with time complexity
for some constant
is a ''polynomial time algorithm''.
Table of common time complexities
The following table summarizes some classes of commonly encountered time complexities. In the table, , i.e., polynomial in ''x''.
Constant time
An algorithm is said to be constant time (also written as
time) if the value of
(the complexity of the algorithm) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
takes constant time as only one
operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Ma ...
has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each
element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking
time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.
Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be independent of the problem size. For example, the task "exchange the values of and if necessary so that
" is called constant time even though the time may depend on whether or not it is already true that
. However, there is some constant such that the time required is always ''at most'' .
Here are some examples of code fragments that run in constant time:
int index = 5;
int item = list
ndex
if (condition true) then
perform some operation that runs in constant time
else
perform some other operation that runs in constant time
for i = 1 to 100
for j = 1 to 200
perform some operation that runs in constant time
If
is
, where is any constant value, this is equivalent to and stated in standard notation as
being
.
Logarithmic time
An algorithm is said to take logarithmic time when
. Since
and
are related by a
constant multiplier, and such a
multiplier is irrelevant to big O classification, the standard usage for logarithmic-time algorithms is
regardless of the base of the logarithm appearing in the expression of .
Algorithms taking logarithmic time are commonly found in operations on
binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s or when using
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
.
An
algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size is of the order of .
An example of logarithmic time is given by dictionary search. Consider a
dictionary
A dictionary is a listing of lexemes from the lexicon of one or more specific languages, often arranged alphabetically (or by radical and stroke for ideographic languages), which may include information on definitions, usage, etymologies ...
which contains entries, sorted by
alphabetical order
Alphabetical order is a system whereby character strings are placed in order based on the position of the characters in the conventional ordering of an alphabet. It is one of the methods of collation. In mathematics, a lexicographical order is t ...
. We suppose that, for
, one may access the th entry of the dictionary in a constant time. Let
denote this th entry. Under these hypotheses, the test to see if a word is in the dictionary may be done in logarithmic time: consider
, where
denotes the
floor function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
. If
, then we are done. Else, if
, continue the search in the same way in the left half of the dictionary, otherwise continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary.
Polylogarithmic time
An algorithm is said to run in
polylogarithmic
In mathematics, a polylogarithmic function in is a polynomial in the logarithm of ,
: a_k (\log n)^k + a_ (\log n)^ + \cdots + a_1(\log n) + a_0.
The notation is often used as a shorthand for , analogous to for .
In computer science, poly ...
time if its time
is
for some constant . Another way to write this is
.
For example,
matrix chain ordering can be solved in polylogarithmic time on a
parallel random-access machine
In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confused ...
, and
a graph can be
determined to be planar in a
fully dynamic way in
time per insert/delete operation.
Sub-linear time
An algorithm is said to run in sub-linear time (often spelled sublinear time) if
. In particular this includes algorithms with the time complexities defined above.
Typical algorithms that are exact and yet run in sub-linear time use
parallel processing (as the
NC1 matrix determinant calculation does), or alternatively have guaranteed assumptions on the input structure (as the logarithmic time
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
and many tree maintenance algorithms do). However,
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
s such as the set of all strings that have a 1-bit in the position indicated by the first
bits of the string may depend on every bit of the input and yet be computable in sub-linear time.
The specific term ''sublinear time algorithm'' is usually reserved to algorithms that are unlike the above in that they are run over classical serial machine models and are not allowed prior assumptions on the input. They are however allowed to be
randomized
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...
, and indeed must be randomized for all but the most trivial of tasks.
As such an algorithm must provide an answer without reading the entire input, its particulars heavily depend on the access allowed to the input. Usually for an input that is represented as a binary string
it is assumed that the algorithm can in time
request and obtain the value of
for any .
Sub-linear time algorithms are typically randomized, and provide only
approximate
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
solutions. In fact, the property of a binary string having only zeros (and no ones) can be easily proved not to be decidable by a (non-approximate) sub-linear time algorithm. Sub-linear time algorithms arise naturally in the investigation of
property testing
In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if s ...
.
Linear time
An algorithm is said to take linear time, or
time, if its time complexity is
. Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant such that the running time is at most
for every input of size . For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.
Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploit
parallelism to provide this. An example is
content-addressable memory
Content-addressable memory (CAM) is a special type of computer memory used in certain very-high-speed searching applications. It is also known as associative memory or associative storage and compares input search data against a table of stored d ...
. This concept of linear time is used in string matching algorithms such as the
Boyer–Moore algorithm and
Ukkonen's algorithm
In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995. The algorithm begins with an implicit suffix tree containing the first character of the string. Then it ste ...
.
Quasilinear time
An algorithm is said to run in quasilinear time (also referred to as log-linear time) if
for some positive constant ; linearithmic time is the case
. Using
soft O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
these algorithms are
. Quasilinear time algorithms are also
for every constant
and thus run faster than any polynomial time algorithm whose time bound includes a term
for any
.
Algorithms which run in quasilinear time include:
*
In-place merge sort,
*
Quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
,
, in its randomized version, has a running time that is
in expectation on the worst-case input. Its non-randomized version has an
running time only when considering average case complexity.
*
Heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
,
,
merge sort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same i ...
,
introsort
Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a l ...
, binary tree sort,
smoothsort
In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of , but it is not a ...
,
patience sorting
In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array.
Overview
The algor ...
, etc. in the worst case
*
Fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...
s,
*
Monge array
In mathematics applied to computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge.
An ''m''-by-''n'' matrix is said to be a ''Monge array'' if, for all \scripts ...
calculation,
In many cases, the
running time is simply the result of performing a
operation times (for the notation, see ). For example,
binary tree sort
A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree ( in-order) so that the elements come out in sorted order. Its typical use is sorting elements online: after each insert ...
creates a
binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
by inserting each element of the -sized array one by one. Since the insert operation on a
self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donal ...
takes
time, the entire algorithm takes
time.
Comparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occ ...
s require at least
comparisons in the worst case because
, by
Stirling's approximation
In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of n. It is named after James Stirling, though a related but less p ...
. They also frequently arise from the
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
.
Sub-quadratic time
An
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
is said to be subquadratic time if
.
For example, simple, comparison-based
sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. ...
s are quadratic (e.g.
insertion sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howev ...
), but more advanced algorithms can be found that are subquadratic (e.g.
shell sort
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange ( bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of ...
). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.
Polynomial time
An algorithm is said to be of polynomial time if its running time is
upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an element ...
ed by a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
expression in the size of the input for the algorithm, that is, for some positive constant ''k''.
Problems
A problem is a difficulty which may be resolved by problem solving.
Problem(s) or The Problem may also refer to:
People
* Problem (rapper), (born 1985) American rapper Books
* ''Problems'' (Aristotle), an Aristotelian (or pseudo-Aristotelian) co ...
for which a deterministic polynomial-time algorithm exists belong to the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
P, which is central in the field of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
.
Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".
Some examples of polynomial-time algorithms:
* The
selection sort
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is not ...
sorting algorithm on ''n'' integers performs
operations for some constant ''A''. Thus it runs in time
and is a polynomial-time algorithm.
* All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
*
Maximum matching
Maximum cardinality matching is a fundamental problem in graph theory.
We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...
s in
graphs
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
can be found in polynomial time.
Strongly and weakly polynomial time
In some contexts, especially in
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, one differentiates between strongly polynomial time and weakly polynomial time algorithms. These two concepts are only relevant if the inputs to the algorithms consist of integers.
Strongly polynomial time is defined in the arithmetic model of computation. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if:
# the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
# the space used by the algorithm is bounded by a polynomial in the size of the input.
Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
. The second condition is strictly necessary: given the integer
(which takes up space proportional to ''n'' in the Turing machine model), it is possible to compute
with ''n'' multiplications using
repeated squaring. However, the space used to represent
is proportional to
, and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.
However, for the first condition, there are algorithms that run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
for computing the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of two integers is one example. Given two integers
and
, the algorithm performs
arithmetic operations on numbers with
at most
bits. At the same time, the number of arithmetic operations cannot be bounded by the number of integers in the input (which is constant in this case, there are always only two integers in the input). Due to the latter observation, the algorithm does not run in strongly polynomial time. Its real running time depends ''logarithmically'' on the magnitudes of
and
(that is, on their length in bits) and not only on the number of integers in the input.
An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in weakly polynomial time.
A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm, is
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
. Weakly polynomial time should not be confused with
pseudo-polynomial time In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the ''numeric value'' of the input (the largest integer present in the input)—but not necessarily in the ''length'' of t ...
, which depends ''linearly'' on the magnitude of values in the problem and is not truly polynomial time.
Complexity classes
The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.
*
P: The
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
of
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s that can be solved on a
deterministic Turing machine in polynomial time
*
NP: The complexity class of decision problems that can be solved on a
non-deterministic Turing machine
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...
in polynomial time
*
ZPP: The complexity class of decision problems that can be solved with zero error on a
probabilistic Turing machine
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turin ...
in polynomial time
*
RP: The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
*
BPP
BPP may refer to:
Education
* BPP Holdings, a holding company based in the United Kingdom
* BPP Law School, a law school based in the United Kingdom and a constituent school of BPP University
* BPP University, a private university based in the ...
: The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time
*
BQP: The complexity class of decision problems that can be solved with 2-sided error on a
quantum Turing machine
A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algori ...
in polynomial time
P is the smallest time-complexity class on a deterministic machine which is
robust
Robustness is the property of being strong and healthy in constitution. When it is transposed into a system, it refers to the ability of tolerating perturbations that might affect the system’s functional body. In the same line ''robustness'' ca ...
in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any given
abstract machine
An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pre ...
will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.
Superpolynomial time
An algorithm is defined to take superpolynomial time if ''T''(''n'') is not bounded above by any polynomial. Using
little omega notation, it is ''ω''(''n''
''c'') time for all constants ''c'', where ''n'' is the input parameter, typically the number of bits in the input.
For example, an algorithm that runs for 2
''n'' steps on an input of size ''n'' requires superpolynomial time (more specifically, exponential time).
An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the
Adleman–Pomerance–Rumely primality test In computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime. Unlike other, more efficient algorithms for this purpose, it avoids the use of random numbers, so it is a dete ...
runs for time on ''n''-bit inputs; this grows faster than any polynomial for large enough ''n'', but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.
An algorithm that requires superpolynomial time lies outside the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
P.
Cobham's thesis posits that these algorithms are impractical, and in many cases they are. Since the
P versus NP problem
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
is unresolved, it is unknown whether
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problems require superpolynomial time.
Quasi-polynomial time
Quasi-polynomial time algorithms are algorithms that run longer than polynomial time, yet not so long as to be exponential time. The worst case running time of a quasi-polynomial time algorithm is
for some fixed For
we get a polynomial time algorithm, for
we get a sub-linear time algorithm.
Quasi-polynomial time algorithms typically arise in
reductions
Reductions ( es, reducciones, also called ; , pl. ) were settlements created by Spanish rulers and Roman Catholic missionaries in Spanish America and the Spanish East Indies (the Philippines). In Portuguese-speaking Latin America, such redu ...
from an
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
problem to another problem. For example, one can take an instance of an NP hard problem, say
3SAT
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
, and convert it to an instance of another problem B, but the size of the instance becomes
. In that case, this reduction does not prove that problem B is NP-hard; this reduction only shows that there is no polynomial time algorithm for B unless there is a quasi-polynomial time algorithm for 3SAT (and thus all of
NP). Similarly, there are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed
Steiner tree problem
In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a nu ...
, for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of
(''n'' being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.
Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include the
planted clique
In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique pr ...
problem in which the goal is to
find a large clique in the union of a clique and a
random graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs li ...
. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a
computational hardness assumption
In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (uncondition ...
to prove the difficulty of several other problems in computational
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
,
property testing
In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if s ...
, and
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
.
The complexity class QP consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of
DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...
as follows.
:
Relation to NP-complete problems
In complexity theory, the unsolved
P versus NP
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is the square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the
exponential time hypothesis
In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...
.
Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of
approximation algorithms
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solut ...
make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the
set cover
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the univ ...
problem.
Sub-exponential time
The term
sub-exponential time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon, and we list the two most widely used ones below.
First definition
A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every there exists an algorithm which solves the problem in time ''O''(2
''n''''ε''). The set of all such problems is the complexity class SUBEXP which can be defined in terms of
DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...
as follows.
:
This notion of sub-exponential is non-uniform in terms of ''ε'' in the sense that ''ε'' is not part of the input and each ε may have its own algorithm for the problem.
Second definition
Some authors define sub-exponential time as running times in
.
This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the
general number field sieve
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form
:\exp\left( ...
, which runs in time about where the length of the input is . Another example was the
graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational compl ...
, which the best known algorithm from 1982 to 2016 solved in However, at
STOC 2016 a quasi-polynomial time algorithm was presented.
It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In
parameterized complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
, this difference is made explicit by considering pairs
of
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s and parameters ''k''. SUBEPT is the class of all parameterized problems that run in time sub-exponential in ''k'' and polynomial in the input size ''n'':
:
More precisely, SUBEPT is the class of all parameterized problems
for which there is a
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
with
and an algorithm that decides ''L'' in time
.
Exponential time hypothesis
The exponential time hypothesis (ETH) is that
3SAT
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
, the satisfiability problem of Boolean formulas in
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
with at most three literals per clause and with ''n'' variables, cannot be solved in time 2
''o''(''n''). More precisely, the hypothesis is that there is some absolute constant such that 3SAT cannot be decided in time 2
''cn'' by any deterministic Turing machine. With ''m'' denoting the number of clauses, ETH is equivalent to the hypothesis that ''k''SAT cannot be solved in time 2
''o''(''m'') for any integer . The exponential time hypothesis implies
P ≠ NP
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used above ...
.
Exponential time
An algorithm is said to be exponential time, if ''T''(''n'') is upper bounded by 2
poly(''n''), where poly(''n'') is some polynomial in ''n''. More formally, an algorithm is exponential time if ''T''(''n'') is bounded by ''O''(2
''n''''k'') for some constant ''k''. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as
EXP Exp may stand for:
* Exponential function
The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the pos ...
.
:
Sometimes, exponential time is used to refer to algorithms that have ''T''(''n'') = 2
''O''(''n''), where the exponent is at most a linear function of ''n''. This gives rise to the complexity class
E.
:
Factorial time
An algorithm is said to be factorial time if ''T(n)'' is upper bounded by the
factorial function ''n!''. Factorial time is a subset of exponential time (EXP) because
for all
. However, it is not a subset of E.
An example of an algorithm that runs in factorial time is
bogosort
In computer science, bogosort (also known as permutation sort, stupid sort, slowsort or bozosort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one th ...
, a notoriously inefficient sorting algorithm based on
trial and error
Trial and error is a fundamental method of problem-solving characterized by repeated, varied attempts which are continued until success, or until the practicer stops trying.
According to W.H. Thorpe, the term was devised by C. Lloyd Morgan (1 ...
. Bogosort sorts a list of ''n'' items by repeatedly
shuffling
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.
__TOC__
Techniques
Overha ...
the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the ''n''! orderings of the ''n'' items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the
infinite monkey theorem
The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, such as the complete works of William Shakespeare. In fact, the monkey would ...
.
Double exponential time
An algorithm is said to be
double exponential time if ''T''(''n'') is upper bounded by 2
2poly(''n''), where poly(''n'') is some polynomial in ''n''. Such algorithms belong to the complexity class
2-EXPTIME.
:
Well-known double exponential time algorithms include:
* Decision procedures for
Presburger arithmetic
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitti ...
* Computing a
Gröbner basis
In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring over a field . A Gröbn ...
(in the worst case)
*
Quantifier elimination Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement "\exists x such that \ldots" can be viewed as a question "When is there an x such t ...
on
real closed field
In mathematics, a real closed field is a field ''F'' that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.
Def ...
s takes at least double exponential time, and can be done in this time.
See also
*
L-notation
''L''-notation is an asymptotic notation analogous to big-O notation, denoted as L_n alpha,c/math> for a bound variable n tending to infinity. Like big-O notation, it is usually used to roughly convey the rate of growth of a function, such as the ...
*
Space complexity
The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it ex ...
References
{{Use dmy dates, date=September 2019
Analysis of algorithms
Computational complexity theory
Computational resources
Time