Information & explanations, latest texts & monographs on
Computational_complexity_theory (including recent related patents.)
Computational complexity theoryComplexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem). Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required. Table of contents showTocToggle("show","hide") 1 Overview 2 Decision problems 3 The P=NP question 4 Famous complexity classes 5 Notable Researchers Overview 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. 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 n2 steps. In this example we say the problem has a time complexity of n2. 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(n2) on one typical computer, then it will also have complexity O(n2) on most other computers, so this notation allows us to generalize away from the details of a particular computer. 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 for a double sized dictionary you have to open it only 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. 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. 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. 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. At least for time complexity, and for polynomial-time decision problems, this is determined by the time hierarchy theorem. A similar space hierarchy theorem can be derived from it. The P=NP question The set P is the set of decision problems that can be solved by a deterministic machine in polynomial time. The set NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. 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). 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". Famous complexity classes The following are some of the classes of problems considered in complexity theory, along with rough definitions. See computation for a chart showing which classes are subsets of other classes. Many of these classes have a 'Co' partner (ie NP and Co-NP) which consists of the complements of all languages in the original class. For example if L is in NP then the complement of L is in Co-NP. (This doesn't mean that the complement of NP is Co-NP - there are languages which are known to be in both, and other languages which are known to be in neither). If you don't see a class listed (such as Co-UP) you should look under its partner (such as UP). PSolvable in polynomial time NPYES answers checkable in polynomial time (see complexity classes P and NP) Co-NPNO answers checkable in polynomial time NP-completeThe hardest problems in NP Co-NP-completeThe hardest problems in Co-NP NP-hardEither NP-complete or harder NP-easynon-decision-problem analogue to NP NP-equivalentnon-decision-problem analogue to NP-complete UPUnambiguous Non-Deterministic Polytime functions. #PCount solutions to an NP problem #P-completeThe hardest problems in #P NCSolvable efficiently (in polylogarithmic time) on parallel computers P-completeThe hardest problems in P to solve on parallel computers PSPACESolvable with polynomial memory and unlimited time PSPACE-completeThe hardest problems in PSPACE EXPTIMESolvable with exponential time EXPSPACESolvable with exponential memory and unlimited time BQPSolvable in polynomial time on a quantum computer (answer is probably right) BPPSolvable in polynomial time by randomized algorithms (answer is probably right) RPSolvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) ZPPSolvable by randomized algorithms (answer is always right, average running time is polynomial) PCP Checkable in polynomial time by a randomized algorithm. Notable Researchers Important Complexity classes P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IPThis article is adapted from from Wikipedia All Wikipedia article text is available under the terms of the GNU Free Documentation License Introduction to the Theory of Computation by Michael Sipser Introduction to Automata Theory, Languages, and Computation (2nd Edition) by John E. Hopcroft Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences) by Michael R. Garey Computability and Complexity Theory by Alan L. Selman Combinatorial Optimization : Networks and Matroids by Eugene Lawler Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft Computability, Complexity, and Languages : Fundamentals of Theoretical Computer Science by Ron Sigal Complexity and Postmodernism: Understanding Complex Systems by Paul Cilliers Elements of the Theory of Computation by Harry R. Lewis Languages and Machines: An Introduction to the Theory of Computer Science (2nd Edition) by Thomas A. Sudkamp Elements of the Theory of Computation (2nd Edition) by Harry R. Lewis Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties by G. Ausiello The Unknowable (Springer Series in Discrete Mathematics and Theoretical Computer Science) by Gregory J. Chaitin Parameterized Complexity (Monographs in Computer Science) by R. G. Downey PI and the AGM: A Study in Analytic Number Theory and Computational Complexity by Jonathan M. Borwein Recent Computational_complexity_theory related patents From USPTO: |