NP-Complete

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 (n^k)

Here, N-Time (n^k) 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.