Computability
- What is the difference between an algorithm, a language and a problem?
- Why nondeterminism?
- Are there minimum criteria for a programming language being Turing complete?
- How to show that a function is not computable? How to show a language is not computably enumerable?
- What are common techniques for reducing problems to each other?
- Differences and relationships between randomized and nondeterministic algorithms?