Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 
New! Keep your concepts! » Create account

Computational complexity theory

+ Save concept Saved concepts

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. [1]

158 relations: AC (complexity), Adjacency list, Adjacency matrix, Age of the universe, Alan Turing, Algorithm, ALL (complexity), Alphabet (formal languages), Alternating Turing machine, Analysis of algorithms, Arthur–Merlin protocol, Best, worst and average case, Big O notation, Binary number, Biology, Bit array, Blum axioms, Blum's speedup theorem, Boolean circuit, Boolean satisfiability problem, Boris Trakhtenbrot, BPP (complexity), BQP, Cambridge University Press, Cellular automaton, Cengage Learning, Church–Turing thesis, Circuit complexity, Clay Mathematics Institute, Co-NP, Cobham's thesis, Combinatorics, Communication complexity, Complement (complexity), Complete (complexity), Complexity, Complexity class, Computability theory, Computational problem, Computer, Connectivity (graph theory), Context of computational complexity, Conway's Game of Life, Counting problem (complexity), Decision problem, Decision tree model, Descriptive complexity theory, Deterministic algorithm, Discrete logarithm, DSPACE, ..., DTIME, Euclidean algorithm, Eugene M. Luks, EXPSPACE, EXPTIME, Formal language, FP (complexity), Function problem, Gabriel Lamé, Game complexity, General number field sieve, Graph (mathematics), Graph isomorphism, Graph isomorphism problem, Graph theory, Hamiltonian path problem, Hisao Yamada, Integer, Integer factorization, Integer programming, Interactive proof system, Intractability, Introduction to Automata Theory, Languages, and Computation, Introduction to the Theory of Computation, IP (complexity), Jack Edmonds, John Myhill, John Wiley & Sons, Knapsack problem, L (complexity), Lance Fortnow, László Babai, Leonid Levin, Linear bounded automaton, List of complexity classes, List of computability and complexity topics, List of important publications in theoretical computer science, List of unsolved problems in computer science, Log-space reduction, Logic gate, Logistics, Manuel Blum, Mathematics, Milan, Millennium Prize Problems, Minimax, MIT Press, Model of computation, Multiplication, NC (complexity), NEXPTIME, NL (complexity), Non-deterministic Turing machine, Nondeterministic algorithm, NP (complexity), NP-completeness, NP-hardness, NP-intermediate, NSPACE, NTIME, Operations research, Optimization problem, P (complexity), Parallel computing, Parameterized complexity, Partial function, Polynomial hierarchy, Polynomial-time reduction, PP (complexity), Presburger arithmetic, Primality test, Probabilistic Turing machine, Probability distribution, Promise problem, Proof complexity, Protein structure prediction, PSPACE, Pure mathematics, QMA, Quantum algorithm, Quantum complexity theory, Quantum Turing machine, Quicksort, Random-access machine, Randomized algorithm, Raymond Smullyan, Richard M. Karp, RP (complexity), RSA (cryptosystem), Savitch's theorem, Sharp-P, Shor's algorithm, Space hierarchy theorem, Springer Science+Business Media, Stephen Cook, String (computer science), Structural complexity theory, Symmetric Turing machine, Symposium on Theoretical Aspects of Computer Science, Theoretical computer science, Theory of computation, Time complexity, Time hierarchy theorem, Transcomputational problem, Travelling salesman problem, Turing machine, Vertex cover, ZPP (complexity). Expand index (108 more) »

AC (complexity)

In circuit complexity, AC is a complexity class hierarchy.

New!!: Computational complexity theory and AC (complexity) · See more »

Adjacency list

In graph theory and computer science, an adjacency list representation of a graph is a collection of unordered lists, one for each vertex in the graph.

New!!: Computational complexity theory and Adjacency list · See more »

Adjacency matrix

In mathematics, computer science and application areas such as sociology, an adjacency matrix is a means of representing which vertices (or nodes) of a graph are adjacent to which other vertices.

New!!: Computational complexity theory and Adjacency matrix · See more »

Age of the universe

In physical cosmology, the age of the universe is the time elapsed since the Big Bang.

New!!: Computational complexity theory and Age of the universe · See more »

Alan Turing

Alan Mathison Turing, OBE, FRS (23 June 1912 – 7 June 1954) was a British pioneering computer scientist, mathematician, logician, cryptanalyst, theoretical biologist, and marathon and ultra distance runner.

