a function 𝑓:{0,1} ⃰ → {0,1} ⃰ is polynomial-time computable if there is a polynomial time-bounded deterministic Turing machine (DTM) 𝑀 that on input 𝑤 outputs 𝑓(𝑤)

Formal Definition

Let 𝐿1 and 𝐿2 ⊆ {0,1} ⃰ be languages

𝐿1 is polynomial-time reducible to 𝐿2 (written as 𝐿1 ≤_𝑝 𝐿2) if there exists a polynomial-time computable function 𝑓:{0,1} ⃰ → {0,1} ⃰ s.t. 𝑤∈𝐿1 ^_⟺ 𝑓(𝑤)∈𝐿2

• if 𝐿1 ≤_𝑝 𝐿2 and 𝐿2 ∈ P, then 𝐿1 ∈ P
• if 𝐿1 ≤_𝑝 𝐿2 and 𝐿2 ∈ NP, then 𝐿1 ∈ NP
• ≤_𝑝 satisfies reflexive and transitive relations