7
$\begingroup$

When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?

$\endgroup$
2
  • 2
    $\begingroup$ I know that this is a very basic question, but I keep on getting it confused, and it would help me out to have it set straight in my mind for good. $\endgroup$
    – Kevin
    Oct 23 '14 at 4:32
  • 1
    $\begingroup$ late comment - but the following way of thinking about it helped me. problem $A$ reduces to problem $B$ literally means that I give you an algorithm to solve problem $A$ through an algorithm to solve problem $B$. This may involve some reduction costs. Then problem $A$ is at most as hard as solving problem $B$ (plus reduction costs). Or problem $B$ is at least as hard as solving problem $A$. I like the former way of saying it rather than the latter. $\endgroup$ Jun 5 at 9:31
8
$\begingroup$

When we reduce $A$ to $B$, we are saying "If I could solve $B$ in some model of computation, then I could solve $A$ in that model, too" (as long as the reduction is sufficiently simple that it can be performed within the relevant model of computation).

This means that $B$ is at least as hard as $A$. But $A$ could be easier – much easier. For example, let $A\in$ P and let $B$ be any EXP-complete problem. Because $B$ is EXP-complete, every problem in EXP reduces to $B$ so, in particular, $A$ reduces to $B$. But we know that $A$ is strictly easier than $B$ by the time hierarchy theorem.

$\endgroup$
5
  • $\begingroup$ This is half the answer. The other half is that the reduction must be 'cheap enough' that the solution method to A obtained has the same complexity as the solution method to B it employs. Only then, you may conclude that B is at least as hard as A. $\endgroup$ Oct 23 '14 at 9:21
  • $\begingroup$ @reinierpost At the time I wrote my answer, I thought that would add extra complication without much expository benefit. But you're right -- it needs to be there. Do you think the edit is clear enough? $\endgroup$ Oct 23 '14 at 10:13
  • $\begingroup$ I think it still misses something like 'as efficiently as' (with the same time or space complexity). Knowing that it can be done at all isn't good enough. $\endgroup$ Oct 23 '14 at 10:46
  • $\begingroup$ @reinierpost I'm folding that into "model of computation". For example, your model of computation might be the nondeterministic polynomially clocked Turing machine. $\endgroup$ Oct 23 '14 at 11:50
  • $\begingroup$ I like to think of this using less-than-or-equal: "A reduces to B" <=> "A ≤ B" <=> "B is at least as hard as A" $\endgroup$ Aug 1 '19 at 9:58
1
$\begingroup$

When we reduce problem $A$ to problem $B$, we are claiming that $B$ is at least as complex as $A$.

$\endgroup$
1
  • 1
    $\begingroup$ Normally, you're trying to prove NP-completeness so you reduce SAT to the problem you're interested in, showing that your problem is at least as hard as SAT. In the question you're linking to, it seems that somebody is trying to use a SAT solver to solve some other problem. So they want to reduce the other problem to SAT, showing that the other problem is no harder than SAT. $\endgroup$ Oct 23 '14 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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