|
|
|
|
Levin reduction
|
(Definition)
|
|
|
If $R_1$ and $R_2$ are search problems and $\mathcal{C}$ is a complexity class then a $\mathcal{C}$ Levin reduction of $R_1$ to $R_2$ consists of three functions $g_1, g_2, g_3\in\mathcal{C}$ which satisfy:
- $g_1$ is a $\mathcal{C}$ Karp reduction of $L(R_1)$ to $L(R_2)$
- If $R_1(x,y)$ then $R_2(f(x),g(x,y))$
- If $R_2(f(x),z)$ then $R_1(x,h(x,z))$
Note that a $\mathcal{C}$ Cook reduction can be constructed by calculating $f(x)$ using the oracle to find $z$ and then calculating $h(x,z)$
$\mathcal{P}$ Levin reductions are just called Levin reductions.
|
"Levin reduction" is owned by Henry.
|
|
(view preamble | get metadata)
Cross-references: oracle, Cook reduction, Karp reduction, functions, complexity class, search problems
There is 1 reference to this entry.
This is version 2 of Levin reduction, born on 2002-09-06, modified 2002-09-06.
Object id is 3427, canonical name is LevinReduction.
Accessed 2434 times total.
Classification:
| AMS MSC: | 68Q05 (Computer science :: Theory of computing :: Models of computation ) | | | 68Q10 (Computer science :: Theory of computing :: Modes of computation ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|