2
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ $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? $\endgroup$ – xskxzr Jun 12 '18 at 10:02
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$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.

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