~/ learn/ comp-372/ cards/ Polynomial-time reductions
1 of 6

Define a polynomial-time reduction L₁ ≤ₚ L₂.

Define a polynomial-time reduction L₁ ≤ₚ L₂.

Answer

A polynomial-time computable function f such that for every instance x, x ∈ L₁ iff f(x) ∈ L₂.

f maps instances of L₁ to instances of L₂ in polynomial time and preserves yes/no membership in both directions.

space flip · ← → navigate · esc to exit
NORMAL ~/memra/library/50b0ebf0-80e0-444e-9070-6a0a1607ea20/flashcard utf-8 LF