New!!: Computational complexity theory and Alan Turing · See more »

Algorithm

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed.

New!!: Computational complexity theory and Algorithm · See more »

ALL (complexity)

In computability and complexity theory, ALL is the class of all decision problems.

New!!: Computational complexity theory and ALL (complexity) · See more »

Alphabet (formal languages)

In formal language theory, a non-empty set is called alphabet when its intended use in string operations shall be indicated.

New!!: Computational complexity theory and Alphabet (formal languages) · See more »

Alternating Turing machine

In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.

New!!: Computational complexity theory and Alternating Turing machine · See more »

Analysis of algorithms

In computer science, the analysis of algorithms is the determination of the amount of resources (such as time and storage) necessary to execute them.

New!!: Computational complexity theory and Analysis of algorithms · See more »

Arthur–Merlin protocol

In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too).

New!!: Computational complexity theory and Arthur–Merlin protocol · See more »

Best, worst and average case

In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.

New!!: Computational complexity theory and Best, worst and average case · See more »

Big O notation

In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.

New!!: Computational complexity theory and Big O notation · See more »

Binary number

In mathematics and digital electronics, a binary number is a number expressed in the binary numeral system, or base-2 numeral system, which represents numeric values using two different symbols: typically 0 (zero) and 1 (one).

New!!: Computational complexity theory and Binary number · See more »

Biology

Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, evolution, distribution, and taxonomy.

New!!: Computational complexity theory and Biology · See more »

Bit array

A bit array (also known as bitmap, bitset, bit string, or bit vector) is an array data structure that compactly stores bits.

New!!: Computational complexity theory and Bit array · See more »

Blum axioms

In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions.

New!!: Computational complexity theory and Blum axioms · See more »

Blum's speedup theorem

In computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions.

New!!: Computational complexity theory and Blum's speedup theorem · See more »

Boolean circuit

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for digital logic circuits.

New!!: Computational complexity theory and Boolean circuit · See more »

Boolean satisfiability problem

In computer science, the Boolean Satisfiability Problem (sometimes called Propositional Satisfiability Problem and abbreviated as SATISFIABILITY or SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.

New!!: Computational complexity theory and Boolean satisfiability problem · See more »

Boris Trakhtenbrot

Boris (Boaz) Avraamovich Trakhtenbrot (Борис Авраамович Трахтенброт; born 19 February 1921 in Brichevo, northern Bessarabia) or Boaz (Boris) Trakhtenbrot (בועז טרכטנברוט) is an Israeli and Russian mathematician in mathematical logic, algorithms, theory of computation and cybernetics.

New!!: Computational complexity theory and Boris Trakhtenbrot · See more »

BPP (complexity)

In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances.

New!!: Computational complexity theory and BPP (complexity) · See more »

BQP

In computational complexity theory, BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

New!!: Computational complexity theory and BQP · See more »

Cambridge University Press

Cambridge University Press (CUP) is the publishing business of the University of Cambridge.

New!!: Computational complexity theory and Cambridge University Press · See more »

Cellular automaton

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling.

New!!: Computational complexity theory and Cellular automaton · See more »

Cengage Learning

Cengage Learning, Inc. is an educational content, technology, and services company for the higher education and K-12, professional and library markets worldwide.

New!!: Computational complexity theory and Cengage Learning · See more »

Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis ("thesis") about the nature of computable functions.

New!!: Computational complexity theory and Church–Turing thesis · See more »

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them.

New!!: Computational complexity theory and Circuit complexity · See more »

Clay Mathematics Institute

The Clay Mathematics Institute (CMI) is a private, non-profit foundation, based in Providence, Rhode Island.

New!!: Computational complexity theory and Clay Mathematics Institute · See more »

Co-NP

In computational complexity theory, co-NP is a complexity class.

New!!: Computational complexity theory and Co-NP · See more »

Cobham's thesis

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n-bit instance of the problem as input, can produce a solution in time O(nc), where c is a constant that depends on the problem but not the particular instance of the problem.

New!!: Computational complexity theory and Cobham's thesis · See more »

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

New!!: Computational complexity theory and Combinatorics · See more »

Communication complexity

The notion of communication complexity was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob).

