Klu raises $1.7M to empower AI Teams  

NP (Complexity)

by Stephen M. Walker II, Co-Founder / CEO

NP stands for "nondeterministic polynomial time," which is a complexity class in computational complexity theory. Problems in NP are those that can be verified by a deterministic Turing machine in polynomial time, meaning that if you're given a proposed solution to a problem, you can determine whether it is correct or not relatively quickly (in polynomial time).

NP is known for its relationship with P, which is the class of problems that can be solved in polynomial time. One of the most famous open problems in computer science is the P vs NP problem, which asks whether every problem that can be verified quickly (in NP) can also be solved quickly (in P). As of my last update, it remains an unsolved question whether P equals NP or not.

What is NP?

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP-complete problems are the hardest problems in NP, and if a polynomial-time algorithm exists for any NP-complete problem, it implies that all problems in NP can be solved in polynomial time. However, no efficient solution algorithms have been found for NP-complete problems, and determining whether these problems are tractable or intractable remains one of the most important questions in theoretical computer science.

What is the relationship between NP and other complexity classes?

The complexity class NP (Non-deterministic Polynomial Time) is related to several other complexity classes, including P, Co-NP, NP-hard, and NP-complete.

  • 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.

  • Co-NP Class: Co-NP 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 = co-NP is an outstanding question in complexity theory.

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

  • NP-complete Class: A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard problems in NP. If one could solve an NP-complete 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 NP-complete problems are believed to be not solvable in polynomial time by any deterministic Turing machine, but this has not been proven for all NP-complete 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 NP-complete problems?

NP-complete 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 NP-complete problems:

  1. Graphs and Hypergraphs:

    • 1-planarity
    • 3-dimensional 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
    • Degree-constrained spanning tree
    • Domatic number
    • Dominating set
    • Feedback vertex set
    • Feedback arc set
    • Graph coloring
    • Graph homomorphism problem
    • Treewidth
    • Vertex cover
  2. Mathematical Programming:

    • 3-partition 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
  3. Formal Languages and String Processing:

    • Closest string
    • Longest common subsequence problem over multiple sequences
  4. 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 Hartree-Fock problem
    • Upward planarity testing
    • Hospitals-and-residents problem with couples
    • Knot genus
    • Latin square completion
    • Maximum 2-satisfiability

While solutions to NP-complete 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 NP-hard problems?

NP-hard problems are computational problems that are at least as hard as the hardest problems in NP (nondeterministic polynomial time). If an NP-hard problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time. Here are some examples of NP-hard problems:

  1. 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?

  2. 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.

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

  4. 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?

  5. 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.

  6. Subset Sum Problem: Given a set of integers, is there a non-empty subset whose sum is zero?

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

  8. 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?

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

  10. Vertex Cover Problem: Given a graph, find the smallest set of vertices that cover all the edges in the graph.

Note: While all NP-complete problems are NP-hard, not all NP-hard problems are NP-complete. An NP-hard problem is NP-complete if it is also in NP, meaning that a solution can be verified in polynomial time.

What are some heuristics for solving NP-hard problems?

Heuristics are often used to solve NP-hard 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 NP-hard problems:

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

  2. 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.

  3. Metaheuristic Algorithms: These are higher-level 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.

  4. Problem-specific Heuristics: These are heuristics designed specifically for a particular problem. For example, the Lin-Kernighan heuristic (LKH) is a well-known heuristic for the Traveling Salesman Problem.

  5. Heuristic Algorithms for Scheduling Problems: These are algorithms designed to solve scheduling problems, which are a common class of NP-hard 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 np-hard and np-complete problems?

The main difference between NP-hard and NP-complete problems lies in their definitions and the types of problems they encompass.

  1. NP-hard Problems: A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. This means that an NP-hard problem is at least as hard as the hardest problems in NP. However, NP-hard 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.

  2. NP-complete Problems: A problem is NP-complete if it is both in NP and NP-hard. 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. NP-complete problems are always decision problems. Examples include determining whether a graph has a Hamiltonian cycle and determining whether a Boolean formula is satisfiable.

All NP-complete problems are NP-hard, but not all NP-hard problems are NP-complete. The distinction is that NP-complete problems are a subset of NP problems (i.e., their solutions can be verified in polynomial time), while NP-hard problems may or may not be in NP.

More terms

What is the Turing test?

The Turing test is a test of a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human. Alan Turing, who proposed the test in 1950, stated that "a computer would deserve to be called intelligent if it could deceive a human into believing that it was human." The test does not check the ability to give correct answers to questions, but rather the ability to gain human approval as a result of its responses.

Read more

What is the branching factor of a tree?

In AI, the branching factor of a tree is the number of children that each node has. A higher branching factor means that each node has more children, and thus the tree is more complex. A lower branching factor means that each node has fewer children, and thus the tree is simpler. The optimal branching factor depends on the specific problem that the AI is trying to solve.

Read more

It's time to build

Collaborate with your team on reliable Generative AI features.
Want expert guidance? Book a 1:1 onboarding session from your dashboard.

Start for free