Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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.
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)
