Complexity Theory

Glossary

definition of np hard problem: a problem H is NP hard, if every problem P in NP is poly time reducible to H. $P \leq_{p} H$

Let’s understand what reduction in complexity class means:

Amartya starts with an example of NP-hard problem: hamiltonian cycle problem: in a graph, if you start at a vertex, you can traverse the whole graph, i.e. visit every vertex and come back to the starting vertex, then your graph has hamiltonian cycle. What we want to prove here is that this problem is an NP-hard problem. We’ll take help of a reduction.

Let’s take another problem: Hamiltonian path: in a graph, you start at any vertex and traverse the whole graph. there is no condition of coming back to the starting point. This problem is an NP problem as the solution is verifiable in linear time < poly time.

Now, we can reduce our problem A to problem B in poly time and, we know problem B is NP-hard problem. thus, this validates our proof that A is also an NP-hard problem.

Reduction: split any vertex in graph G, into two with vertex V’ having all incoming edges and V’’ having all outgoing edges.

$A (G) = B (R (G)) = B (G ’)$

lonerapier.xyz

Explorer

Complexity Theory

References

Graph View

Backlinks