Language and Decision Problem are Equivalent anguage A language L is just a subset of [0, 1 *, the set of all strings of bits ☆{0,13=Un≥00,1 Language to Decision Problem Given a bit string x, decide whetherxE L Decision Problem to language Given a Decision Problem Encode all the instances into bit strings The corresponding language contains all the strings of yES" instancesLanguage and Decision Problem are Equivalent Language A language 𝐿 is just a subset of 0,1 ∗ , the set of all strings of bits ❖ 0,1 ∗ = ڂ≤��0 0,1 𝑛 Language to Decision Problem • Given a bit string 𝑥, decide whether 𝑥 ∈ 𝐿 Decision Problem to Language • Given a Decision Problem • Encode all the instances into bit strings • The corresponding language contains all the strings of “YES” instances 5