Cheap and Secure Web Hosting Provider : See Now

[Solved]: Can someone provide a trivial example to the "reduction" procedure used to prove hardness?

, , No Comments
Problem Detail: 

I cannot comprehend how you can prove hardness between two NP complete problems.

For example, let X be a NP hard problem, I want to prove Y is also NP hard.

I can do this by reducing X to Y, if Y is as difficult as X then it is NP hard, otherwise it is not.

But how is this done exactly? Do we restate the problem?

When I looked online it was something about reducing 3 SAT problem to Clique problem, but I don't even know what these problem are.

Is there a trivial example showing how this is done? Thanks!

Asked By : John Swoon

Answered By : Gaste

Let $\Sigma$ and $\Gamma$ be two finite alphabets and $L_A$ and $L_B$ be two languages over $\Sigma$ and $\Gamma$, respectively. A polynomial reduction is a function $f$ from $\Sigma^{\star}$ to $\Gamma^{\star}$, which is computable in polynomial time, such that for all words $x \in \Sigma^{\star}$ it is true that \begin{align} x \in L_A \iff f(x) \in L_B. \end{align}

The function $f$ maps words from one language to words from another language. When speaking of problems, we mean the associated decision problems. Decision problem $A$: Given an word $x \in \Sigma^{\star}$, is it true that $x \in L_A$ (analogous for $B$). Such a word $x \in \Sigma^{\star}$ is also called an instance of the decision problem $A$.

One easy reduction would be the reduction $\mathrm{CLIQUE}$ to $\mathrm{IS}$ (independent set). The languages are defined as follows: \begin{align} CLIQUE = \{ (G, k) \mid \text{the graph $G$ contains a complete subgraph with $k$ vertices} \} \\ IS = \{ (G, k) \mid \text{the graph $G$ contains $k$ vertices, that have no edges between each other} \} \end{align} The complete subgraph in the first definition is called a k-clique and the set of vertices in the second definition is called an independent set.

As you already stated in your question, $\mathrm{3SAT}$ can be reduced to $\mathrm{CLIQUE}$, thus $\mathrm{CLIQUE}$ is NP-hard. For proving that $\mathrm{IS}$ is NP-hard, we reduce $\mathrm{CLIQUE}$ to $\mathrm{IS}$: We map each element $(G, k)$ to $(G', k)$, where $G'$ is the complement graph of $G$ (that means two vertices are connected in $G'$ if and only if they are not connected in $G$). We can compute $G'$ in $\mathcal{O}(|V(G)|^2)$ many steps. If we find a clique $H$ in $G$, all nodes of $H$ are connect with each other in $G$. Thus there is no edge between those nodes in the complement graph $G'$, and therefore the nodes of $H$ are an independent set in $G'$. If we find an independent set $U \subseteq V(G')$ with $k$ elements in $G'$, we know that there is no edge between any of the vertices in $U$ in $G'$. Thus there is an edge between any two vertices of $U$ in $G$, and therefore $G$ contains a k-clique.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35311

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback