TOPICS
Search

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.


See also

Bit Complexity, Graph Isomorphism Complete, NP-Complete Problem, NP-Hard Problem, NP-Problem, P-Problem, P Versus NP Problem

Explore with Wolfram|Alpha

References

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.Update a linkGoetz, P. "Phil Goetz's Complexity Dictionary." http://www.cs.buffalo.edu/~goetz/dict.htmlGriffor, 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." http://www.ericweisstein.com/encyclopedias/books/ComputationalComplexity.html.Welsh, D. J. A. Complexity: Knots, Colourings and Counting. New York: Cambridge University Press, 1993.

Referenced on Wolfram|Alpha

Complexity Theory

Cite this as:

Weisstein, Eric W. "Complexity Theory." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ComplexityTheory.html

Subject classifications