I am trying to grasp this concept of reductions, which has surfaced during my study of NP-completeness.
So, my textbook notes that "if $Q_1$ reduces to $Q_2$, then $Q_1$ is at least as easy as $Q_2$." First of all, this claim seems counterintuitive. If a problem can be "reduced" to a different problem, shouldn't that mean that the original problem was harder than the first?
My second question is, if you know some information about $Q_1$, what similar information can you conclude about $Q_2$? For example, if $Q_1$ can be solved in polynomial time, what can you say about $Q_2$? Vice versa?
Hopefully I explained my problem clearly enough! Thanks in advance!
"$A$ reduces to $B$" means that there's a way to take an instance of $A$ and "easily" turn it into an instance of $B$, so that - if I solve that $B$-instance - I can "easily" turn the answer into a solution to the $A$ instance.
This means that if I had a way to solve $B$, I could "easily" turn it into a way to solve $A$; this is why, intuitively, $B$ is harder than $A$.
For a concrete example: say $A$ is the problem of determining whether a number is prime, and $B$ is the problem of factoring a number completely. Then I can reduce $A$ to $B$ as follows: take a number $n$, factor it completely, and then see if I got at least three factors.
If you try to reduce $B$ to $A$, though, you get stuck. Say you had a magic wand that could tell if a number was prime. How would you use this to factor $n$? Well, first you could tell that $n$ isn't prime - but what then? You still seem to need to search through a lot of numbers to find $n$'s factors (and indeed, it is conjectured that $B$ does not reduce to $A$!).
This should help you see why the problem being reduced is easier than the problem reduced to.
This means the answer to your second question is, "Basically nothing." The only information you can conclude is negative: if $A$ reduces to $B$ and $A$ is not solvable in polynomial time, then neither is $B$. Positive information transfer goes the other way, e.g. if $B$ is solvable in exponential time then so is $A$.