CS 3350 Automata, Computability, and Formal Languages
Fall 2015, Quiz 2

Name: __________________________________________________________

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:

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?