New!!: Computational complexity theory and Communication complexity · See more »

Complement (complexity)

In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.

New!!: Computational complexity theory and Complement (complexity) · See more »

Complete (complexity)

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.

New!!: Computational complexity theory and Complete (complexity) · See more »

Complexity

There is no absolute definition of what complexity means; the only consensus among researchers is that there is no agreement about the specific definition of complexity.

New!!: Computational complexity theory and Complexity · See more »

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.

New!!: Computational complexity theory and Complexity class · See more »

Computability theory

Computability theory, also called recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

New!!: Computational complexity theory and Computability theory · See more »

Computational problem

In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might be able to solve.

New!!: Computational complexity theory and Computational problem · See more »

Computer

A computer is a general-purpose device that can be programmed to carry out a set of arithmetic or logical operations automatically.

New!!: Computational complexity theory and Computer · See more »

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other.

New!!: Computational complexity theory and Connectivity (graph theory) · See more »

Context of computational complexity

In computational complexity theory and analysis of algorithms, a number of metrics are defined describing the resources, such as time or space, that a machine needs to solve a particular problem.

New!!: Computational complexity theory and Context of computational complexity · See more »

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.

New!!: Computational complexity theory and Conway's Game of Life · See more »

Counting problem (complexity)

In computational complexity theory and computability theory, a counting problem is a type of computational problem.

New!!: Computational complexity theory and Counting problem (complexity) · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.

New!!: Computational complexity theory and Decision problem · See more »

Decision tree model

In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is considered to be basically a decision tree, i.e., a sequence of branching operations based on comparisons of some quantities, the comparisons being assigned the unit computational cost.

New!!: Computational complexity theory and Decision tree model · See more »

Descriptive complexity theory

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

New!!: Computational complexity theory and Descriptive complexity theory · See more »

Deterministic algorithm

In computer science, a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.

New!!: Computational complexity theory and Deterministic algorithm · See more »

Discrete logarithm

In mathematics, a discrete logarithm is an integer k solving the equation, where b and g are elements of a finite group.

New!!: Computational complexity theory and Discrete logarithm · See more »

DSPACE

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine.

New!!: Computational complexity theory and DSPACE · See more »

DTIME

In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine.

New!!: Computational complexity theory and DTIME · See more »

Euclidean algorithm

. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION.

New!!: Computational complexity theory and Euclidean algorithm · See more »

Eugene M. Luks

Eugene Michael Luks (born circa 1940) is an American mathematician and computer scientist, a professor emeritus of computer and information science at the University of Oregon.

New!!: Computational complexity theory and Eugene M. Luks · See more »

EXPSPACE

In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. (Some authors restrict p(n) to be a linear function, but most authors instead call the resulting class ESPACE.) If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem.

New!!: Computational complexity theory and EXPSPACE · See more »

EXPTIME

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know and also, by the time hierarchy theorem and the space hierarchy theorem, that so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are.

New!!: Computational complexity theory and EXPTIME · See more »

Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols that may be constrained by rules that are specific to it.

New!!: Computational complexity theory and Formal language · See more »

FP (complexity)

In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.

New!!: Computational complexity theory and FP (complexity) · See more »

Function problem

In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO.

New!!: Computational complexity theory and Function problem · See more »

Gabriel Lamé

Gabriel Léon Jean Baptiste Lamé (22 July 1795 – 1 May 1870) was a French mathematician who contributed to the theory of partial differential equations by the use of curvilinear coordinates, and the mathematical theory of elasticity.

New!!: Computational complexity theory and Gabriel Lamé · See more »

Game complexity

Combinatorial game theory has several ways of measuring game complexity.

New!!: Computational complexity theory and Game complexity · See more »

General number field sieve

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 100 digits.

New!!: Computational complexity theory and General number field sieve · See more »

Graph (mathematics)

In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links.

New!!: Computational complexity theory and Graph (mathematics) · See more »

Graph isomorphism

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is generally called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.

New!!: Computational complexity theory and Graph isomorphism · See more »

Graph isomorphism problem

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

New!!: Computational complexity theory and Graph isomorphism problem · See more »

Graph theory

In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

New!!: Computational complexity theory and Graph theory · See more »

Hamiltonian path problem

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).

New!!: Computational complexity theory and Hamiltonian path problem · See more »

Hisao Yamada

