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?

  • $\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

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.

  • $\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$ – reinierpost 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$ – David Richerby 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$ – reinierpost 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$ – David Richerby 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$ – Uzebeckatrente Aug 1 '19 at 9:58

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

I originally wrote this answer the other way around, which hopefully explains some of the comment threads. My original answer was:

Looking at this question, which says (emphasis mine)

Here is the problem. Given $k,n,T_1,\ldots,T_m$, where each $T_i \subseteq \{1,\ldots,n\}$. Is there a subset $S \subseteq \{1,\ldots,n\}$ with size at most $k$ such that $S \cap T_i \neq \emptyset$ for all $i$? I am trying to reduce this problem to SAT. . . .

It looks like when we reduce problem $A$ to problem $B$, we are claiming that $A$ is at least as complex as $B$.

  • 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$ – David Richerby Oct 23 '14 at 9:10
  • $\begingroup$ That's what got me confused. I didn't read the entire question and assumed it was a typical NP-Completness proof. $\endgroup$ – Kevin Oct 23 '14 at 9:11

Let me give you an example for the better understanding. Range of natural numbers : {1,2,3,.....,n} , where n goes upto +(infinite). Range of Integers : {-n,.....-1,0,1,....,n} , where n goes from -(infinite) to +(infinite). Now, let us consider Natural numbers as N and Integers as Z. Also, N ∩ Z ≠ ∅, for all n+. You know that N ⊆ Z. Hence, all the elements of N are occupied by Z, along with other elements. When complexity of N is over, we use Z. So, Z is more complex than N. Now, looking at your question for two problems, you can be sure now, that problem B is more omplex than problem A. :)

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Oct 23 '14 at 6:05
  • 3
    $\begingroup$ Your example has nothing to do with the question. $\endgroup$ – FrankW Oct 23 '14 at 6:06
  • 3
    $\begingroup$ I don't understand your answer but it seems to have nothing to do with complexity theory. Your conclusion that $B$ is at least as hard as $A$ is correct but I don't see how your argument about $\mathbb{N}$ and $\mathbb{Z}$ relates to that. $\endgroup$ – David Richerby Oct 23 '14 at 9:11
  • $\begingroup$ And note that infinity is not a natural number or an integer, whereas your answer seems to be claiming that it is. $\endgroup$ – David Richerby Oct 23 '14 at 10:14

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.