Fall 2015, Quiz 2

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?