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

NP-equivalent

Index NP-equivalent

In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. [1]

13 relations: Black box, Complexity class, Computational complexity theory, Decision problem, Function problem, Integer, NP-completeness, NP-easy, NP-hardness, Optimization problem, Subset, Subset sum problem, Travelling salesman problem.

Black box

In science, computing, and engineering, a black box is a device, system or object which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings.

New!!: NP-equivalent and Black box · See more »

Complexity class

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

New!!: NP-equivalent and Complexity class · See more »

Computational complexity theory

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

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

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: NP-equivalent and Decision problem · 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.

New!!: NP-equivalent and Function problem · 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!!: NP-equivalent and Integer · See more »

NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: NP-equivalent and NP-completeness · See more »

NP-easy

In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP.

New!!: NP-equivalent and NP-easy · See more »

NP-hardness

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

New!!: NP-equivalent and NP-hardness · 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!!: NP-equivalent and Optimization problem · See more »

Subset

In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

New!!: NP-equivalent and Subset · See more »

Subset sum problem

In computer science, the subset sum problem is an important problem in complexity theory and cryptography.

New!!: NP-equivalent and Subset sum 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 and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

New!!: NP-equivalent and Travelling salesman problem · See more »

References

[1] https://en.wikipedia.org/wiki/NP-equivalent

OutgoingIncoming
Hey! We are on Facebook now! »