I have three related questions which have been bothering me for a while now...
Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I reduce $A$ to $B$?
If it is possible, can this reduction be done in polynomial time?
Is it even meaningful (having any importance, in terms of complexity analysis) if we have a non-polynomial time reduction?
Help for these questions would be highly solicited!
Thanks in advance!
- Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I reduce $A$ to $B$?
Maybe, maybe not. It depends on what $A$ and $B$ are. I suggest you revise the concept of NP-completeness and bear in mind that every problem in P is also in NP. These will help you understand the situation better and I think you'll be able to answer your question yourself, then.
- If it is possible, can this reduction be done in polynomial time?
Not necessarily. I think when you've figured out part 1, you'll probably be able to figure this one out, too.
- Is it even meaningful (having any importance, in terms of complexity analysis) if we have a non-polynomial time reduction?
If we don't restrict the power of reductions, they're not interesting. Let $A$ be any problem at all and let $B$ also be any problem, except for $\emptyset$ and $\Sigma^*$. We can define a reduction from $A$ to $B$ as follows. Choose any string $y\in B$ and any string $n\notin B$ (think: "yes" and "no"). Now define the function $$f(x)=\begin{cases}y&\text{if }x\in A\\ n&\text{if }x\notin A\,.\end{cases}$$ This is a reduction from $A$ to $B$. It's as hard to compute as $A$ is, which could be in P, NP, quadruply exponential nondeterministic space, uncomputable, or anything else; it's independent of the complexity of $B$. Can you see why we need $B\neq\emptyset$ and $B\neq \Sigma^*$?
So unrestricted reductions aren't really of any interest. However, there are situations in which we consider reductions other than polynomial-time ones. For example, when we study computability (e.g., the undecidability of the halting problem), we usually allow any computable reduction.1 In other contexts, we use reductions that are weaker than polynomial time. There is a perfectly good concept of P-complete problems but, as a consequence of the things I wrote above (can you see why?), it's boring to consider polynomial-time reductions between problems in P. So, typically, we use logspace reductions, there. In fact, we can consider NP-completeness with respect to logspace reductions and, as far as anybody knows, that gives exactly the same class of NP-complete problems. Sometimes, even weaker notions of reductions are used. There are probably also contexts in which it makes sense to use resource-bounded reductions (i.e., not just any computable function) that are more generous than polynomial-time. Maybe if you were studying problems of such high complexity that, say, an exponential-time reduction would still be cheap compared to solving the actual problem.
1. Actually, thinking about it, most of the reductions you'll see in an undergraduate computability course probably can be done in polynomial time, but that's unnecessary detail if all you're trying to work out is "Computable? Yes or no."
