# NP-hard proof: Polynomial time reduction

As I understand, to show that a certain problem $$P$$ is NP-hard we can reduce a known NP-hard problem $$Q$$ to a problem in $$P$$. This reduction, say $$f$$, has to be polynomial time.

Could someone please explain is it necessary that $$f$$ maps each instance of $$q\in Q$$ to $$P$$ or can we map a selected subset of $$\tilde Q \subseteq Q$$ to $$P$$? i.e. does pre-image of $$f$$ has to be be all of $$Q$$ or can it be a subset of $$Q$$?

Thanks

• It's really confusing to call a problem $P$ and have the slightly different typesetting being the only thing that distinguishes the problem $P$ from the complexity class P. – David Richerby Jan 7 at 12:56

Yes and no. To cut a long story short, it's enough that the pre-image of $f$ is NP-hard.

Intuitively, the point of NP-hardness is that, if you had an efficient algorithm for an NP-hard problem, then you would have an efficient algorithm for all problems in NP. Let's suppose you've come up with a new problem, Triomphe's Problem (TP), and you want to prove that it's NP-hard. You need to show that every problem in NP can be reduced to TP. There are, on the face of it, two ways of doing this.

The direct way. Show that there is a polynomial-time computable function $f$ with the following property: for any nondeterministic polynomial-time Turing machine $M$ and every input $x$, $f(M,x)$ is an instance of TP and $f(M,x)$ is a "yes" instance of TP if, and only if, $M$ accepts $x$. This is how Cook proved NP-completeness of Boolean satisfiability and how Fagin proved NP-completeness of evaluation of formulas of existential second-order logic.

The indirect way. Show that there is an NP-hard problem $P$ and a polynomial-time computable function $f$ with the following property: for any instance $x$ of $P$, $f(x)$ is an instance of TP and it is a "yes" instance of TP if, and only if, $p$ is a "yes" instance of $P$. This is how just about every other NP-hard problem, apart from the two listed above, was proven NP-hard.

The indirect way works through a chain of reductions. We need to establish that every problem in NP can be reduced to TP. So, we start with our nondeterministic polynomial-time Turing machine $M$ and its input $x$. We convert that to an instance of Boolean satisfiability. Then we convert that into, say, an instance of 3-SAT. Then we convert that into, say, an instance of 3-colourability. Then maybe we convert that into an instance of $P$ and, finally, convert that into an instance of our fictional problem TP. Because all of these reductions work for every instance of the problem, we have a reduction from our generic NP problem to TP.

Both in theory and in practice, that is how reductions are done: you need to translate every instance of the problem. But we don't actually need that much. Look at the first step of the chain of reductions in the previous paragraph. We started with any Turing machine at all, and we converted it into a Boolean formula. Without looking closer, all we know is that we've produced some Boolean formula, and we don't know any details about it. However, looking more closely at the reduction, we see that the formula is in conjunctive normal form (CNF) (or that the proof can easily be modified to make it so). For the next step, converting to 3-CNF, the definition of reductions tells us that we have to be able to translate every Boolean formula into one in 3-CNF, but we know we don't need to do that much. It would suffice to translate only the formulas that are already in conjunctive normal form, because those are the only ones that the translation from Turing machines will produce. And that's actually what the standard proof does.

Normally, when a new problem is proven NP-hard, a full reduction is given from some known NP-hard problem to the new problem, which translates all instances. However, in principal, you could get away with a reduction that does less than that, as long as it covers enough instances to establish the chain back to the generic Turing machine $M$ and its input $x$. To give another example, 3-colourability is NP-hard because of a standard reduction from 3-SAT. You could prove a new problem to be NP-hard by a reduction that only translates the instances of 3-colourability that could be produced by that reduction from 3-SAT. This works because 3-colourability is already NP-hard when its input is restricted to be from the class of graphs that can arise from the reduction from 3-SAT.

However, if you're a student doing exercises and exam questions, I'd recommend that you always produce reductions that map the whole problem, rather than just a subset of it.

• Thanks a lot. I need some clarification, if you please. If we reduce from MAX-SAT to say, TP, can we restrict the number of Boolean clauses in the MAX-SAT problem to be less than or equal to the number of Boolean variables (assuming more than 3 Boolean variables)? I am thinking this is ok since 3-SAT is NP-complete just with one Boolean clause. So as long as I have a MAX-SAT problem with more than 3 Boolean variables and at least 1 Boolean clause as in the form of 3-SAT problem (CNF with 3 variables) that MAX-SAT problem is NP-hard. Could you please say if this argument is correct? – Mat Dec 24 '13 at 14:31
• I don't understand what you mean by "3-SAT is NP-complete with just one Boolean clause"? What do you mean by "Boolean clause"? All clauses are disjunctions of Boolean variables and 3-SAT certainly isn't NP-complete with just one clause. – David Richerby Dec 24 '13 at 14:39
• Sorry I confused clause with formula. By clause I mean the Boolean formula e.g., $(x_1\lor x_2 \lor x_3)\land (x_1\lor x_4\lor x_5)...$ So 3-SAT is just one formula like this (clause in my comment) So if I make a MAX-SAT problem even with 2 formulas having more than 3 variables in each clause that set of MAX-SAT problems can accommodate all of SAT problems right? Thanks – Mat Dec 24 '13 at 15:03
• Could you please say if it is correct now? – Mat Dec 24 '13 at 17:50

I'm not sure I understood you. But I believe you wanted to ask the following question:

Assuming I have NPH problem $Q$, we usually refer it as a language/set. For example, the set of all the tuples $(G,k)$ such that $G$ is a graph and it has a vertex cover of size $k$.

To prove that a problem $P$ is NPH, it is enough to prove that given input $q$ to some NPH problem $Q$, you can map it in polynomial time (the mapping is the polynomial reduction function) to some input $p$ for the problem $P$, such that set of $q\in Q$ if and only if $p\in P$.

For example $Q$ as the vertex cover NPH problem, for every input to $Q$, a graph $G$ and integer $k$, you can map it in polynomial time to some input for the problem $P$, such that $q\in Q$ if and only if $p\in P$.

This proves that $P$ is also NPH, because if it is not, and you have polynomial time reduction, you can easily build a deterministic polynomial time algorithm that will solve the original NPH problem.

If you reduction is only from some subset of the inputs for the NPH problem, it won't work - because you cannot build deterministic polynomial time algorithm for $Q$, given the reduction and a deterministic algorithm that solves P in polynomial time.

(In my answer I assume the P != NP. Otherwise, for problems like VC, there is already a deterministic polynomial time algorithm)

• Be careful. In your fifth paragraph, you claim a proof of something, based on the non-existence of polynomial-time algorithms for NP-hard problems. We don't know that $P\neq NP$ so it's possible that there are polynomial-time algorithms for NP-hard problems! – David Richerby Dec 24 '13 at 12:17
• I will add a clarification to my answer. – Gari BN Dec 24 '13 at 13:39
• OK but the concept of reductions and completeness still make sense even if $P=NP$. The intuition that there's no polynomial-time algorithm for an NP-complete problem because then there'd have to be a polynomial-time algorithm for all NP-complete problems is fine as intuition but you shouldn't try to hang proofs off it. – David Richerby Dec 24 '13 at 13:43