NP (non-deterministic polynomial-time)

NP (non-deterministic polynomial-time) is a complexity class in theoretical computer science that captures the set of decision problems for which a potential solution can be verified efficiently. In other words, NP consists of problems for which solutions can be checked in polynomial time, although finding the solutions themselves may require exponential time.

To understand NP, it is necessary to define the terms "decision problem" and "polynomial time." A decision problem is a computational problem that can be formulated as a yes-or-no question. For example, given a graph, is there a path between two given nodes? Polynomial time refers to the amount of time it takes to solve a problem based on the size of the input. A problem is said to be solvable in polynomial time if the running time of the algorithm that solves it is bounded by a polynomial function of the input size.

Now, NP is an abbreviation for "non-deterministic polynomial-time," where "non-deterministic" refers to a theoretical model of computation that allows for parallel exploration of multiple possibilities. In the context of NP, it means that there exists a non-deterministic algorithm that can solve the problem in polynomial time.

Formally, a language L is in NP if there exists a polynomial-time verifier V such that for every instance x in L, there is a certificate y (also called a witness or proof) that satisfies two conditions: (1) V(x, y) accepts (outputs "yes") if and only if x is in L, and (2) V runs in polynomial time with respect to the length of x.

The certificate y represents a potential solution to the problem, and the verifier V checks whether y is indeed a valid solution for x. The verifier should be able to verify the correctness of y in polynomial time. However, the non-deterministic aspect of NP allows for the existence of multiple possible certificates, and the verifier can choose the one that leads to an accepting outcome if it exists.

To illustrate this concept, let's consider the subset sum problem. Given a set of integers and a target value, the problem asks whether there is a subset of the integers that sums up to the target value. The decision version of this problem can be stated as follows: given a set of integers, is there a subset with a sum equal to the target value?

To show that this problem is in NP, we need to define a verifier. The verifier takes as input a set of integers, a target value, and a subset of integers (the certificate). It checks whether the sum of the integers in the subset equals the target value. If it does, the verifier accepts the input; otherwise, it rejects it. The verifier runs in polynomial time because it iterates through the subset once to calculate the sum, which can be done in polynomial time.

In this case, the subset itself serves as the certificate, and the verifier efficiently verifies whether the subset is a valid solution. If the answer to the decision problem is "yes," there must exist a valid certificate (subset) that satisfies the verifier, proving that the problem is in NP.

It's important to note that being in NP does not necessarily mean that a problem is efficiently solvable. While verifying a solution can be done in polynomial time, finding the solution itself may require exponential time. The class of problems that can be solved in polynomial time is known as P, and it is widely believed that P is a proper subset of NP, meaning there are problems in NP that are not in P.

The relationship between P and NP is a fundamental question in computer science and is closely related to the famous P versus NP problem. This problem asks whether every problem in NP can be solved in polynomial time, effectively collapsing NP into P. While this question remains open, no polynomial-time algorithm has been found for NP-complete problems, a subset of NP problems to which every problem in NP can be reduced in polynomial time.

In conclusion, NP is a complexity class that contains decision problems for which solutions can be verified efficiently. It represents the set of problems that can be solved in polynomial time using a non-deterministic algorithm. While verifying solutions in NP can be done efficiently, finding the solutions themselves is generally believed to require exponential time. The question of whether P equals NP, which asks whether every problem in NP can be solved in polynomial time, remains an unsolved problem in computer science.