Reduction and completeness Decision problem for language A is reducible to that for language B in time t if 3f:Domain(A)> Domain(B)s.t.V input instance x for A, 1.x∈A台f(x)∈B,and 2. one can compute f(x)in time t(x) Thus to solve A,it is enough to solve B. ▣First compute f(x) Run algorithm for B on f(x). ▣If the algorithm outputs f(x)∈B,then output x∈A. 13Reduction and completeness ◼ Decision problem for language 𝐴 is reducible to that for language 𝐵 in time 𝑡 if ∃𝑓:𝐷𝑜𝑚𝑎𝑖𝑛 𝐴 → 𝐷𝑜𝑚𝑎𝑖𝑛(𝐵) s.t. ∀ input instance 𝑥 for 𝐴, 1. 𝑥 ∈ 𝐴 ⇔ 𝑓 𝑥 ∈ 𝐵, and 2. one can compute 𝑓(𝑥) in time 𝑡 𝑥 ◼ Thus to solve 𝐴, it is enough to solve 𝐵. ❑ First compute 𝑓(𝑥) ❑ Run algorithm for 𝐵 on 𝑓(𝑥). ❑ If the algorithm outputs 𝑓 𝑥 ∈ 𝐵, then output 𝑥 ∈ 𝐴. 13