was a Japanese computer scientist, known for his influential contributions to theoretical computer science, as well as for the development of Japanese keyboard layouts, a challenging practical problem.

New!!: Computational complexity theory and Hisao Yamada · See more »

Integer

An integer (from the Latin ''integer'' meaning "whole")Integer 's first, literal meaning in Latin is "untouched", from in ("not") plus tangere ("to touch").

New!!: Computational complexity theory and Integer · See more »

Integer factorization

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.

New!!: Computational complexity theory and Integer factorization · See more »

Integer programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers.

New!!: Computational complexity theory and Integer programming · See more »

Interactive proof system

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.

New!!: Computational complexity theory and Interactive proof system · See more »

Intractability

Intractable is an adjective describing high complexity, which makes it difficult to change, manipulate, or resolve an issue.

New!!: Computational complexity theory and Intractability · See more »

Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation.

New!!: Computational complexity theory and Introduction to Automata Theory, Languages, and Computation · See more »

Introduction to the Theory of Computation

Introduction to the Theory of Computation (ISBN 0-534-95097-3) is a standard textbook in theoretical computer science, written by Michael Sipser and first published by PWS Publishing in 1997.

New!!: Computational complexity theory and Introduction to the Theory of Computation · See more »

IP (complexity)

In computational complexity theory, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system.

New!!: Computational complexity theory and IP (complexity) · See more »

Jack Edmonds

Jack R. Edmonds (born April 5, 1934) is an American computer scientist, regarded as one of the most important contributors to the field of combinatorial optimization.

New!!: Computational complexity theory and Jack Edmonds · See more »

John Myhill

John R. Myhill, Sr. (11 August 1923 – 15 February 1987) was a British mathematician.

New!!: Computational complexity theory and John Myhill · See more »

John Wiley & Sons

John Wiley & Sons, Inc., also referred to as Wiley, is a global publishing company that specializes in academic publishing and markets its products to professionals and consumers, students and instructors in higher education, and researchers and practitioners in scientific, technical, medical, and scholarly fields.

New!!: Computational complexity theory and John Wiley & Sons · See more »

Knapsack problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

New!!: Computational complexity theory and Knapsack problem · See more »

L (complexity)

In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of memory space.

New!!: Computational complexity theory and L (complexity) · See more »

Lance Fortnow

Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems.

New!!: Computational complexity theory and Lance Fortnow · See more »

László Babai

László (Laci) Babai (born July 20, 1950 in Budapest) from Babai's web site, retrieved 2010-07-30.

New!!: Computational complexity theory and László Babai · See more »

Leonid Levin

Leonid Anatolievich Levin (Леони́д Анато́льевич Ле́вин; Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist.

New!!: Computational complexity theory and Leonid Levin · See more »

Linear bounded automaton

In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine.

New!!: Computational complexity theory and Linear bounded automaton · See more »

List of complexity classes

This is a list of complexity classes in computational complexity theory.

New!!: Computational complexity theory and List of complexity classes · See more »

List of computability and complexity topics

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

New!!: Computational complexity theory and List of computability and complexity topics · See more »

List of important publications in theoretical computer science

No description.

New!!: Computational complexity theory and List of important publications in theoretical computer science · See more »

List of unsolved problems in computer science

This article is a list of unsolved problems in computer science.

New!!: Computational complexity theory and List of unsolved problems in computer science · See more »

Log-space reduction

In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.

New!!: Computational complexity theory and Log-space reduction · See more »

Logic gate

In electronics, a logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more logical inputs, and produces a single logical output.

New!!: Computational complexity theory and Logic gate · See more »

Logistics

Logistics is the management of the flow of things between the point of origin and the point of consumption in order to meet requirements of customers or corporations.

New!!: Computational complexity theory and Logistics · See more »

Manuel Blum

Manuel Blum (Caracas, 26 April 1938) is a Venezuelan computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

New!!: Computational complexity theory and Manuel Blum · See more »

Mathematics

Mathematics (from Greek μάθημα máthēma, “knowledge, study, learning”) is the study of topics such as quantity (numbers), structure, space, and change.

New!!: Computational complexity theory and Mathematics · See more »

Milan

Milan (or; Milano; Milanese: Milan), the second-most populous city in Italy, serves as the capital of Lombardy.

New!!: Computational complexity theory and Milan · See more »

Millennium Prize Problems

The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000.

New!!: Computational complexity theory and Millennium Prize Problems · See more »

Minimax

Minimax (sometimes MinMax or MM) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario.

New!!: Computational complexity theory and Minimax · See more »

MIT Press

The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States).

