A polynomial reduction from a problem X to problem Y is a function f:Σ∗→Σ∗ computable in polynomial-time such that: w∈X⟺f(w)∈YX≤pY means X is polynomially reducible to Y