assignment 2 NP complete problem

NP-COMPLETE PROBLEM

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems. The abbreviation NP refers to "nondeterministic polynomial time."

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. This means that the time required to solve even moderately sized versions of many of these problems can easily reach into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.

Formal definition of NP-completeness

Main article: formal definition for NP-completeness (article P = NP)

A decision problem   is NP-complete if:

1.  is in NP, and

2. Every problem in NP is reducible to   in polynomial time.

 C can be shown to be in NP by demonstrating that a candidate solution to   can be verified in polynomial time.

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1.

A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for  , we could solve all problems in NP in polynomial time.

NP-complete problems

An interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices. Consider these two problems:

• Graph Isomorphism: Is graph G1 isomorphic to graph G2?

• Subgraph Isomorphism: Is graph G1 isomorphic to a subgraph of graph G2?

The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard, but isn't thought to be NP-complete.

Some NP-complete problems, indicating the reductions typically used to prove their NP-completeness

Solving NP-complete Problems

The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:

• Approximation: Instead of searching for an optimal solution, search for an "almost" optimal one.

• Randomization: Use randomness to get a faster average running time, and allow the algorithm to fail with some small probability. Note: The Monte Carlo method is not an example of an efficient algorithm, although evolutionary approaches like Genetic algorithms may be.

• Restriction: By restricting the structure of the input (e.g., to planar graphs), faster algorithms are usually possible.

• Parameterization: Often there are fast algorithms if certain parameters of the input are fixed.

• Heuristic: An algorithm that works "reasonably well" in many cases, but for which there is no proof that it is both always fast and always produces a good result. Metaheuristic approaches are often used.