Related

Complexity

As a course

Exercises

Language, Algorithm, and Problem

(Chomsky hierarchy) Computational complexity of problem

• $\Sigma$: alphabet, a finite set of symbols
• String: a finite sequence of symbols over alphabet
• $\Sigma^*=\text{set of all strings}$
  • Kleene star: $A^*:=\cup_{n \ge 0} A^n$
  • $A^+:=\cup_{n \ge 1} A^n=AA^*$
• Language $L \subset \Sigma^*$
  • For problem X, the corresponding language $L=\{ w | w=encode(y) \text{,where y is an input with answer “Yes” to problem X}\}$.