What Makes a Problem NP-Complete? Core Criteria & Applications
If you have ever attempted to solve crossword puzzles, you will find that it is harder to solve than to verify a solution provided by others. Similarly, proving Mathematical equations by yourself is much harder than verifying the proof provided by others. The general description for this difference is that finding a Mathematical puzzle or proving a mathematical equation requires some creativity, then verifying a solution provided by someone else.
This article discusses several computational complexity theories that are classified in terms of their hardness. We will define P problem, NP problems, NP-complete problem, and NP-hard problems, subset sum problem, Sat problem, Vertex Cover problem, and Hamiltonian path problem.
P and NP Problem
In computational complexity theory, P is a set of decision problems that can be resolved by a deterministic turing machine using polynomial time. P includes several natural problems including the decision of linear programming and determining maximum matching.
On other hand, NP is a set of decision problems that can be resolved by a nondeterministic turing machine using polynomial time. The complexity class of NP in term of N-Time is defined as follows:
NP = \[U_{k \epsilon N}\] N-Time (nk)
Here, N-Time (nk) is a set of decision problems that can be solved by a non-deterministic turing machine in 0 time.
NP Complete Problems
In NP, NP-complete problems are the set of all decision problems whose solutions can be easily verified in polynomial time on a non-deterministic turing machine. A problem P in NP is considered as the NP-complete if all other problems can be converted or minimized into P in polynomial time. Hence, finding productive algorithms for any NP-complete problems implies that productive algorithms can be determined for all NP problems, as any problem related to this group can be converted into a solution to any other problem of such group.
It is not yet confirmed whether any polynomial-time algorithm will be ever found for NP-complete problems and determining whether these problems are manageable or unmanageable remains one of the most important questions in Computer Science.
Hence, while solving NP-complete problems, the best approach is to use a polynomial algorithm to estimate a solution. The answer thus obtained will not certainly be ideal but will be approximately close.
Some NP-complete problems when expressed as a decision are: Hamilton Path Problem, Vertex Cover Problem, Boolean Satisfiability Problem, (SAT), Subset Sum Problem, Travelling Salesman Problem, Clique Problem, Independent Problem, Dominating Problem. In this article, we will cover a few of these problems.
NP Hard Problems
A problem is considered as NP-hard if an algorithm for its solution can be modified to solve NP problems or P problems, as P problems are the subset of NP problems. The easiest example of NP-hard problems is the subset sum problems. A problem that is both NP and NP-hard is considered as NP-complete.
NP-hard problems do not belong to Class NP, but all problems in class NP can be reducible to them. Very rarely, NP-hard problems need the exponential time or even worse. As discussed above, NP-complete problems are a subset of NP-hard problems, and due to this NP-complete problems are sometimes known as NP-hard problems.
It is also said that problems which nowadays are considered as only NP-hard, will be proved to be NP-complete in the future. It is quite sufficient that someone has invented a non-deterministic machine that solves problems in polynomial time.
Subset Sum Problem
In Computer Science, the subset sum problem is a decision problem. The subset sum problem is frequently used to determine the subset of a given set S = (S₁, s₂, s₃...sₙ). Here, the elements of set S are a positive integer in such a way that s’∈S and the sum of the elements of the subset is equivalent to some positive integer X.
A backtracking approach is used to solve the subset sum problems. Here, the implicit tree is a binary tree. The root of the tree is chosen in such a way that no decision is taken yet reserved on any input. Here, we assume that the elements of the set are arranged in ascending order as shown below:
S₁ < s₂ < s₃…< sₙ
The left root node of the tree represents that we have to include S₁ from the set S whereas the right node of the tree represents that we have to execute S₁. Each node retains the total of the partial solution elements. If at any step, the sum is equal to X then it is considered that the search is successful and terminates.
Hence, the dead-end of the tree can be seen only when either of the two inequalities exists:
The sum of S’ is quite large i.e. : s + Si + 1 > X
The sum of S’ is quite small i.e. S’ + \[\sum_{j=i+1}^{n}\] Sⱼ < X
Hamiltonian Path and Hamiltonian Cycle Problem
In graph theory, the Hamiltonian path problem and the Hamiltonian cycle (or Hamiltonian circuit) problem are problems of finding whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex only once) or a Hamiltonian cycle exists in a directed or undirected graph.
A special case of the Hamiltonian cycle problem is the travelling salesman problem obtained by setting the distance between two cities to one if they are adjacent, and verifying that total distance travelled is equivalent to n ( If so, the route is considered as a Hamiltonian circuit, and if no Hamiltonian circuit is found then the shortest route will be longer).
Relation Between Hamiltonian Path Problem And Hamiltonian Cycle Problem
In a single direction, the Hamiltonian path problem for graph A is equivalent to the hamiltonian cycle problem in graph B obtained by adding a new vertex ‘k’ and joining ‘k’ to all the vertices of A. Hence, determining the hamiltonian path problem cannot be significantly lower than the hamilton cycle problem.
In two directions, the Hamiltonian cycle problem for graph A is equivalent to the hamiltonian path problem in a graph B obtained by copying one vertex ‘k’ of A, k’ that is assuming k’ has a similar neighborhood as k, and by summing up the two dummy vertices of degree 1 and joining them with k and k’ respectively.
[Image will be Uploaded Soon]
Vertex Cover Problem
A vertex cover of graph G is a set Vc of vertices in G such that each edge in G has a minimum one of the vertices Vc as an ending point. This implies that each vertex in the graph is touching a minimum of one edge. The vertex cover problem is considered an NP problem because any solutions can be verified in polytime with n² test of all the edges to determine if their endpoints are included in the proposed vertex cover.
The image given below shows the vertex cover. Each of the red vertices in the graph forms the graph’s vertex cover. The set of all red nodes in each graph is touching every edge in the graph.
[Image will be Uploaded Soon]
Minimum Vertex Cover
The vertex covering number also known as minimum vertex cover is the size of the smallest vertex cover of G and is represented as T(G).
Here are some of the examples of minimum vertex cover where the nodes in the minimum vertex cover can be seen in red color.
[Image will be Uploaded Soon]
Determining the smallest vertex is a classical optimization problem and is considered an NP-hard problem. The vertex cover problem was one of Karp's 21 NP-complete problems and is therefore known as a classical NP-complete problem in complexity theory.
SAT Problem
The SAT problem or the Boolean Satisfiability problem is a problem that asks what is the fastest algorithm to tell for a given problem in Boolean Algebra (with an unknown number of variables). In other words, it asks whether the variables of the Boolean Algebra can be continually replaced by the values True or False in such a way that formula evaluates to True. If this is the situation, the formula is satisfactory.
On the other hand, if no such conditions exist, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable.
For example, the function ( “a And Not b”) is not satisfiable because one can determine the values of a = True and b = False which makes ( a And Not b) = True. On the contrary, “a And Not a” is unsatisfiable.
SAT is considered to be the first and the foremost problem that was proven to be NP-complete. This implies that all problems in the class NP, which considers a broad range of natural decision and optimization problems, are at most as difficult to solve as SAT.
There is no known algorithm that can efficiently solve each SAT problem. Also, it is believed that no such algorithm exists. But, this belief has not been proven mathematically.
Facts to Remember
P is a problem that can be resolved using an abstraction computer model known as a deterministic turing machine and generally considered as a polynomial amount of space known as PSPACE.
NP is a problem that can be resolved using an abstraction computer model known as a non- non-deterministic turing machine and generally considered as a non-deterministic -polynomial amount of space known as NPSPACE.
Solved Example
1. Does the graph given below have a Hamiltonian Circuit or Hamiltonian Path?
[Image will be Uploaded Soon]
Solution:
We can see that once we travel to vertex E, then there is no way to leave vertex E, without returning to vertex C. Therefore, there is no possibility of a Hamiltonian circuit. But if we start at vertex E, then we can find different hamiltonian paths such as ECABD and ECDAB.
2. How many Circuits will Complete a graph having 9 Vertices?
A complete graph with 9 vertices will have (9 - 1)! = 8! = 8 ×7 6× 5 × 4 × 3× 2 ×1 = 40320 possible Hamiltonian circuits. Half of the circuits found are duplicates of other circuits but in reverse order, leaving 20,160 unique circuits.
3. Given a set (3, 4,5,6) and X -= 9. Find the Subset using a Backtracking Approach.
Solution:
S = (3, 4,5,6) and X = 9
S’ = (Ө)
The implicit binary tree for a given subset problem is shown below:
[Image will be Uploaded Soon]
The number inside a node is the addition of the partial solution elements at a specific level..
Hence, if the value of the partial solution element sum is equal to the positive integer 'X' then the search will be terminated at that particular time, or it continues if all the possible solutions are required to be obtained.
FAQs on NP-Complete Problems in Maths: Definitions & Easy Examples
1. What does NP stand for in the context of computer science?
In computer science, NP stands for Nondeterministic Polynomial time. It represents a class of decision problems for which a proposed solution can be verified as correct or incorrect in polynomial time by a deterministic Turing machine. This means that while finding the solution might be hard, checking if a given answer is right is relatively easy.
2. What are the two essential properties that define an NP-Complete problem?
A problem is classified as NP-Complete if it satisfies two fundamental conditions:
It belongs to the complexity class NP. This means a potential solution to the problem can be verified for correctness in polynomial time.
It is NP-hard. This means that every other problem in the NP class can be reduced to it in polynomial time. In simpler terms, it is at least as difficult as the hardest problems in NP.
3. What are some classic examples of NP-Complete problems?
There are many well-known NP-Complete problems that appear in various fields. Some classic examples include:
The Travelling Salesman Problem (Decision Version): Given a list of cities and the distances between them, is there a route that visits each city exactly once and has a total length less than a given value 'k'?
The Boolean Satisfiability Problem (SAT): Given a Boolean expression, is there an assignment of TRUE/FALSE values to the variables that makes the entire expression true?
The Subset-Sum Problem: Given a set of integers, is there a non-empty subset whose elements sum to zero?
The Hamiltonian Path Problem: In a given graph, is there a path that visits each vertex exactly once?
4. What is the difference between NP, NP-Hard, and NP-Complete problems?
These terms describe different classes of computational problems based on their difficulty. Here is a clear comparison:
NP (Nondeterministic Polynomial time): This class contains decision problems whose solutions can be verified in polynomial time. It does not mean they can be solved in polynomial time.
NP-Hard: A problem is NP-Hard if every problem in NP can be reduced to it in polynomial time. These problems are at least as hard as the hardest problems in NP. NP-Hard problems do not necessarily have to be in the NP class themselves (e.g., the Halting Problem).
NP-Complete: A problem is NP-Complete if it is both in NP and is NP-Hard. This makes them the most difficult problems within the NP class.
5. What is the famous P versus NP problem?
The P versus NP problem is one of the most significant unsolved problems in computer science and mathematics. It asks whether every problem whose solution can be quickly verified (in polynomial time) can also be quickly solved (in polynomial time). In technical terms, it asks whether the complexity class P (problems solvable in polynomial time) is the same as the complexity class NP. While it is widely believed that P ≠ NP, a formal proof is yet to be discovered.
6. How does one prove that a new problem is NP-Complete?
To prove a new problem (let's call it Problem X) is NP-Complete, you must follow a two-step process:
Show that Problem X is in NP: You must demonstrate that a given solution to Problem X can be verified for correctness in polynomial time.
Show that Problem X is NP-Hard: This is typically done using a polynomial-time reduction. You must choose a known NP-Complete problem (like SAT or 3-SAT) and show that it can be transformed into an instance of Problem X in polynomial time. This proves that Problem X is at least as hard as a known NP-Complete problem.
7. Why is the Shortest Path problem solvable in polynomial time (in P), while the Longest Path problem is NP-Hard?
This is a classic example of how a small change in a problem's definition can drastically alter its complexity. The Shortest Path problem (on graphs with non-negative edge weights) exhibits the 'optimal substructure' property. This means that a shortest path between two vertices contains shortest paths between intermediate vertices. This property allows efficient, greedy algorithms like Dijkstra's algorithm to find the solution in polynomial time. In contrast, the Longest Path problem does not have this property, and no similar efficient algorithm is known. Finding the longest path generally requires exploring an exponential number of possible paths, making it NP-Hard.
8. What are the practical implications of knowing a problem is NP-Complete?
Proving that a problem is NP-Complete has significant practical consequences. It strongly suggests that no efficient, general-purpose algorithm exists to find the exact optimal solution for large inputs. Instead of searching for such an algorithm, computer scientists and engineers focus on alternative strategies, such as:
Approximation Algorithms: These algorithms run in polynomial time and find a solution that is guaranteed to be within a certain factor of the optimal one.
Heuristics: These are clever, problem-specific 'rules of thumb' that often find good solutions quickly but provide no guarantee of optimality.
Solving for Special Cases: Sometimes, a problem that is NP-Complete in its general form can be solved efficiently if certain constraints are applied.
