Automata, Computability, and Formal Languages
1. Formulate Church-Turing thesis. Is it a mathematical theorem? A statement about the physical world?
2. Formulate the current definition of a feasible algorithm. Give two examples explaining why this definition is not perfect:
- an example of an algorithm that is feasible according to this definition but not feasible according to common sense; and
- an example of an algorithm that is feasible from the practical viewpoint but not feasible according to this definition.
3. Define what is a problem from the class NP.
4. Define what it means for a problem to be NP-hard. Give an example
of an NP-hard problem.
5. Can every NP-hard problem be solved by an algorithm?
Can every NP-hard problem be solved by a feasible algorithm?