New!!: Computational complexity theory and MIT Press · See more »

Model of computation

In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs.

New!!: Computational complexity theory and Model of computation · See more »

Multiplication

Multiplication (often denoted by the cross symbol "×", by a point "·" or by the absence of symbol) is one of the four elementary, mathematical operations of arithmetic; with the others being addition, subtraction and division.

New!!: Computational complexity theory and Multiplication · See more »

NC (complexity)

In complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.

New!!: Computational complexity theory and NC (complexity) · See more »

NEXPTIME

In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2n O(1) and unlimited space.

New!!: Computational complexity theory and NEXPTIME · See more »

NL (complexity)

In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

New!!: Computational complexity theory and NL (complexity) · See more »

Non-deterministic Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

New!!: Computational complexity theory and Non-deterministic Turing machine · See more »

Nondeterministic algorithm

In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.

New!!: Computational complexity theory and Nondeterministic algorithm · See more »

NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.

New!!: Computational complexity theory and NP (complexity) · See more »

NP-completeness

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard.

New!!: Computational complexity theory and NP-completeness · See more »

NP-hardness

NP-hardness (''n''on-deterministic ''p''olynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP".

New!!: Computational complexity theory and NP-hardness · See more »

NP-intermediate

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI.

New!!: Computational complexity theory and NP-intermediate · See more »

NSPACE

In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine.

New!!: Computational complexity theory and NSPACE · See more »

NTIME

In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time O(f(n)).

New!!: Computational complexity theory and NTIME · See more »

Operations research

Operations research, or operational research in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions.

New!!: Computational complexity theory and Operations research · See more »

Optimization problem

In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions.

New!!: Computational complexity theory and Optimization problem · See more »

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes.

New!!: Computational complexity theory and P (complexity) · See more »

Parallel computing

Parallel computing is a form/type of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved at the same time.

New!!: Computational complexity theory and Parallel computing · See more »

Parameterized complexity

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input.

New!!: Computational complexity theory and Parameterized complexity · See more »

Partial function

In mathematics, a partial function from X to Y (written as) is a function, for some subset X′ of X.

New!!: Computational complexity theory and Partial function · See more »

Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

New!!: Computational complexity theory and Polynomial hierarchy · See more »

Polynomial-time reduction

In computational complexity theory, a polynomial-time reduction is a method of solving one problem by means of a hypothetical subroutine for solving a different problem (that is, a reduction), that uses polynomial time excluding the time within the subroutine.

New!!: Computational complexity theory and Polynomial-time reduction · See more »

PP (complexity)

In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances.

New!!: Computational complexity theory and PP (complexity) · See more »

Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929.

New!!: Computational complexity theory and Presburger arithmetic · See more »

Primality test

A primality test is an algorithm for determining whether an input number is prime.

New!!: Computational complexity theory and Primality test · See more »

Probabilistic Turing machine

In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution.

New!!: Computational complexity theory and Probabilistic Turing machine · See more »

Probability distribution

In probability and statistics, a probability distribution assigns a probability to each measurable subset of the possible outcomes of a random experiment, survey, or procedure of statistical inference.

New!!: Computational complexity theory and Probability distribution · See more »

Promise problem

In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs.

New!!: Computational complexity theory and Promise problem · See more »

Proof complexity

In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce.

New!!: Computational complexity theory and Proof complexity · See more »

Protein structure prediction

Protein structure prediction is the prediction of the three-dimensional structure of a protein from its amino acid sequence — that is, the prediction of its folding and its secondary, tertiary, and quaternary structure from its primary structure.

New!!: Computational complexity theory and Protein structure prediction · See more »

PSPACE

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

New!!: Computational complexity theory and PSPACE · See more »

Pure mathematics

Broadly speaking, pure mathematics is mathematics that studies entirely abstract concepts.

New!!: Computational complexity theory and Pure mathematics · See more »

QMA

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic complexity class NP or the probabilistic complexity class MA.

New!!: Computational complexity theory and QMA · See more »

Quantum algorithm

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation.

New!!: Computational complexity theory and Quantum algorithm · See more »

Quantum complexity theory

Quantum complexity theory is a part of computational complexity theory in theoretical computer science.

New!!: Computational complexity theory and Quantum complexity theory · See more »

Quantum Turing machine

A quantum Turing machine (QTM), also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer.

New!!: Computational complexity theory and Quantum Turing machine · See more »

Quicksort

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

New!!: Computational complexity theory and Quicksort · See more »

Random-access machine

In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines.

New!!: Computational complexity theory and Random-access machine · See more »

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

New!!: Computational complexity theory and Randomized algorithm · See more »

Raymond Smullyan

Raymond Merrill Smullyan (born May 25, 1919) is an American mathematician, concert pianist, logician, Taoist philosopher, and magician.

New!!: Computational complexity theory and Raymond Smullyan · See more »

Richard M. Karp

Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley.

New!!: Computational complexity theory and Richard M. Karp · See more »

RP (complexity)

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

New!!: Computational complexity theory and RP (complexity) · See more »

RSA (cryptosystem)

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission.

New!!: Computational complexity theory and RSA (cryptosystem) · See more »

Savitch's theorem

In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity.

New!!: Computational complexity theory and Savitch's theorem · See more »

Sharp-P

In computational complexity theory, the complexity class #P (pronounced "number P" or, sometimes "sharp P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP.

New!!: Computational complexity theory and Sharp-P · See more »

Shor's algorithm

Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994.

New!!: Computational complexity theory and Shor's algorithm · See more »

Space hierarchy theorem

In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions.

New!!: Computational complexity theory and Space hierarchy theorem · See more »

Springer Science+Business Media

Springer Science+Business Media or Springer is a global publishing company that publishes books, e-books and peer-reviewed journals in science, technical and medical (STM) publishing.

New!!: Computational complexity theory and Springer Science+Business Media · See more »

Stephen Cook

Stephen Arthur Cook, (born December 14, 1939) is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity.

New!!: Computational complexity theory and Stephen Cook · See more »

String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

New!!: Computational complexity theory and String (computer science) · See more »

Structural complexity theory

In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms.

New!!: Computational complexity theory and Structural complexity theory · See more »

Symmetric Turing machine

A symmetric Turing machine is a Turing machine which has a configuration graph that is undirected (that is, configuration i yields configuration j if and only if j yields i).

New!!: Computational complexity theory and Symmetric Turing machine · See more »

Symposium on Theoretical Aspects of Computer Science

Symposium on Theoretical Aspects of Computer Science (STACS) is an academic conference in the field of computer science.

New!!: Computational complexity theory and Symposium on Theoretical Aspects of Computer Science · See more »

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics that focuses on more abstract or mathematical aspects of computing and includes the theory of computation.

New!!: Computational complexity theory and Theoretical computer science · See more »

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

New!!: Computational complexity theory and Theory of computation · See more »

Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

New!!: Computational complexity theory and Time complexity · See more »

Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines.

New!!: Computational complexity theory and Time hierarchy theorem · See more »

Transcomputational problem

In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information.

New!!: Computational complexity theory and Transcomputational problem · See more »

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

New!!: Computational complexity theory and Travelling salesman problem · See more »

Turing machine

A Turing machine is an abstract "machine" that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model that defines such a device.

New!!: Computational complexity theory and Turing machine · See more »

Vertex cover

In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.

New!!: Computational complexity theory and Vertex cover · See more »

ZPP (complexity)

In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

New!!: Computational complexity theory and ZPP (complexity) · See more »

Redirects here:

Asymptotic complexity, Calculation complexity, Complexity of algorithms, Complexity theory (computation), Complexity theory in computation, Computational complexity analysis, Computational intractability, Computational intractablity, Computationally efficient, Computationally infeasible, Computationally intractable, Continuous complexity theory, Efficient procedure, Efficiently-computable, Feasible computability, Feasible computation, Hierarchy theorem, Input size, Intractability (complexity), Intractable problem, Intractableness, Intractably, Levin reduction, Order of complexity, Order of computation, Space complexity theory.

References

[1] https://en.wikipedia.org/wiki/Computational_complexity_theory

OutgoingIncoming
Hey! We are on Facebook now! »