PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
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:

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)

View style:

Log in to rate this entry.
(view current ratings)

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 2060 times total.

Classification:
AMS MSC68Q05 (Computer science :: Theory of computing :: Models of computation )
 68Q10 (Computer science :: Theory of computing :: Modes of computation )

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)