patternMinor
When problem A reduces to problem B, which problem is more complex?
Viewed 0 times
problemreducesmorewhenwhichcomplex
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#32219, answer score: 9
Revisions (0)
No revisions yet.