Automata and Complexity
Automata and Complexity CS 4510
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4510 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 13 views. For similar materials see /class/234141/cs-4510-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Automata and Complexity
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
Cook7s NPCompleteness theorem Legal Windows Let N Q E F 6M 45 qa 4 be a xed ltape nondeterministic Turing machine that runs in time pn a polynomial LetA QUFU A reduction machine takes as input a string w that is an input to N and produces a formula F that simulates N on w that is the formula F is satis able if and only if N accepts w Let w be an input to N Assume that all computation paths of N on w has length t Treat each con guration of N on w as a length t string over A that has as the start and the end symbol De ne a table T with t 3 columns and t 1 rows where each row is a con guration with the rst row being the initial con guration C0 qswlwg Forl lt i lt tl and l lt j lt t2 the ijth window is a 2 X 3 window consisting of the six entries in Tij7 l Tij Tij l Ti lj 7 l Ti lj and Ti lj 1 Such a window is a legal window if it is one of the following 0 State as the center symbol of the top row 7 For all transitions 6p a that includes 4 d L the following are legal windows p a q I d i 7 For all transitions 6p a that includes 4 d R the following are legal windows For all I E F Forallbel b p a bdq 0 State as the rightmost symbol of the top row 7 For all transitions from state p that includes q 7L for whatever symbol read and whatever symbol written the following are legal windows For all 125 6 F c q I 7 For all transitions from state p that includes q d R for whatever symbol read the following are legal windows 5 b p For all 125 6 F c b d 0 State as the leftmost symbol of the top row 7 For all transitions 6p a that includes 7 d L for whatever state it moves to the following are legal windows p a b d c i 7 For all transitions 6p a that includes 4 d R the following are legal windows p a d L c a b c a b c i 7 For all transitions to q 7L from whatever state on whatever symbol read and whatever symbol written abc For all 125 6 F For all c E F o No state in the top row 7 For all abc E F For all abc E F a b q
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'