NP-Complete Problems

 

NP-Complete Problems

So we have demonstrated that Satisfiability, 3-SAT, Independent Set and Vertex Cover are all NP-Complete. If we can find an efficient solution to any one of them, we can efficiently solve every problem in NP.

This means that if a problem is NP-Complete, it is considered to be a hard problem, because any algorithm for solving it must be able to solve all problems in NP in polynomial time. NP-Complete problems are considered to be the hardest problems in NP, and finding efficient solutions to them is a major open problem in computer science.

In fact there is an enormous, growing number of known NP-Complete problems covering a range of applications from computer science, operations research, mathematics, biology, chemistry and many more subject areas. Even puzzles like tetris, minesweeper and candy crush have been proven NP-Complete.

It's important to note that the fact that a problem is NP-Complete does not mean that it is necessarily difficult to solve in practice. Many NP-Complete problems can be solved relatively efficiently for small input sizes, and there may be efficient heuristics or approximate algorithms that work well for larger input sizes. However, there is no known way to solve NP-Complete problems in polynomial time, so they become increasingly difficult to solve as the input size grows.

We haven’t found a way to solve any of them efficiently - and we’ve had over 40 years to work on it. Neither can we prove that no efficient solution exists!

However, it is important to note that NP-Completeness is not a guarantee that a problem cannot be solved efficiently. It is simply a theoretical result that tells us that if an efficient solution to an NP-Complete problem were to be found, then this would also give us an efficient solution to all other problems in NP. In practice, it is possible that some NP-Complete problems may turn out to have efficient solutions, but this has not yet been demonstrated for any such problem.

Proof techniques

●     Restriction

○     This is the easiest and most common: show that a special case of your problem is NP-complete.

○     A good example is reducing vertex cover to weighted vertex cover.

●     Local Replacement

○     Make a change to each component of your problem so that it becomes an equivalent component of the new problem

○     Example SAT to 3-SAT

●     Component Design

○     The hard way - manufacture components which enforce equivalence between instances

○     Example 3-SAT to Vertex cover

Transformation ○ Convert a known NP-complete problem into your problem. ○ A good example is reducing 3-SAT to independent set. ● Completeness ○ Show that every problem in NP reduces to your problem in polynomial time. ○ This is very rare and is only known for a handful of problems.

To prove that a problem is NP-complete, it is sufficient to show that it is in NP and that it can be reduced to a known NP-complete problem in polynomial time. This is often done by using one of the proof techniques mentioned above. It is also possible to prove that a problem is NP-hard, which means that it is at least as hard as the hardest problems in NP, even if it is not necessarily in NP itself.

Practice

Given that the Hamiltonian cycle problem is NP-Complete

●     Given a graph G = (V,E), is there a cycle which visits each node exactly once (a cycle must return to its starting point)

The Hamiltonian cycle problem is a decision problem that involves determining whether a given graph has a cycle that visits each node exactly once. It is known to be NP-Complete, which means that it is not known whether there is an efficient algorithm for solving the problem. This means that finding a solution to the Hamiltonian cycle problem is equivalent to finding an efficient solution to all of the problems in NP. The Hamiltonian cycle problem is in NP because a "yes" instance of the problem (i.e., a graph with a Hamiltonian cycle) can be verified in polynomial time by using a witness (the cycle itself). However, it is not known whether the problem can be solved in polynomial time, so it is not known whether the Hamiltonian cycle problem is in P. The Hamiltonian cycle problem is not in co-NP, because it does not involve verifying "no" instances of the problem.

Prove the following are also NP-Complete

●     The longest simple cycle problem

○     Given a graph G = (V,E), is there a cycle which visits k nodes or more?

●     The travelling salesman problem

○     You know this one...

To prove that the longest simple cycle problem is NP-Complete, we can use a reduction from the Hamiltonian cycle problem. Given a graph G and an integer k, we can create a new graph G' by adding k-1 new nodes to G and connecting them to all of the nodes in G with edges of length 1. If G has a Hamiltonian cycle, then this cycle must pass through all of the nodes in G, and it will also pass through the k-1 new nodes because they are connected to all of the nodes in G. Thus, G' will have a simple cycle of length k or more. On the other hand, if G' has a simple cycle of length k or more, then this cycle must pass through all of the nodes in G, so G must have a Hamiltonian cycle. This reduction can be done in polynomial time, so the longest simple cycle problem is NP-Complete.

