List of computability and complexity topics

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

This is a list of computability and complexity topics, by Wikipedia page.

Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard computations are, in quantitative terms, both with upper bounds (algorithms whose complexity in the worst cases, as use of computing resources, can be estimated), and from below (proofs that no procedure to carry out some task can be very fast).

For more abstract foundational matters, see the list of mathematical logic topics. See also list of algorithms, list of algorithm general topics.

Calculation

Computability theory: models of computation

Decision problems

Definability questions

Complexity theory

Complexity classes

See the list of complexity classes

Named problems

Extensions

Retrieved from "https://en.wikipedia.org/w/index.php?title=List_of_computability_and_complexity_topics&oldid=801124807"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/List_of_computability_and_complexity_topics
This page is based on the copyrighted Wikipedia article "List of computability and complexity topics"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA