List of computability and complexity topics

List of computability and complexity topics

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.

Contents

Calculation

Computability theory: models of computation

Decision problems

Definability questions

Complexity theory

Complexity classes

See the list of complexity classes

Named problems

Extensions


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • List of basic discrete mathematics topics — Discrete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally , in the sense of not supporting or requiring the notion of continuity. Most, if not all, of the objects studied in finite… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of algorithm general topics — This is a list of algorithm general topics, by Wikipedia page. * Analysis of algorithms * Ant colony algorithm * Approximation algorithm * Best and worst cases * Big O notation * Combinatorial search * Competitive analysis * Computability theory… …   Wikipedia

  • List of complexity classes — This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics.Many of these classes have a Co partner which consists of the complements of …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Lists of mathematics topics — This article itemizes the various lists of mathematics topics. Some of these lists link to hundreds of articles; some link only to a few. The extremely long list of mathematics articles contains all mathematical articles in alphabetical order.… …   Wikipedia

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Computability — You might be looking for Computable function, Computability theory, Computation, or Theory of computation. Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within… …   Wikipedia

  • List of software engineering topics — This list complements the software engineering article, giving more details and examples. For an alphabetical listing of topics, please see List of software engineering topics (alphabetical).Influence on societySoftware engineers affect society… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”