0
$\begingroup$

Given two problems A and B.

Given two algorithms a' and b'. a' solves A and b' solves B.

If A reduces to B and B reduces to A.

Then can we say anything about a' and b'? Are they the same?

$\endgroup$
2
$\begingroup$

A reduction can be thought of a way to "rephrase" a problem in terms of another. This can be denoted using $A \to B$, $A$ reduces to $B$. This means that if you have an algorithm that solves $B$ then you also have an algorithm that solves $A$, since $A$ reduces to $B$, $A \to B$. Now you also have $B \to A$ so in some way, your problems are equivalent since they can be reduced to each other.

However, this does not imply much about the algorithms themselves because they can be arbitrarily bad. For example, the sorting problem has time complexity $O(n \log n)$. But an awful algorithm that sorts by testing all possible permutations has time complexity $O(n!)$.

The only thing we can say is that the algorithms aren't better (their time complexity isn't lower than) the problems themselves.

$\endgroup$
0
$\begingroup$

What do you want to say about $a'$ and $b'$? They can't possibly be the same algorithm unless $A=B$, since one of them solves $A$ and the other one doesn't. Even if $A=B$, they're not necessarily the same algorithm: if there's one algorithm that solves some problem, there are infinitely many (your favourite algorithm; count to two and then do your favourite algorithm; count to three and...).

It's so obvious that $a'$ and $b'$ are different except in trivial cases that having to ask the question suggests that you've misunderstood something, but I'm not sure what, so I can't be more helpful at the moment.

$\endgroup$

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.