|
In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given computational problem. This cost is usually measured in terms of abstract parameters such as time and space, called computational resources. Time represents the number of steps it takes to solve a problem and space represents the quantity of information storage required or how much memory it takes. There are often tradeoffs between time and space that have to be considered when trying to solve a computational problem. It often turns out that an alternative algorithm will require less time but more space (or vice versa) to solve a given problem. Time requirements sometimes must be amortized to determine the time cost for a well defined average case. Space requirements can be profiled over time, too, especially in consideration of a multi-user computer system. Image File history File links Portal. ...
Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. ...
Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ...
In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. ...
In computational complexity theory, a computational resource is a resource used by some computational model in the solution of computational problems. ...
Flowcharts are often used to represent algorithms. ...
Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. In this case, "parallelizable time" and "non-parallelizable time" are considered. The latter is important in real-time applications, and it gives a limit to how far the computation can be parallelized. Some steps must be done sequentially because they depend on the results of previous steps. Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain faster results. ...
Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required. In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ...
Overview After the theory explaining which problems can be solved and which cannot be, it was natural to ask about the relative computational difficulty of computable functions. This is the subject matter of computational complexity. It has been suggested that recursive function be merged into this article or section. ...
A single "problem" is an entire set of related questions, where each question is a finite-length string. For example, the problem FACTORIZE is: given an integer written in binary, return all of the prime factors of that number. A particular question is called an instance. For example, "give the factors of the number 15" is one instance of the FACTORIZE problem. In computer programming and some branches of mathematics, strings are sequences of various simple objects. ...
In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ...
The binary or base-two numeral system is a system for representing numbers in which a radix of two is used; that is, each digit in a binary numeral may have either of two different values. ...
In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...
The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. To understand this intuitively, consider the example of an instance that is n bits long that can be solved in n² steps. In this example we say the problem has a time complexity of n². Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, we generally use Big O notation. If a problem has time complexity O(n²) on one typical computer, then it will also have complexity O(n²p(n)) on most other computers for some polynomial p(n), so this notation allows us to generalize away from the details of a particular computer. In the fields of algorithm analysis and computational complexity theory, the running time or space requirements of an algorithm are expressed as a function of the problem size. ...
Flowcharts are often used to represent algorithms. ...
It has been suggested that Landau notation be merged into this article or section. ...
In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...
Example: Mowing grass has linear complexity because it takes double the time to mow double the area. However, looking up something in a dictionary has only logarithmic complexity because a double sized dictionary only has to be opened one time more (e.g. exactly in the middle - then the problem is reduced to the half).
Decision problems Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always YES/NO. For example, the problem IS-PRIME is: given an integer written in binary, return whether it is a prime number or not. A decision problem is equivalent to a language, which is a set of finite-length strings. For a given decision problem, the equivalent language is the set of all strings for which the answer is YES. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...
Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem. For example, the problem HAS-FACTOR is: given integers n and k written in binary, return whether n has any prime factors less than k. If we can solve HAS-FACTOR with a certain amount of resources, then we can use that solution to solve FACTORIZE without much more resources. Just do a binary search on k until you find the smallest factor of n. Then divide out that factor, and repeat until you find all the factors. In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ...
Complexity theory often makes a distinction between YES answers and NO answers. For example, the set NP is defined as the set of problems where the YES instances can be checked "quickly" (i.e. in polynomial time). The set Co-NP is the set of problems where the NO instances can be checked quickly. The "Co" in the name stands for "complement". The complement of a problem is one where all the YES and NO answers are swapped, such as IS-COMPOSITE for IS-PRIME. In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. ...
An important result in complexity theory is the fact that no matter how hard a problem can get (i.e. how much time and space resources it requires), there will always be even harder problems. For time complexity, this is determined by the time hierarchy theorem. A similar space hierarchy theorem can also be derived. In computational complexity theory, the time hierarchy theorems are important statements that ensure the existence of certain hard problems which cannot be solved in a given amount of time. ...
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. ...
Computational resources Complexity theory analyzes the difficulty of computational problems in terms of many different computational resources. The same problem can be described in terms of the necessary amounts of many different computational resources, including time, space, randomness, alternation, and other less-intuitive measures. A complexity class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource. In computational complexity theory, a computational resource is a resource used by some computational model in the solution of computational problems. ...
Alternation is a solitaire card game which is played using two decks of playing cards. ...
In computational complexity theory, a complexity class is a set of problems of related complexity. ...
Perhaps the most well-studied computational resources are deterministic time (DTIME) and deterministic space (DSPACE). These resources represent the amount of computation time and memory space needed on a deterministic computer, like the computers that actually exist. These resources are of great practical interest, and are well-studied.
Some computational problems are easier to analyze in terms of more unusual resources. For example, a nondeterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The nondeterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that nondeterministic time is a very important resource in analyzing computational problems. In theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state of...
Many more unusual computational resources have been used in complexity theory. Technically, any complexity measure can be viewed as a computational resource, and complexity measures are very broadly defined by the Blum complexity axioms. In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. ...
In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. ...
Complexity classes A complexity class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource. In computational complexity theory, a complexity class is a set of problems of related complexity. ...
The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases. In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...
The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...
In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. This class contains many problems that people would like to be able to solve effectively, including the Boolean satisfiability problem, the Hamiltonian path problem and the Vertex cover problem. All the problems in this class have the property that their solutions can be checked effectively. In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ...
In theoretical computer science, an ordinary (deterministic) Turing machine (DTM) has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state...
The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ...
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). ...
In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karps 21 NP-complete problems. ...
Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity. Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ...
Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, in which we seek to characterize complexity classes by the type of logic needed to express the languages in them. ...
The P = NP question The question of whether P is the same set as NP is the most important open question in theoretical computer science. There is even a $1,000,000 prize for solving it. (See complexity classes P and NP and oracles). The Clay Mathematics Institute (CMI) is a private, non-profit foundation, based in Cambridge, Massachusetts, and dedicated to increasing and disseminating mathematical knowledge. ...
Diagram of complexity classes provided that P ≠NP. If P = NP, then all three classes are equal. ...
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...
Questions like this motivate the concepts of hard and complete. A set of problems X is hard for a set of problems Y if every problem in Y can be transformed easily into some problem in X with the same answer. The definition of "easily" is different in different contexts. The most important hard set is NP-hard. Set X is complete for Y if it is hard for Y, and is also a subset of Y. The most important complete set is NP-complete. See the articles on those two sets for more detail on the definition of "hard" and "complete". In computational complexity theory, a computational problem is complete for a complexity class when it is, in a formal sense, one of the hardest or most expressive problems in the complexity class. ...
In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing...
In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
Intractability Problems that are solvable in theory, but cannot be solved in practice, are called intractable. What can be solved "in practice" is open to debate, but in general only problems that have polynomial-time solutions are solvable for more than the smallest inputs. Problems that are known to be intractable include those that are EXPTIME-complete. If NP is not the same as P, then the NP-complete problems are also intractable. The word decidable has formal meaning in computability theory, the theory of formal languages, and mathematical logic. ...
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ...
To see why exponential-time solutions are not usable in practice, consider a problem that requires 2n operations to solve (n is the size of the input). For a relatively small input size of n=100, and assuming a computer that can perform 1010 (10 giga) operations per second, a solution would take about 4*1012 years, much longer than the current age of the universe. giga- (symbol: G) is a prefix in the SI system of units denoting 109, or 1 000 000 000. ...
Nothing is certain as to the extent of either the age or size of the universe, but the age of the Universe, according to the Big Bang theory, is defined as the largest possible value of proper time integrated along a timelike curve from the Earth at the present epoch...
Notable researchers László Babai László Babai (called Laci by friends and colleagues) is a professor of mathematics and computer science at the University of Chicago. ...
Manuel Blum (born 26 April 1938 in Caracas, Venezuela) is a computer scientist who received the Turing Award in 1995 In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking. // Biography Blum attended MIT, where he received his bachelors...
In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. ...
Allan Bertram Borodin is a mathematician who has done important work in computational complexity theory. ...
Stephen A. Cook is a noted computer scientist. ...
Juris Hartmanis (born July 7, 1928 in Riga, Latvia) is a prominent computer scientist who, with Richard E. Stearns, received the 1993 ACM Turing Award in recognition of their seminal paper which established the foundations for the field of computational complexity theory. Born in Latvia, he moved to Germany after...
This article is being considered for deletion in accordance with Wikipedias deletion policy. ...
Richard M. Karp (born 1935) is a computer scientist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985. ...
Marek Karpinski is a computer scientist known for his research in the theory of algorithms and their applications, combinatorial optimization, computational complexity, and mathematical foundations. ...
Leonid Levin (born 1948, USSR) is a computer scientist. ...
Christos H. Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory. ...
Alexander Razborov is a Russian mathematician who won the Nevanlinna Prize in 1990 for his work in theoretical aspects of computer science. ...
Walter Savitch is a Professor Emeritus of Computer Science at the University of California at San Diego. ...
Michael Sipser Michael Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. ...
Richard Edwin Stearns is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award in recognition of their seminal paper which established the foundations for the field of computational complexity theory. Stearns is now Distinguished Professor Emeritus of Computer Science at the University at Albany, which...
In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. ...
Madhu Sudan (मधॠसूदन) (b. ...
Leslie Valiant was educated at Kings College, Cambridge, Imperial College London; and at Warwick University where he received his Ph. ...
Andrew Chi-Chih Yao (Chinese: 姚期智; Hanyu Pinyin: ) (born December 24, 1946) is a prominent computer scientist. ...
Professor Oded Goldreich Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. ...
See also For the Computer Science term, see Computational complexity theory. ...
This is a list of important publications in computer science, organized by field. ...
This is a list of unsolved problems in computer science. ...
This is a list of computability and complexity topics, by Wikipedia page. ...
In combinatorial game theory, game complexity is a measure of the complexity of a game. ...
The Complexity of Songs was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory. ...
References
External links |
Feeds |
Contact