NP (Complexity)
by Stephen M. Walker II, CoFounder / CEO
What is NP?
NP (Nondeterministic Polynomial time) is a complexity class in computational theory. It contains decision problems for which a given solution can be verified as correct or incorrect in polynomial time by a deterministic Turing machine. In simpler terms, if you're given a "yes" answer to a problem, you can check that it's correct relatively quickly. But finding that "yes" answer might take a very long time. This contrasts with P (Polynomial time) problems, where solutions can be both found and verified in polynomial time. It's a crucial concept in understanding the P vs NP problem, one of the most fundamental unsolved questions in computer science.
What is the relationship between NP and other complexity classes?
The complexity class NP (Nondeterministic Polynomial Time) is related to several other complexity classes, including P, CoNP, NPhard, and NPcomplete.

P Class — The P class stands for Polynomial Time. It is the collection of decision problems that can be solved by a deterministic machine in polynomial time. If a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem. Hence, P is a subset of NP.

CoNP Class — CoNP stands for the complement of NP Class. If a problem X is in NP, then its complement X’ is also in CoNP. Whether or not NP = coNP is an outstanding question in complexity theory.

NPhard Class — An NPhard problem is at least as hard as the hardest problem in NP. All NPhard problems are not in NP. It takes a long time to check them. This means if a solution for an NPhard problem is given then it takes a long time to check whether it is right or not.

NPcomplete Class — A problem is NPcomplete if it is both NP and NPhard. NPcomplete problems are the hard problems in NP. If one could solve an NPcomplete problem in polynomial time, then one could also solve any NP problem in polynomial time.
The relationship between NP and other complexity classes is an active area of research. Many NPcomplete problems are believed to be not solvable in polynomial time by any deterministic Turing machine, but this has not been proven for all NPcomplete problems. The question of whether P equals NP, known as the P vs NP problem, is one of the most significant open questions in computer science.
What are some NPcomplete problems?
NPcomplete problems are decision problems for which a solution can be verified in polynomial time, and if any one of them can be solved in polynomial time, all problems in NP can be solved in polynomial time. Here are some examples of NPcomplete problems:

Graphs and Hypergraphs:
 1planarity
 3dimensional matching
 Bandwidth problem
 Bipartite dimension
 Capacitated minimum spanning tree
 Route inspection problem (also called Chinese postman problem)
 Clique cover problem
 Clique problem
 Complete coloring
 Cycle rank
 Degreeconstrained spanning tree
 Domatic number
 Dominating set
 Feedback vertex set
 Feedback arc set
 Graph coloring
 Graph homomorphism problem
 Treewidth
 Vertex cover

Mathematical Programming:
 3partition problem
 Bin packing problem
 Bottleneck traveling salesman
 Uncapacitated facility location problem
 Flow Shop Scheduling Problem
 Generalized assignment problem
 Integer programming
 Variations on the Traveling salesman problem
 Vehicle routing problem

Formal Languages and String Processing:
 Closest string
 Longest common subsequence problem over multiple sequences

Other Problems:
 Berth allocation problem
 Betweenness
 Assembling an optimal Bitcoin block
 Boolean satisfiability problem (SAT)
 Circuit satisfiability problem
 Conjunctive Boolean query
 Exact cover problem
 Finding the global minimum solution of a HartreeFock problem
 Upward planarity testing
 Hospitalsandresidents problem with couples
 Knot genus
 Latin square completion
 Maximum 2satisfiability
While solutions to NPcomplete problems can be verified "quickly", there is no known way to find a solution quickly. The time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows.
What are some NPhard problems?
NPhard problems are computational problems that are at least as hard as the hardest problems in NP (nondeterministic polynomial time). If an NPhard problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time. Here are some examples of NPhard problems:

Traveling Salesman Problem: 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?

Knapsack Problem: Given a set of items, each with a weight 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.

Halting Problem: Given a description of a program and a finite input, decide whether the program finishes running or will run forever.

Boolean Satisfiability Problem (SAT): Given a Boolean expression composed of a number of variables, is there a truth assignment to the variables that makes the entire expression true?

Job Scheduling Problem: Given a set of jobs each with a start time, an end time, and a profit, find the most profitable subset of jobs that are compatible with each other.

Subset Sum Problem: Given a set of integers, is there a nonempty subset whose sum is zero?

Integer Partition Problem: Given a number, can it be divided into a sum of prime numbers?

Bin Packing Problem: Given a set of items with different weights, can they be packed into bins such that the total weight in each bin is less than or equal to the bin capacity?

Graph Coloring Problem: Given a graph, assign colors to the vertices so that no two adjacent vertices share the same color.

Vertex Cover Problem: Given a graph, find the smallest set of vertices that cover all the edges in the graph.
Note: While all NPcomplete problems are NPhard, not all NPhard problems are NPcomplete. An NPhard problem is NPcomplete if it is also in NP, meaning that a solution can be verified in polynomial time.
What are some heuristics for solving NPhard problems?
Heuristics are often used to solve NPhard problems, as they can provide approximate solutions in a reasonable amount of time, even though they may not always find the optimal solution. Here are some common heuristics used for NPhard problems:

Greedy Algorithms — These algorithms make the locally optimal choice at each decision point with the hope that these local decisions lead to a globally optimal solution. They are simple, easy to implement, and often provide good approximations for many problems.

Exhaustive Search — This approach involves checking all possible solutions to find the best one. While this can guarantee finding the optimal solution, it is often impractical for large problems due to its high time complexity.

Metaheuristic Algorithms — These are higherlevel heuristics designed to select and modify other heuristics, with the goal of improving their performance. Examples include Genetic Algorithms, Simulated Annealing, and Tabu Search. These methods are often used when the search space is large and complex.

Problemspecific Heuristics — These are heuristics designed specifically for a particular problem. For example, the LinKernighan heuristic (LKH) is a wellknown heuristic for the Traveling Salesman Problem.

Heuristic Algorithms for Scheduling Problems — These are algorithms designed to solve scheduling problems, which are a common class of NPhard problems. They often involve assigning tasks to resources over time.
It's important to note that the effectiveness of a heuristic can vary depending on the specific problem and instance. Therefore, it's often necessary to experiment with different heuristics to find the one that works best for a particular problem.
What is the difference between nphard and npcomplete problems?
The main difference between NPhard and NPcomplete problems lies in their definitions and the types of problems they encompass.

NPhard Problems — A problem is NPhard if every problem in NP can be reduced to it in polynomial time. This means that an NPhard problem is at least as hard as the hardest problems in NP. However, NPhard problems do not necessarily have to be in NP, and they do not have to be decision problems. They could be optimization problems or decision problems. Examples include the Halting problem and the Vertex cover problem.

NPcomplete Problems — A problem is NPcomplete if it is both in NP and NPhard. This means that not only can every problem in NP be reduced to it in polynomial time, but a solution to the problem can also be verified in polynomial time. NPcomplete problems are always decision problems. Examples include determining whether a graph has a Hamiltonian cycle and determining whether a Boolean formula is satisfiable.
All NPcomplete problems are NPhard, but not all NPhard problems are NPcomplete. The distinction is that NPcomplete problems are a subset of NP problems (i.e., their solutions can be verified in polynomial time), while NPhard problems may or may not be in NP.