Language and Decision Problem are Equivalent Language A language L is just a subset of (0,1)*,the set of all strings of bits {0,1}*=Un≥0{0,1m Language to Decision Problem Given a bit string x,decide whether x EL 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 5Language 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