可计算性和复杂性列表

此词条暂由彩云小译翻译，翻译字数共115，未经人工整理和审校，带来阅读不便，请见谅。

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

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).

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.

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

有关更抽象的基本问题，请参阅数理逻辑主题列表。参见算法列表，算法一般主题列表。

Calculation

• Lookup table

• • Mathematical table

• • Multiplication table

• • Generating trigonometric tables

• History of computers

• Multiplication algorithm

• • Peasant multiplication

• Division by two

• Exponentiating by squaring

• Addition chain

• • Scholz conjecture

• Presburger arithmetic

Computability theory: models of computation

• Arithmetic circuits

• Algorithm

• • Procedure, recursion

• Finite state automaton

• • Mealy machine

• • Minsky register machine

• • Moore machine

• • State diagram

• • State transition system

• • Deterministic finite automaton

• • Nondeterministic finite automaton

• • Generalized nondeterministic finite automaton

• • Regular language

• • • Pumping lemma

• • • Myhill-Nerode theorem

• • Regular expression

• • Regular grammar

• • Prefix grammar

• • Tree automaton

• Pushdown automaton

• • Context-free grammar

• Büchi automaton

• Chomsky hierarchy

• • Context-sensitive language, context-sensitive grammar

• • Recursively enumerable language

• Register machine

• Stack machine

• Petri net

• Post machine

• Rewriting

• • Markov algorithm

• • Term rewriting

• • String rewriting system

• • L-system

• • Knuth–Bendix completion algorithm

• Star height

• • Star height problem

• • Generalized star height problem

• Cellular automaton

• • Rule 110 cellular automaton

• • Conway's Game of Life

• • Langton's ant

• • Edge of chaos

• Turing machine

• • Deterministic Turing machine

• • Non-deterministic Turing machine

• • Alternating automaton

• • Alternating Turing machine

• • Turing-complete

• • Turing tarpit

• • Oracle machine

• Lambda calculus

• Combinatory logic

• • Combinator

• • • B, C, K, W System

• Parallel computing

• Flynn's taxonomy

• Quantum computer

• • Universal quantum computer

• Church-Turing thesis

• • Recursive function

Decision problems

• Entscheidungsproblem

• Halting problem

• • Correctness

• Post correspondence problem

• Decidable language

• • Undecidable language

• Word problem for groups

• Wang tile

• Penrose tiling

Definability questions

• Computable number

• Definable number

• Halting probability

• Algorithmic information theory

• Algorithmic probability

• Data compression

Complexity theory

• Advice (complexity)

• Amortized analysis

• Arthur–Merlin protocol

• Best and worst cases

• Busy beaver

• Circuit complexity

• Constructible function

• Cook's theorem

• Exponential time

• Function problem

• Linear time

• Linear speedup theorem

• Natural proof

• Polynomial time

• Polynomial-time many-one reduction

• Polynomial-time Turing reduction

• Savitch's theorem

• Space hierarchy theorem

• Speed Prior

• Speedup theorem

• Subquadratic time

• Time hierarchy theorem

Complexity classes

See the list of complexity classes

See the list of complexity classes

查看复杂性类的列表

• Exponential hierarchy

• Polynomial hierarchy

Named problems

• Clique problem

• Hamiltonian cycle problem

• Hamiltonian path problem

• Integer factorization

• Knapsack problem

• Satisfiability problem

• • 2-satisfiability

• • Boolean satisfiability problem

• Subset sum problem

• 3SUM

• Traveling salesman problem

• Vertex cover problem

• One way function

• Set cover problem

• Independent set problem

Extensions

• Probabilistic algorithm, randomized algorithm

• Las Vegas algorithm

• Non-determinism

• Non-deterministic Turing machine

• Interactive computation

• Interactive proof system

• Probabilistic Turing Machine

• Approximation algorithm

• Simulated annealing

• Ant colony algorithm

• Game semantics

• Generalized game

• Multiple-agent system

• Parameterized complexity

• Process calculi

• • Pi-calculus

• Hypercomputation

• Real computation

Computability and complexity

可计算性和复杂性

Category:Theory of computation

类别: 计算理论

Computability

可计算性

Computability

可计算性

This page was moved from wikipedia:en:List of computability and complexity topics. Its edit history can be viewed at 可计算性和复杂性列表/edithistory