To prove that the traveling salesman problem is NP-Complete, we can use a reduction from the Hamiltonian cycle problem. Given a graph G, we can create a new graph G' by adding a new node s and connecting it to all of the nodes in G with edges of length 1. If G has a Hamiltonian cycle, then we can use this cycle as a solution to the traveling salesman problem in G' by visiting all of the nodes in G and then returning to s. On the other hand, if we have a solution to the traveling salesman problem in G', then this solution must visit all of the nodes in G and return to s, which means that G must have a Hamiltonian cycle. This reduction can also be done in polynomial time, so the traveling salesman problem is NP-Complete.

Moving forward - Optimisation Problems

Optimisation problems involve finding the minimum or maximum value of a function. Consequently they are not in either P or NP as they are not decision problems so they cannot be called NP-Complete.

 

However, if we transform the optimisation problem into an equivalent decision problem by asking whether or not the function has a value greater/less than some constant k, we can prove that this problem is NP-Complete.

However, we can still try to find an efficient solution for them, or we can try to transform them into an equivalent decision problem so that we can use NP-Completeness results to classify them. For example, the traveling salesman problem is an optimization problem that asks for the shortest possible route that visits a given set of locations exactly once and then returns to the starting point. However, we can turn it into a decision problem by asking whether there exists a route with total distance less than a given value k. This decision problem can then be classified using NP-Completeness results. Similarly, the shortest path problem can be transformed into a decision problem by asking whether there exists a path between two nodes with a total distance less than k.

If this proof is successful, the optimisation problem is said to be NP-Hard, which means at least as hard as the hardest NP problems.

To prove that the longest simple cycle problem is NP-Complete, we can use a reduction from the Hamiltonian cycle problem. Given an instance of the Hamiltonian cycle problem, we can create an equivalent instance of the longest simple cycle problem by setting k to be the number of nodes in the graph. If the Hamiltonian cycle problem has a solution (a cycle that visits all nodes in the graph), then the longest simple cycle problem will have a solution (a cycle that visits at least k nodes). On the other hand, if the Hamiltonian cycle problem does not have a solution, then the longest simple cycle problem will not have a solution (because there is no cycle that visits all nodes). Thus, the longest simple cycle problem is NP-Complete.

To prove that the traveling salesman problem is NP-Complete, we can use a reduction from the Hamiltonian cycle problem. Given an instance of the Hamiltonian cycle problem, we can create an equivalent instance of the traveling salesman problem by setting the distance between each pair of nodes to be 1. If the Hamiltonian cycle problem has a solution (a cycle that visits all nodes in the graph), then the traveling salesman problem will have a solution (a route that visits all nodes and has a total distance equal to the number of nodes in the graph). On the other hand, if the Hamiltonian cycle problem does not have a solution, then the traveling salesman problem will not have a solution (because there is no route that visits all nodes). Thus, the traveling salesman problem is NP-Complete.

Bearing this in mind - have a go at proving maximum clique is NP-Hard

To prove that the maximum clique problem is NP-hard, we can use the fact that the clique decision problem (which asks whether a given graph has a clique of size k or greater) is NP-complete. Given a graph G and a value k, the clique decision problem can be solved in polynomial time by simply checking all possible subsets of the vertices in the graph and determining whether any of them form a clique of size k or greater.

To prove that the maximum clique problem is NP-hard, we can show that it is at least as difficult as the clique decision problem. In other words, we can demonstrate that an efficient solution to the maximum clique problem would also allow us to solve the clique decision problem in polynomial time.

To do this, we can start by assuming that we have an efficient algorithm for solving the maximum clique problem. Given a graph G, we can use this algorithm to find the size of the largest clique in the graph. Let this size be k. We can then use the clique decision problem to determine whether there is a clique of size k or greater in the graph. If the clique decision problem returns "yes", then we know that the maximum clique problem has a solution, and we can use the algorithm to find it. If the clique decision problem returns "no", then we know that the maximum clique problem does not have a solution.

Since the clique decision problem is NP-complete, this demonstrates that the maximum clique problem is NP-hard, because we have shown that an efficient solution to the maximum clique problem would allow us to solve the clique decision problem in polynomial time.