Polynomial time reduction from A to B - B is at least as hard as A

Question

Many times I've heard that if we can reduce problem A to problem B in polynomial time, then the problem B is at least as hard as problem A. How precise is this statement? I believe we should understand it in this way: if A can be poly-time reduced to B, then if there's a poly-time algorithm for B, then it must be there for A.

My point is that A can actually be harder than B (can have higher time complexity, for example O(n^100), compared to B - O(n^4), because the poly-time reduction itself can be time consuming. So the sum of O(n^4) and time needed for reduction could give an algorithm for A that will be O(n^100). So every time I read A is no harder than B in this context is that it's impossible for A to have no polynomial time algorithm while B has one. Is that correct?

nullptr nullptr · Accepted Answer · 2015-02-01T13:29:36

Correct.

In general, I would say that the term 'hard' in this statement corresponds to a complexity class, not to a degree of the polynomial. Or, rather, a 'hardness' of a problem is the minimal complexity class containing this problem.

That is, if A is at least as hard as B, then the minimal complexity class for B is superseded by the minimal complexity class of A.

Polynomial time reduction from A to B - B is at least as hard as A

2 Answers