NP Completeness

Question 1

What is the Church-Turing Thesis?

Answer 1

Any Algorithm can be expressed as a Turing Machine

Question 2

How would we represent the Turing Machine with the following:

State - (q3)
Tape - abbaca
Head - at position 4

Answer 2

abb(q3)aca

We place the state of the machine before the current position of the head

Question 3

What does the Phi_start condition check in the Cook Levine Theorem?

Answer 3

This checks that the first row of the Turing Machine is as we would expect it to be.

Question 4

What does the Phi_cell condition check in the Cook Levine Theorem?

Answer 4

This checks that each cell in the Turing Machine Tableaux has at least one entry, and at most one entry.

Each possible entry in each possible cell is represented as a variable.

Question 5

What does the Phi_accept condition check in the Cook Levine Theorem?

Answer 5

This checks that the last row in the Turing Machine Tableaux contains a column with the accepting state

Question 6

What does the Phi_move condition check in the Cook Levine Theorem?

Answer 6

This checks that every transition in the Turing Machine Tableaux is a valid one.

It does this by checking that each
transition is consistent with the Turing Machine’s Transition Function