A language $L$ is polynomially transformable to $L_0$

122 Views Asked by At

Could someone explain to me the following definition??

A language $L$ is polynomially transformable to $L_0$ if there is a deterministic polynomial-time-bounded Turing machine $M$ which will convert each string $w$ in the alphabet of $L$ into a string $w_0$ in the alphabet of $L_0$, such that $w$ is in $L$ if and only if $w_0$ is in $L_0$.

1

There are 1 best solutions below

0
On

I'll hone in on the concept gradually.

First, it's very useful to be able to reduce one problem to another. The general idea is a standard mathematical technique: we take a problem A we don't understand and reduce it to another problem B we do understand, and in doing so, gain understanding of problem A. So that's a reduction. Indeed, reductionism has a big place in the history of science.

Now in complexity theory, we want to define mathematically what a reduction is and measure how quickly it can be done. Informally, polynomial-time algorithms are "fast", and exponential-time algorithms are "slow". So we want a "fast" way to reduce one problem to another.

What you're describing is what's called a polynomial-time Many-one reduction. This is a particular approach to accomplishing a polynomial-time reduction. So the goal is to map each word in a given language in a "fast" way to a word in another.

These kinds of reductions are very useful. In fact, most of the theory of NP-Completeness is built on reductions.