We are working to restore the Unionpedia app on the Google Play Store
OutgoingIncoming
🌟We've simplified our design for better navigation!
Instagram Facebook X LinkedIn

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]

Table of Contents

  1. 16 relations: Black box, Boolean function, Complexity class, Computational complexity theory, Decision problem, Function problem, Integer, NP (complexity), NP-completeness, NP-easy, NP-hardness, On-Line Encyclopedia of Integer Sequences, Optimization problem, Subset, Subset sum problem, Travelling salesman problem.

Black box

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

See NP-equivalent and Black box

Boolean function

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually, or). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic.

See NP-equivalent and Boolean function

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". NP-equivalent and complexity class are complexity classes.

See NP-equivalent and Complexity class

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other.

See NP-equivalent and Computational complexity theory

Decision problem

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

See NP-equivalent and Decision problem

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.

See NP-equivalent and Function problem

Integer

An integer is the number zero (0), a positive natural number (1, 2, 3,...), or the negation of a positive natural number (−1, −2, −3,...). The negations or additive inverses of the positive natural numbers are referred to as negative integers.

See NP-equivalent and Integer

NP (complexity)

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP-equivalent and NP (complexity) are complexity classes.

See NP-equivalent and NP (complexity)

NP-completeness

In computational complexity theory, a problem is NP-complete when. NP-equivalent and NP-completeness are complexity classes.

See NP-equivalent and NP-completeness

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. NP-equivalent and NP-easy are complexity classes.

See NP-equivalent and NP-easy

NP-hardness

In computational complexity theory, a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from L to H. That is, assuming a solution for H takes 1 unit time, Hs solution can be used to solve L in polynomial time. NP-equivalent and nP-hardness are complexity classes.

See NP-equivalent and NP-hardness

On-Line Encyclopedia of Integer Sequences

The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences.

See NP-equivalent and On-Line Encyclopedia of Integer Sequences

Optimization problem

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

See NP-equivalent and Optimization problem

Subset

In mathematics, a set A is a subset of a set B if all elements of A are also elements of B; B is then a superset of A. It is possible for A and B to be equal; if they are unequal, then A is a proper subset of B. The relationship of one set being a subset of another is called inclusion (or sometimes containment).

See NP-equivalent and Subset

Subset sum problem

The subset sum problem (SSP) is a decision problem in computer science.

See NP-equivalent and Subset sum problem

Travelling salesman problem

The travelling salesman problem, also known as the travelling salesperson 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 theoretical computer science and operations research.

See NP-equivalent and Travelling salesman problem

References

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