Class Note for CMPSCI 601 at UMass(26)
Class Note for CMPSCI 601 at UMass(26)
Popular in Course
Popular in Department
This 24 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(26)
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: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 22 Clizlue TSP INAPPROX exists P appmx algfar n0 8 lt 1 MAX SAT ATSP VerteXCover APPROX same but nat all 8lt I PT As ETSP all 8lt I Knapsac poly in n 18 CMPSCI 601 Interactive Proofs Lecture 22 Il X readonly input nite 039 random bits control H Proof work tape MerlinArthur games MA Babai Decision problem D input string 3 Merlin Prover chooses the polynomiallength string H that Maximizes the chances of convincing Arthur that a is an element of D Arthur Veri er computes the Average value of his possible computations on H as Arthur is a polynomial time probabilistic Turing machine De nition 221 We say that A accepts D iff the follow ing conditions hold 1 If a E D there exists a proof H13 such that A accepts for every random string a Pro A az a 2 Accept 2 1 2 If a g D for every proof H A rejects for most of the random strings a Pro AHa a 2 Accept lt i Any decision problem D E NP has a deterministic polynomial time veri er satisfying De nition 221 By adding randomness to the veri er we can greatly re strict its computational power and the number of bits of H that it needs to look at while still enabling it to accept all of NP We say that a veri er A is r02 qnrestricted iff for all inputs of size n and all proofs H A uses at most Orn random bits and examines at most Oqn bits of its proof H Let PCPrn be the set of boolean queries that are accepted by r01 qnrestricted veri ers Fact 222 PCP Theorem NP 2 PCPlog n 1 The proof of this theorem is pretty messy certainly more than we can deal with here But we can look at the appli cations of the PCP Theorem to approximation problems MAXBSAT given a 3CNF formula nd a truth as signment that maximizes the number of true clauses x1 V932 V927 x1 V324 V927 aT1aTQaT4 x2VaT3VaT4 T2V933V935 V V WVT2WS3 V VUSQ Proposition 223 MAXBSAT has a polynomialtime e 2 approximation algorithm Proof Be greedy set each variable in turn to the better value Q You can do better a random assignment gets 78 of the clauses Open for Years Assuming NP P is there some 6 0 lt e lt 1 st MAXBSAT has no PTIME eapproximation algorithm Theorem 224 The PCP theorem NP 2 PCPlog n 1 is equivalent to the fact that If P 2 NP then Forsome e1gt e gt 0 MAXBSAT has no polynomialtime eapproximation algorithm Fact 225 MAXBSAT has a PTIME approximation al gorithm with e 2 and no better ratio can be achieved unless P 2 NP References 0 Approximation Algorithms for NP Hara Problems Dorit Hochbaum 6d PWS 1997 0 Juraj Hromkovic Algorithmics for Hard Problems Springer 2001 0 Sanjeev Arora The Approximability ofNPhard Prob lems STOC 98 wwwcsprincetoneduNarora CMPSCI 601 Nondeterminism Lecture 22 9 n AAA ooooooooooooowooooooooo tn ValueID E ValueLeftChildID ValueRightChildID weak communication pattern wasteful use of all these processors De nition 226 De ne an alternating Turing machine to be a Turing machine Whose states are divided into two groups the existential states and the universal states Recall that an instantaneous description ID consists of the machine s state worktape contents and head posi tions The notion of when such a machine accepts an input is de ned by induction The alternating Turing ma chine in IDO accepts iff l IDO is in a nal accepting state or 2 IDO is in an existential state and there exists a next ID that accepts or 3 IDO is in a universal state there is at least one next ID and all next ID s accept gtt GOO 000 E A tf1 CMPSCI601 The Game Semantics Lecture 22 What does it mean for a string to be in the language of an alternating TM We sometimes misleadingly say the ATM accepts as just as we might say the NDTM accepts as But this isn t really sensible because we should not talk about what an NDTM or ATM will do only what it might do Language of an NDTM a E N iff N might accept as Equivalently a E N if a smart player who controls N s choices and wants N to accept can make N accept Game Semantics of an ATM There are two players White who controls M in the existential states and wants M to accept and Black who controls M in the universal states and wants M to reject a E M iff White can force M to accept a given optimal play by each player This is equivalent to the de nition of acceptance given on the last slide but I nd it much easier to understand 10 CMPSCI 601 Index Tapes Lecture 22 From now on assume that our Turing machines have a random access readonly input There is an index tape which can be written on and read like other tapes When ever the value h written in binary appears on the index tape the read head will automatically scan bit h bit of the input readonly input w indeXTape workTape 50 gt 11 We can now de ne alternating complexity classes as fol lows ASPACEsn is the set of boolean queries languages accepted by alternating Turing machines that use Osn tape cells on any computation path when the input size is n Similarly ATIMEtn is the set of boolean queries lan guages accepted by alternating TM s that take Otn time steps on any computation path when the input size is n Theorem 227 For 301 2 log n and for tn 2 n 1AT1MEtnk 1DSPACEtnk ASPACEsn E DTIMEkSngt k 1 Corollary 228 In particular ASPACElog n 2 P ATIMEn0lt1gt PSPACE 12 The Alternation Theorem has four parts We must simulate l A timebounded DTM with a spacebounded ATM using the circuit game 2 A spacebounded DTM with a timebounded ATM using the Savitch game 3 A spacebounded ATM with a timebounded DTM using the marking algorithm and 4 A timebounded ATM with a spacebounded DTM using exhaustive search of the game tree First though let s see some examples of alternating ma chines I ll include both classical and gamesemantics descriptions of each machine 13 De ne the monotone circuit value problem MCVP to be the subset of CVP in which no negation gates occur It turns out that MCVP is still Pcomplete Proposition 229 MCVP is recognizable m ASPACElog Proof Let G be a monotone boolean circuit For a E VG de ne EVALa if InputOna then accept if InputOffa then reject if GAa then universally choose child I of a if Gva then existentially choose child I of a ReturnEVALb mthNH M simply calls EVALr EVALa returns accept iff gate a evaluates to one Space used for naming vertices a b 0log Q 14 Game Semantics for this Proof In the Circuit Game we start with a marker at the output gate of a monotone Boolean circuit G On each move the marker moves from the current gate to one of its children one of its inputs For AND gates Black chooses which child to move to and for OR gates White chooses When we reach an input gate marked with a literal White wins the game iff this literal evaluates to true White wants to stay on gates that evaluate to true Black on gates that evaluate to false Whoever is happy with the output gate can always move the marker to stay happy until an input is reached 15 De nition 2210 The quanti ed satis abl l ily problem Q SAT is the set of true formulas of the following form l Q11Q22 QWW For any boolean formula 0 on variables f 0 6 SAT 42gt Emcp E QSAT p g SAT 42gt Vf Ip E QSAT Thus QSAT logically contains SAT and SAT 16 Proposition 2211 QSAT is recognizable m ATIMEn Proof Construct an alternating machine A as follows To evaluate the sentence I E 3x1Va2 Qw c f in an existential state A writes down a boolean value for 321 in a universal state it writes a bit for 322 and so on Next A must evaluate the quanti erfree boolean formula a on these chosen values For each A in a A univer sally chooses which side to evaluate for each V A existentially chooses Thus A only has to read one of the chosen bits 92 and accept iff it is true and occurs positively or false and oc curs negatively A runs in linear time A accepts Cl iff Cl is true Q Game Semantics White picks values for the El vari ables Black for the V variables White wins iff the quanti er free part evaluates to true 17 Theorem 2212 For any 301 2 log n NSPACEsn g ATIMEsn2 g DSPACEsn2 Proof NSPACEsn Q ATIMEsn2 Let N be an NSPACEsn Turing machine Letw be an inputto N n 2 w 6 SUV 42gt C0mpGraphN w E REACH P d as y accepts iff there is a path in CompGraphUV w of length at most 2d from a to y Pday E 32Pd 1az Pd 1zy 1 Existentially choose middle ID z 2 Universally 3231 2 at z AND z y 3 ReturnPd 1 acy W W gtgtTltd 1 0ltdsltngtgt d W gtgt M 0ltltsltngtgt2gt 7 1 7 1 18 Game Semantics for this version of Savitch s Theorem White originally claims that the path from s to t of length at most 250 exists in CompGraphN White ad vances this claim by naming the alleged middle vertex of the alleged path Black picks either the rst half or the second half of the path to challenge The path whose ex istence is disputed is then half the length They continue halving the length of the disputed path each time until they dispute the existence of an edge At this point the player with the correct claim about this edge wins If White s path actually exists White has a winning strat egy that consists of always telling the truth If White is wrong however either the rst or second half of the al leged path must fail to exist and Black has a winning move 19 ATIMEtn g DSPACEtn Let A be an ATIME machine input 11 n 2 CompGraphA 11 has depth Otn and size 200501 A deterministic Turing machine can systematically search this entire andor graph using space This is done by keeping a string of length Otn 0102 0 7k denoting that we are currently simulating step 7quot of A s computation having made choices 01 CT on all of the existential and universal branches up until now The rest of the simulation will report an answer as to whether choices 01 or will lead to acceptance This is done as follows If one of the following conditions holds 1 CT 2 1 or 2 answer yes and step r was existential or 3 answer no and step r was universal then let 0 2 7k and report answer back to the r 1St step Otherwise set 0 2 1 and continue Note that we do not have to store intermediate IDs of the simulation because the sequence 0102 cm uniquely determines which ID of A we go to next Q 20 ATIMEtn g DSPACEtn We evaluate the computation graph of ATIMEt ma chine using tn space to cycle through all possible com putations of A on input 11 The game tree for the machine represents all possible con gurations and moves of the players In effect our al gorithm exhaustively searches every possible path through this tree using space tn to keep track of where in the search it might be One could do this with a very time inef cient recursive algorithm 21 Theorem 2213 ASPACEsn DTIME205 gtgt Proof ASPACEsn g DTIME205 Let A be an ASPACEsn machine Let 11 be an input n 2 CompGraphAw has size g 205n The marking algorithm evaluates this in DTIME WWW gtt i 0SH EA gtj oltsltn 2 We mark the Winner at each point starting from the end con gurations and working backward 22 DTIME205 g ASPACEsn Let M be a DTIME 214500 TM 21 an input n 2 De ne an alternating procedure Ct p a which accepts iff the contents of cell p at time t in M s computation on input 11 is symbol a Inductively Ct H p 1 holds iff the three symbols a1 a0 a1 in tape positions p 1 p p 1 lead to a b in position p in one step of M s computation CL1 a0 a1 b Ct 11 E Ela1a0a1a1a0a1 b Vi E 101C tpiai Space needed is 0log lm 03 Note that M accepts w iff 61274501 1 M1 23 Space 1 2 p n The Time 0 gm11 wg mm L LI 1 ml ltq17w2gt mm L L t a r do 01 t 1 b TUL ltQf7 1gt Ct 11 E 3a1a0a1a1a0a1 b Vi E 101C tpiai Game Semantics At each point in the game the contents of a single cell of the tableau are in dispute Originally this is the bottomleft cell which White claims is accept ing At each move White names the three cells above the current one which must imply the claimed contents of the current one Black then picks one of these three to dispute Note the similarity to the Circuit Game This completes the proof of Theorem 227 Q 24 mm Arlthmetlc H1erarchy W c0re Recursive 139 e re complete Primitive Recursive EXPTIME PSPACE c0NP PolynomialTime Hierarchy complete c0NP NP NP 1 c0NP NP complete quottruly feasiblequot NC NC2 logCFL SAC NSPACE log n 3 DSPACE log n Regular LogarithmicTime Hierarchy 25
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'