Computer science Portal

As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g., execution time), and the inherent difficulty in providing efficient algorithms for specific computational problems. Image File history File links Portal. ... The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In computational complexity theory, a computational resource is a resource used by some computational model in the solution of computational problems. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. ...

A typical question of the theory is, "As the size of the input to an algorithm increases, how do the running time and memory requirements of the algorithm change and what are the implications and ramifications of that change?" In other words, the theory, among other things, investigates the scalability of computational problems and algorithms. In particular, the theory places practical limits on what computers can accomplish. It has been suggested that this article or section be merged with Scale (computing). ... This article is about the machine. ...

An important aspect of the theory is to categorize computational problems and algorithms into complexity classes. The most important open question of complexity theory is whether the complexity class P is the same as the complexity class NP, or is merely a subset as is generally believed. Shortly after the question was first posed, it was realised that many important industry problems in the field of operations research are of an NP subclass called NP-complete. NP-complete problems have the property that solutions to these problems are quick to check, yet the current methods to find solutions are not "efficiently scalable" (as described more formally below). More importantly, if the NP class is larger than P, then no efficiently scalable solutions exist for these problems. In computational complexity theory, a complexity class is a set of problems of related complexity. ... 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. ... 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. ... Operations Research or Operational Research (OR) is an interdisciplinary branch of mathematics which uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima (profit, faster assembly line, greater crop yield, higher bandwidth, etc) or minima... 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...

The openness of the P-NP problem prompts and justifies various research areas in the computational complexity theory, such as identification of efficiently solvable special cases of common computational problems, study of the computational complexity of finding approximate or heuristic solutions, as well as research into the hierarchies of complexity classes.

Overview

Complexity theory deals with the relative computational difficulty of computable functions. This differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required. Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ... 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. ...

A single "problem" is a complete 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 formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... “Prime decomposition” redirects here. ... 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 which has exactly two distinct natural number divisors: 1 and 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, the Big O notation is generally used (sometimes described as the "order" of the calculation, as in "on the order of"). If a problem has time complexity O(n²) on one typical computer, then it will also have complexity O(n²) on most other computers, 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. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...

Example: Mowing grass has linear time complexity because it takes double the time to mow double the area. However, looking up something in a dictionary has only logarithmic time complexity because a double sized dictionary only has to be opened one time more (i.e. exactly in the middle, then the problem size is reduced by half). A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. ...

The space complexity of a problem is a related concept, that measures the amount of space, or memory required by the algorithm. An informal analogy would be the amount of scratch paper needed while working out a problem with pen and paper. Space complexity is also measured with Big O notation. The terms storage (U.K.) or memory (U.S.) refer to the parts of a digital computer that retain physical state (data) for some interval of time, possibly even after electrical power to the computer is turned off. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...

A different measure of problem complexity, which is useful in some cases, is circuit complexity. This is a measure of the size of a boolean circuit needed to compute the answer to a problem, in terms of the number of logic gates required to build the circuit. Such a measure is useful, for example, when designing hardware microchips to compute the function instead of software. Circuit complexity is a topic in computational complexity theory, a branch of theoretical computer science which classifies boolean functions according to the amount of computational resources needed to compute them. ... Boolean logic is a complete system for logical operations. ... A logic gate is an arrangement of electronically-controlled switches used to calculate operations in Boolean algebra. ... Integrated circuit of Atmel Diopsis 740 System on Chip showing memory blocks, logic and input/output pads around the periphery Microchips with a transparent window, showing the integrated circuit inside. ... Computer software (or simply software) refers to one or more computer programs and data held in the storage of a computer for some purpose. ...

Decision problems

Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always yes or no. Complexity theory distinguishes between problems verifying yes and problems verifying no answers. A problem that reverses the yes and no answers of another problem is called a complement of that problem. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. ...

For example, a well known decision problem IS-PRIME returns a yes answer when a given input is a prime and a no otherwise, while the problem IS-COMPOSITE determines whether a given integer is not a prime number (i.e. a composite number). When IS-PRIME returns a yes, IS-COMPOSITE returns a no, and vice versa. So the IS-COMPOSITE is a complement of IS-PRIME, and similarly IS-PRIME is a complement of IS-COMPOSITE. In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... A composite number is a positive integer which has a positive divisor other than one or itself. ...

Decision problems are often considered because an arbitrary problem can always be reduced to some decision problem. For instance, 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. This is accomplished by doing a binary search on k until the smallest factor of n is found, then dividing out that factor and repeating until all the factors are found. In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. ... 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. ...

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 proven 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 explained 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. In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. ... In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. ...

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... In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(f(n)), and unlimited space. ...

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.^[1] 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 efficiently.^[1] 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... To meet Wikipedias quality standards, this article or section may require cleanup. ... 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 – this field is called descriptive complexity. Mathematical logic is a major area of mathematics, which grew out of symbolic logic. ... Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, which seeks to characterize complexity classes by the type of logic needed to express the languages in them. ...

Open questions

The P = NP question

Main article: Complexity classses P and NP

See also: Oracle machine

The question of whether NP is the same set as P (that is whether problems that can be solved in non-deterministic polynomial time can be solved in deterministic polynomial time) is one of the most important open questions in theoretical computer science due to the wide implications a solution would present.^[1] If it were true, many important problems would be shown to have "efficient" solutions. These include various types of integer programming in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems efficiently using computers.^[2][3] The P=NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute the solution of which is a US$1,000,000 prize for the first person to provide a solution.^[4] Computational complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... Operations Research or Operational Research (OR) is an interdisciplinary branch of mathematics which uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima (profit, faster assembly line, greater crop yield, higher bandwidth, etc) or minima... Look up Logistics in Wiktionary, the free dictionary. ... Protein structure prediction is one of the most significant technologies pursued by computational structural biology and theoretical chemistry. ... Biology studies the variety of life (clockwise from top-left) E. coli, tree fern, gazelle, Goliath beetle Biology (from Greek: βίος, bio, life; and λόγος, logos, knowledge), also referred to as the biological sciences, is the study of living organisms utilizing the scientific method. ... Broadly speaking, pure mathematics is mathematics motivated entirely for reasons other than application. ... This article is about the machine. ... The Clay Mathematics Institute (CMI) is a private, non-profit foundation, based in Cambridge, Massachusetts, and dedicated to increasing and disseminating mathematical knowledge. ... The Clay Mathematics Institute (CMI) is a private, non-profit foundation, based in Cambridge, Massachusetts. ... USD redirects here. ...

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 that produces the same solution. The definition of "easily" is different in different contexts. In the particular case of P versus NP, the relevant hard set is NP-hard – a set of problems, that are not necessarily in NP themselves, but to which any NP problem can be reduced in polynomial time. 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...

Set X is complete for Y if it is hard for Y, and is also a subset of Y. Thus, the set 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. Because the problem of P = NP remains unsolved, being able to reduce a problem to a known NP-complete problem would indicate that there is no known polynomial-time solution for it. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.^[1] 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...

Incomplete problems in NP

Diagram of complexity classes provided that P ≠ NP. The existence of problems in NP outside both P and NP-complete in this case was established by Ladner.^[5]

Incomplete problems are problems in NP that are neither NP-complete nor in P. In other words, incomplete problems can neither be solved in polynomial time nor do they belong to the hardest problems of NP. It has been shown that, if P ≠ NP, then there exist NP-incomplete problems.^[5][6] Image File history File links Complexity_classes. ... Image File history File links Complexity_classes. ...

An important open problem in this context is, whether the graph isomorphism problem is in P, NP-complete, or NP-incomplete. The answer is not known, but there are strong hints that the problem is at least not NP-complete.^[7] The graph isomorphism problem asks whether two given graphs are isomorphic. In computational complexity theory, the graph isomorphism problem or GI problem is the graph theory problem of determining whether, given two graphs G1 and G2, it is possible to permute (or relabel) the vertices of one graph so that it is equal to the other. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ...

NP = co-NP

Where co-NP is the set containing the complement problems (i.e. problems with the yes/no answers reversed) of NP problems. It is believed that the two classes are not equal, however it has not yet been proven. It has been shown that if these two complexity classes are not equal, then it follows that no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.^[6] In computational complexity theory, co-NP is a complexity class. ... In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. ... In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem...

Intractability

See also: Combinatorial explosion

Problems that are solvable in theory, but cannot be solved in practice, are called intractable. Naive complexity theory assumes problems that lack polynomial-time solutions are intractable for more than the smallest inputs. Problems that are known to be intractable in this sense include those that are EXPTIME-complete. If NP is not the same as P, then the NP-complete problems are also intractable in this sense. What this means "in practice" is open to debate. In cryptanalysis, a brute force attack on a cipher is a brute-force search of the key space; that is, testing all possible keys, in an attempt to recover the plaintext used to produce a particular ciphertext. ... 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 might be unusable in practice, consider a problem that requires 2ⁿ 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 10¹² operations per second, a solution would take about 4×10¹⁰ years, much longer than the current age of the universe. On the other hand, a problem that requires n¹⁵ operations would be in P, yet a solution would also take about 4×10¹⁰ years for n=100. And a problem that required 2^0.0000001*n operations would not be in P, but would be solvable for quite large cases. The age of the universe, in Big Bang cosmology, refers to the time elapsed between the Big Bang and the present day. ...

Finally, saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Presburger arithmetic is the first-order theory of the natural numbers with addition. ...

Researchers that have laid the foundations of the computational complexity theory

