Complexity Theory
The theory of classifying problems based on how difficult they are to solve. A problem is assigned to the P-problem (polynomial-time) class if the number of steps needed to solve it is bounded by some power of the problem's size. A problem is assigned to the NP-problem (nondeterministic polynomial-time) class if it permits a nondeterministic solution and the number of steps to verify the solution is bounded by some power of the problem's size. The class of P-problems is a subset of the class of NP-problems, but there also exist problems which are not NP.
There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. In fact, the problem of identifying isomorphic graphs seems to fall in a crack between P and NP-complete, if such a crack exists (Skiena 1990, p. 181), and as a result, the problem is sometimes assigned to a special graph isomorphism complete complexity class.
If a solution is known to an NP-problem, it can be reduced to a single polynomial-time verification. A problem is NP-complete if it is NP and an algorithm for solving it can be translated into one for solving any other NP-problem. Examples of NP-complete problems include the Hamiltonian cycle and traveling salesman problems. Linear programming, thought to be an NP-problem, was shown to actually be a P-problem by L. Khachian in 1979. It is not known if all apparently NP-problems are actually P-problems.
Bridges, D. S. Computability. New York: Springer-Verlag, 1994.
Brookshear, J. G. Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, CA: Benjamin/Cummings, 1989.
Cooper, S. B.; Slaman, T. A.; and Wainer, S. S. (Eds.). Computability, Enumerability, Unsolvability: Directions in Recursion Theory. New York: Cambridge University Press, 1996.
Davis, M. Computability and Unsolvability. New York: Dover, 1982.
Du, D.-Z. and Ko, K.-I. Theory of Computational Complexity. New York; Wiley, 2000.
Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.
Goetz, P. "Phil
Goetz's Complexity Dictionary." https://www.cs.buffalo.edu/~goetz/dict.html
Griffor, E. R. (Ed.). Handbook of Computability Theory. Amsterdam, Netherlands: Elsevier, 1999.
Hopcroft, J. E. and Ullman, J. D. Introduction to Automated Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979.
Lewis, H. R. and Papadimitriou, C. H. Elements of the Theory of Computation, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1997.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.
Sudkamp, T. A. Language and Machines: An Introduction to the Theory of Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1996.
Weisstein, E. W. "Books about Computational Complexity." https://www.ericweisstein.com/encyclopedias/books/ComputationalComplexity.html.
Welsh, D. J. A. Complexity: Knots, Colourings and Counting. New York: Cambridge University Press, 1993.
Weisstein, Eric W. "Complexity Theory." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ComplexityTheory.html
Contact the MathWorld Team
complexity theory