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

Polynomial-time reduction

+ Save concept Saved concepts

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

35 relations: Algorithm, Arthur–Merlin protocol, Complete (complexity), Complexity class, Computational complexity theory, Crossing number (graph theory), Decision problem, Existential theory of the reals, EXPTIME, Graph (mathematics), Graph isomorphism problem, International Symposium on Graph Drawing, Karp's 21 NP-complete problems, L (complexity), Log-space reduction, Many-one reduction, NC (complexity), NL (complexity), NP (complexity), NP-completeness, NP-hardness, P (complexity), P-complete, Polynomial hierarchy, Polynomial transformations, PSPACE, PSPACE-complete, Reduction (complexity), Richard M. Karp, Stephen Cook, Subroutine, Time complexity, Truth table, Truth-table reduction, Turing reduction.

Algorithm

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

New!!: Polynomial-time reduction and Algorithm · 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!!: Polynomial-time reduction and Arthur–Merlin protocol · 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!!: Polynomial-time reduction and Complete (complexity) · See more »

Complexity class

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

New!!: Polynomial-time reduction and Complexity class · See more »

Computational complexity theory

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.

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

Crossing number (graph theory)

In graph theory, the crossing number of a graph is the lowest number of edge crossings of a plane drawing of the graph.

New!!: Polynomial-time reduction and Crossing number (graph theory) · 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!!: Polynomial-time reduction and Decision problem · See more »

Existential theory of the reals

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where F(X_1,\dots X_n) is a quantifier-free formula involving equalities and inequalities of real polynomials.

New!!: Polynomial-time reduction and Existential theory of the reals · 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!!: Polynomial-time reduction and EXPTIME · 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!!: Polynomial-time reduction and Graph (mathematics) · See more »

Graph isomorphism problem

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

New!!: Polynomial-time reduction and Graph isomorphism problem · See more »

International Symposium on Graph Drawing

The International Symposium on Graph Drawing (GD) is an annual academic conference in which researchers present peer reviewed papers on graph drawing, information visualization of network information, geometric graph theory, and related topics.

New!!: Polynomial-time reduction and International Symposium on Graph Drawing · See more »

Karp's 21 NP-complete problems

In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete.

New!!: Polynomial-time reduction and Karp's 21 NP-complete problems · 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!!: Polynomial-time reduction and L (complexity) · 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!!: Polynomial-time reduction and Log-space reduction · See more »

Many-one reduction

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem.

New!!: Polynomial-time reduction and Many-one reduction · 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!!: Polynomial-time reduction and NC (complexity) · 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!!: Polynomial-time reduction and NL (complexity) · See more »

NP (complexity)

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

New!!: Polynomial-time reduction 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!!: Polynomial-time reduction 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!!: Polynomial-time reduction and NP-hardness · 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!!: Polynomial-time reduction and P (complexity) · See more »

P-complete

In complexity theory, the notion of P-complete decision problems is useful in the analysis of both.

New!!: Polynomial-time reduction and P-complete · 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!!: Polynomial-time reduction and Polynomial hierarchy · See more »

Polynomial transformations

In mathematics, a polynomial transformation consists of computing the polynomial whose roots are a given function of the roots of polynomial.

New!!: Polynomial-time reduction and Polynomial transformations · 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!!: Polynomial-time reduction and PSPACE · See more »

PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time.

New!!: Polynomial-time reduction and PSPACE-complete · See more »

Reduction (complexity)

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.

New!!: Polynomial-time reduction and Reduction (complexity) · 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!!: Polynomial-time reduction and Richard M. Karp · 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!!: Polynomial-time reduction and Stephen Cook · See more »

Subroutine

In computer programming, a subroutine is a sequence of program instructions that perform a specific task, packaged as a unit.

New!!: Polynomial-time reduction and Subroutine · 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!!: Polynomial-time reduction and Time complexity · See more »

Truth table

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their logical variables (Enderton, 2001).

New!!: Polynomial-time reduction and Truth table · See more »

Truth-table reduction

In computability theory, a truth-table reduction is a reduction from one set of natural numbers to another.

New!!: Polynomial-time reduction and Truth-table reduction · See more »

Turing reduction

In computability theory, a Turing reduction from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987).

New!!: Polynomial-time reduction and Turing reduction · See more »

Redirects here:

Karp reduction, Polynomial reducibility, Polynomial time equivalent, Polynomial time reduction, Polynomial transformation, Polynomial-time Turing reduction, Polynomial-time equivalent, Polynomial-time many-one reduction.

References

[1] https://en.wikipedia.org/wiki/Polynomial-time_reduction

OutgoingIncoming
Hey! We are on Facebook now! »