• Manuel Blum, who developed an axiomatic complexity theory based on his Blum axioms
• Allan Borodin
• Stephen Cook
• Michael R. Garey
• Oded Goldreich
• Juris Hartmanis
• David S. Johnson
• Richard Karp
• Donald Knuth
• Leonid Levin
• Christos H. Papadimitriou
• Alexander Razborov
• Richard Stearns
• Leslie Valiant
• Andrew Yao

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. ... Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... 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. ... 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... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ... 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. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Leonid Levin (born November 2, 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. ... 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... 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 and computational theorist. ...

See also

• Complexity
• List of important publications in computational complexity theory
• List of open problems in computational complexity theory
• List of computability and complexity topics
• Game complexity
• The Complexity of Songs
• Run-time analysis

Complexity in general usage is the opposite of simplicity. ... 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. ... Combinatorial game theory has several ways of measuring game complexity. ... 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. ... It has been suggested that this article or section be merged with Analysis of algorithms. ...

References

• L. Fortnow, Steve Homer (2002/2003). A Short History of Computational Complexity. In D. van Dalen, J. Dawson, and A. Kanamori, editors, The History of Mathematical Logic. North-Holland, Amsterdam.

• Jan van Leeuwen, ed. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, 1990. ISBN 978-0-444-88071-0 (Volume A). QA 76.H279 1990. Huge compendium of information, 1000s of references in the various articles.

1. ^ ^{a b c d} Sipser, Michael (2006). "Time Complexity", Introduction to the Theory of Computation, 2nd edition, USA: Thomson Course Technology. ISBN 0534950973. 
2. ^ Berger, Bonnie A.; Leighton, Terrance (1998). "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete". Journal of Computational Biology 5: p27-40. PubMed. 
3. ^ Cook, Stephen (April 2000). "The P versus NP Problem". Clay Mathematics Institute. Retrieved on 2006-10-18. 
4. ^ Jaffe, Arthur M. (2006). "The Millennium Grand Challenge in Mathematics". Notices of the AMS 53 (6). Retrieved on 2006-10-18. 
5. ^ ^{a b} Ladner, Richard E. (1975). "On the structure of polynomial time reducibility" (PDF). Journal of the ACM (JACM) 22: 151–171. doi:10.1145/321864.321877. 
6. ^ ^{a b} Du, Ding-Zhu; Ko, Ker-I (2000). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0. 
7. ^ Arvind, Vikraman & Kurur, Piyush P. (2006), "Graph isomorphism is in SPP", Information and Computation 204 (5): 835–852, DOI 10.1016/j.ic.2006.02.002

Michael Sipser Michael Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. ... Thomson Learning based in Connecticut is one of the four operating divisions of The Thomson Corporation(TSX:TOC; NYSE:TOC). ... Stephen A. Cook is a noted computer scientist. ... The Clay Mathematics Institute (CMI) is a private, non-profit foundation, based in Cambridge, Massachusetts. ... Year 2006 (MMVI) was a common year starting on Sunday of the Gregorian calendar. ... is the 291st day of the year (292nd in leap years) in the Gregorian calendar. ... Arthur Jaffe is an American mathematical physicist and a professor at Harvard University. ... Year 2006 (MMVI) was a common year starting on Sunday of the Gregorian calendar. ... is the 291st day of the year (292nd in leap years) in the Gregorian calendar. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... The Wiley Building in Hoboken, New Jersey, located on the waterfront between River Street and Frank Sinatra Drive. ...

External links

• The Complexity Zoo – a Wiki on complexity classes.
• Free (at least for now) book on computational complexity

In computational complexity theory, a complexity class is a set of problems of related complexity. ... This is a list of complexity classes in computational complexity theory. ... 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. ... 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 computational complexity theory, co-NP is a complexity class. ... 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... In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem... 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, UP (Unambiguous Non-deterministic Polynomial-time) is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input. ... The title given to this article is incorrect due to technical limitations. ... The title given to this article is incorrect due to technical limitations. ... In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In complexity theory, the class NC (Nicks Class) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. ... In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In complexity theory, PSPACE-complete is a complexity class. ... 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. ... In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2p(n)) for some polynomial p(n), and unlimited space. ... In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. ... In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2(2p(n))) time, where p(n) is a polynomial function of n. ... PR is the complexity class of all primitive recursive functions – or, equivalently, the set of all formal languages that can be decided by such a function. ... RE (recursively enumerable) is the class of decision problems for which a yes answer can be verified by a Turing machine in a finite amount of time. ... Co-RE is the set of all languages that are complements of a language in RE. In a sense, Co-RE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever. ... RE-complete is the set of decision problems that are complete for the complexity class RE. In a sense, these are the hardest recursively enumerable problems. ... CO-RE-complete is the set of decision problems that are complete for the complexity class co-RE. In a sense, these are the complements of the hardest recursively enumerable problems. ... The class of decision problems solvable by a Turing machine. ... BQP, in computational complexity theory, stands for Bounded error, Quantum, Polynomial time. It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances. ... This article is about the complexity class. ... In complexity theory, RP (randomized polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always runs in polynomial time in the input size If the correct answer is NO, it always returns NO If the correct answer is YES, then... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ... In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems. ... // Interactive Proof Systems In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has...