3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ "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." That doesn't make a whole lot of sense. Reducing X to Y shows that Y is at least as difficult as X. Have you checked the basic definitions and examples in your textbook and/or course notes? $\endgroup$ – David Richerby Dec 15 '14 at 9:28
  • $\begingroup$ At the very least you can read the Wikipedia articles on the subject. Or a textbook if you have that. $\endgroup$ – reinierpost Dec 15 '14 at 9:32
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

First of all It may be a good idea to read about SAT and Clique problems. Quite a good point to start your research in NP problems. I'd suggest investigating SAT-3CNF, as it is a flagship example of an NP-Complete (both NP-Hard and in NP itself) problem.

Now, to show that an NP-Hard problem X can be reduced to Y would indeed prove that Y is NP-Hard too. To do that you need to provide a relation that maps X to Y (so for any example from X this function maps it to an example from Y.) What you basically want to show is that being able to solve Y efficiently, you'd be also able to solve X efficiently. Personally I believe you should start by reading about SAT-3CNF and Independent Set problems - there are some great examples explaining how they are equivalent, and the mapping is pretty intuitive. You may read about them, for example, here.

To answer your last question - I believe dealing with NP problems can be treated as non-trivial itself. Therefore I would recommend to spend just some time with them, get used to them and try to understand them, so that you are not just pointlessly trying to memorize problems and solutions.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.