# Is every reduction function $f \in O(n)$?

I have no detailed questions actually. My question is about a (maybe possible) generalization for reductions.

We defined reduction as following (If I translate a term false please correct me.):

$L_1, L_2 \in \{0,1\}^*$ two languages.

One may reduce the language $L_1$ to $L_2$, if there is a total function:

$f: \{0,1\}^* \rightarrow \{0,1\}^*$ with the following properties:

1. $\forall w\in \{0,1\}^* :w\in L_1 \Leftrightarrow f(w) \in L_2$
2. The function is via a Turing Machine $M_f$ computable.

My question is the following:

If one may can reduce a language to another, then one may can construct a function from a language to another. It means intuitively for me that the reduction function has to go over $|L_1| = n$ operations. Which means that the reduction function is computable in $O(n)$. But I am not sure about any generalization. I mean does it imply that:

$f$ is a reduction function $\Rightarrow f\in O(n)$

• $f$ is computable in $O(n)$ does not mean $f\in O(n)$. In addition, $n=|L_1|$ is a constant (assume $L_1$ is finite), so $O(n)$ is equivalently $O(1)$. I guess you do not mean the reduction function is computable in $O(1)$, so what do you really mean? Jun 12 '18 at 10:02

I'm not sure exactly what you mean. In essentially all interesting cases, $L_1$ is infinite, so you can't say that $|L_1|=n$. Second, the function $f$ is a function from strings to strings, so it doesn't make sense to ask if it's $O(n)$ because $O(\cdot)$ is a class of functions from numbers to numbers.

However, you're most probably asking if all reductions are in $\mathrm{TIME}[O(n)]$, i.e., if they can all be computed in linear time. They can't.

By the time hierarchy theorem, for any $r>s$, there are languages in $\mathrm{TIME}[O(n^r)]$ that are provably not in $\mathrm{TIME}[O(n^s)]$. So, consider any problem $X$ that is P-complete under polynomial-time reductions. We must have $X\in\mathrm{TIME}[O(n^s)]$ for some $s$. By the time hierarchy theorem, there is some langauge $Y\in\mathrm{TIME}[O(n^{s+1})]\setminus\mathrm{TIME}[O(n^s)]$. Since $X$ is P-complete and $Y\in{}$P, there must be some polynomial-time reduction $Y\to X$. However, this reduction cannot run in linear time. If the reduction did run in linear time, there would have to be some $k$ such that it transforms every length-$n$ instance of $Y$ into an instance of $X$ with length at most $kn$ (a function running in linear time can only produce linearly much output). But, then, we would be able to decide $Y$ via the reduction in time $$O(n) + O((kn)^s) = O(n) +O(n^s) =O(n^s)\,,$$ contradicting our choice of $Y\notin\mathrm{TIME}[O(n^s)]$.

Note that, in general, if we're talking about computability rather than complexity, we only care that the reduction is computable – we usually don't care about its time or space complexity at all. However, in other contexts, we do care about linear-time reductions, for example in proving problems hard under the exponential time hypothesis.

$O(n)$ does not appear anywhere in the defintion. Thus the functions are not required to be computable in this time.

I am not sure what you mean by $|L_1| = n$ -- the language will in general be of infinite cardinality.

There are, however, restricted kinds of reductions that additionaly require the reduction function to be of a certain runtime. For example, say you have two languages of quadratic time complexity. Then a reduction of exponential complexity would be of little interest, because it could itself compute things more complex than the languages.

So when you look at languages from a time complexity class $O(g)$, then you normally want the reduction to be in $O(g)$, too. But this must be stated in the defintion.