DOC PREVIEW
MSU CSE 830 - cook

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Nondeterministic Turing Machines and Cook’s Theorem• Turing machine (TM )– Memory is a 1-way infinite tape∗ Each tape cell has a finite capacity (holds one object of type char)∗ There is one tape head, and the only cell that can be read is the one the tapehead is at– Instructions∗ The only instructions available to a TM are reading a character, writing acharacter, moving the tape head one cell to the left or right, and goto instruc-tions– Despite the simplicity of this model, a TM is a general model of computation∗ Church-Turing Thesis: Any algorithm can be expressed as a TM∗ Extended Church-Turing Thesis: Any polynomial-time algorithm can be ex-pressed as a TM that operates in polynomial time· There is ample evidence to support both claims, but no proof is possiblewithout destroying the spirit of the claims· The extended thesis needs to be adapted to handle probabilistic algorithmsand quantum algorithms• Nondeterminism– In most algorithmic models, the next step is always determined∗ A computation can be expressed as a path (sequence of configurations)– In a nondeterministic algorithm, multiple next steps are possible∗ A computation now is expressed as a tree or more generally as a directedacyclic graph– Example: If (a == b) goto (7, 9, or 11) else goto (13 or 15)– Acceptance/rejection of an input by a nondeterministic algorithm∗ A nondeterministic algorithm A accepts an input if there exists an acceptingpath within its computation graph for that input.∗ A nondeterministic algorithm A rejects an input if all paths within its compu-tation graph for that input are rejecting.– Measuring time for a nondeterministic algorithm∗ A nondeterministic algorithm A operates in nondeterministic polynomial timeif the HEIGHT of its computation tree for all inputs of size n is bounded bya polynomial in n.1• NP– The set of decision problems that are solved by some nondeterministic algorithm(TM) that operates in nondeterministic polynomial-time is the class NP– Connection to previous definition of NP∗ One way to think about a nondeterministic algorithm· First guess a polynomial-sized certificate C(I) nondeterministically· Then apply deterministic verification algorithm to all guessed certificates∗ Another way to think about the certificate C(I)· A certificate can be the sequence of choices made by the NTM in acceptinginput I· Given the certificate and the NTM, we can verify that I is accepted by theNTM in deterministic polynomial time.Theorem 1 Let L be a language decided by a deterministic Turing Machine M = (K, Σ, δ, s)which operates within time f(n). Then there exists a deterministic Turing Machine M0which,for any string x, constructs an instance I of CIRCUIT VALUE with the following properties:1. |I| ≤ (f (n))kfor some constant k that depends only on M2. M0produces I within time f (n)k0for some constant k0that depends only on M3. M accepts x if and only if I evaluates to TRUE.Proof:• Define the table T (M, x) of M’s computation on x as follows– T (M, x) has f(n) + 1 rows numbered 0 through f (n)– T (M, x) has f(n) columns numbered 1 through f (n)– The entry in the ithrow and jthcolumn is labeled T (M, x)[i, j].– T (M, x)[i, j] contains two fields as follows:∗ Field one of T (M, x)[i, j] corresponds to the contents of the jthcell of M’swork tape after time step i for 0 ≤ i ≤ f(n) and 1 ≤ j ≤ f (n).∗ Field two of T (M, x)[i, j] takes one of |K| + 1 different values depending onthe location of the tape head of M after the ithtime step of M on input x.· If the tape head is in cell j, this field is set to the state of M after the ithtime step of M on input x.· If the tape head is not in cell j, this field is set to a null state value.– Note M may halt on x in time step t < f (n). In this case, all subsequent rowsduplicate row t.– T (M, x) includes all the relevant information of M’s computation on x.2• How large must each table entry be?– The first field of each table entry can assume at most |Σ| distinct values.– The second field of each table entry can assume at most |K| + 1 distinct values.– Thus each table entry must have size log |Σ|(|K|+1) which is a constant dependentonly on M.• What information can be used to compute T (M, x)[i, j] for i > 0?– T (M, x)[i, j] depends only on T (M, x)[i−1, j−1], T (M, x)[i−1, j], and T (M, x)[i−1, j + 1].– In particular, if the tape head of M is not in cells j − 1 through j + 1 in time stepi − 1, T (M, x)[i, j] = T (M, x)[i − 1, j].• How can T (M, x)[i, j] for i > 0 be computed?– Note T (M, x)[i, j] depends on T (M, x)[i−1, j−1], T (M, x)[i−1, j], and T (M, x)[i−1, j + 1] in exactly the same manner for all i > 0 and 1 < j < f(n) (ignoring sidecolumns).– Thus a single Boolean circuit C can be used to compute T (M, x)[i, j] from T (M, x)[i−1, j − 1], T (M, x)[i − 1, j], and T (M, x)[i − 1, j + 1] for these values of i and j.∗ Need to handle “side table entries” with a slightly modified circuit.– The size of C is a constant dependent only on M .• Costructing the instance (circuit) I– The input gates to the circuit I corresponds to the initial configuration of M’scomputation on x; that is row 0 of table T (M, x)∗ Easily computed from input x– Most of the rest of circuit I is circuit C (or the slightly modified C to handle sideconditions) replicated many times∗ How many copies of circuit C do we need?– Output value∗ Final tree of OR gates that OR together all the field 2’s of the last row of thetable to see if M is in a yes state– I conforms to conditions we demanded∗ What is the size of I?∗ Why are we guaranteed that I is a yes input to CIRCUIT VALUE if and onlyif x is a yes input to L?2Corollary 1 CIRCUIT SAT is NP-complete.Lemma 1 CIRCUIT SAT


View Full Document

MSU CSE 830 - cook

Download cook
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view cook and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view cook 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?