Reducibility

Overview

A reduction is a way of converting one problem into another in such a way that a solution to the second problem can be used to solve the first problem.

Turing Reductions

An oracle for a language $B$ is an external device that is capable of reporting whether any string $w$ is a member of $B$. An oracle Turing machine is a TM with the additional capability of querying an oracle. We write $M^B$ to describe an oracle Turing machine $M$ with an oracle for language $B$.

A language $A$ is decidable relative to another language $B$ if $A$ is decidable if it has an oracle for $B$. $A$ is Turing reducible to $B$, denoted $A{\le }_{T}B$, if $A$ is decidable relative to $B$.

Suppose $A{\le }_{T}B$. If $B$ is decidable, then $A$ is decidable. If $A$ is undecidable, then $B$ is undecidable.

Mapping Reductions

Let $A$ be a language over $\mathrm{\Sigma }$ and $B$ be a language over $\mathrm{\Gamma }$. A mapping reduction (or many-one reduction) from $A$ to $B$ is a computable function $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$ such that, for all inputs $w$,

If such a function exists, we write $A{\le }_{m}B$.

Polynomial Time

Language $A$ is polynomial time mapping reducible to language $B$ if a polynomial time computable function $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$ exists, where for every $w$,

If such a function exists, we write $A{\le }_m^{P}B$.

Reference Table

The following is a list of languages that are useful for constructing reductions to and from.

Additionally, any regular and context-free language is decidable.