### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# THEORY OF COMPUTATION CS 215

UCR

GPA 3.88

### View Full Document

## 23

## 0

## Popular in Course

## Popular in ComputerScienence

This 6 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 215 at University of California Riverside taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/231746/cs-215-university-of-california-riverside in ComputerScienence at University of California Riverside.

## Reviews for THEORY OF COMPUTATION

### 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: 10/29/15

C8215 REVIEW EXERCISES not graded Problem 1 problem 715 Let UNARYSSUM be the subsetsum problem in which all numbers are represented in unaryi That is each number k is encoded as a string of h 17s a Show that UNARYSSUM is in P b Why does the NPcompleteness proof for SUBSETSUM in the book fail to show UNARYSSUM is NP cornplete Be speci c as you can about what is wrong with the content of the reduction Don7t just say for example because UNARYSSUM is in P so if the reduction was correct we would know that PNP and we don7t know that a The standard dynamic programming algorithm for subset sum runs in time bounded by a polynomial in the size of the input and T the target when T is integer See httpwwwcsucredu neal2004cs141indezcgiSubsetSumByDP If the input is in unary then here is a polytime algorithm 1 Check the sum of the numbers is at least the target T 2 If not reject 5 Otherwise run the standard dynamic programming algorithm You can verify that the algorithm is correct and runs in time polynomial in the size of the input b Because the reduction is not polynomialtime The numbers are of size around 2 so writing them out in unary takes exponential time Problem 2 a problem 717 Prove using the de nitions of P NP and NPcomplete that if PNP then each language L in P except the languages 2 and 0 is NPcornpletei b Prove formally that 0 is not NPcomplete according to the de nition of NPcomplete a Suppose PNP Let L be any language in P To show L is NPcomplete we need to show I L is in NP and any language L in NP reduces to L in polytime I Since L is in P L is in NP because PQNP 2 Let L be a language in NP Since we are assuming PNP L is in P So there is a polytime machine M that decides L Since L is neither 0 nor 2 there is a z E L and a 1 g L Here is the reduction f from L to L On input w 1 Run M on w Ifw accepts output 1 Otherwise output 1 The reduction is polynomialtime because M is You can verify that the reduction is correct That is Vww E L 42gt E L b f0 were NPcomplete there would be a reduction f from SAT to 0 Let F be any satis able formula For the reduction to be correct we would have to have E 0 But there is nothing in 0 so this is impossible Problem 3 problem 724 De ne D pzl 12 zngt p is a polynomial over variables 11 12 In and pc1c2 cn 0 for some c1c2 cn E N That is D contains the InultiVariable polynomials that have integer rootsi a Show that D is NPhard Hint 0 iff 0 or gz 0 while gz2 0 iff 0 and gz 0 b What speci cally is wrong with the following proof that D is in NP Here is a veri er for Di Vltpx1 l l l xngtc ll Interpret c as a vector c1 c2 l l l cn of integers 2 If pc1c2 l l l cn 0 acceptl Clearly step 1 and 2 can be evaluated in polynomial time and clearly D 3c Vltpgtc acceptsl Thus D has a polynomialtime veri er and is in NP a We reduce SSAT to it Given a Boolean formula F in 3cnf construct a polynomial P as follows For each Boolean variable xv in F have a variable Xv in P Next construct a set S of polynomials over the variables Xv as follows For each variable Xv add a polynomial Xv l 7 Xv to the set S For each clause C in F add a corresponding polynomial to the set For example if C x1 x2 A73 then add the polynomial X1X2l 7 X3 to the set S Finally de ne polynomial p Eq ms 42 Clearly this reduction is polytime Next we verify its correctness Suppose F is satis able Fix a satisfying assignment For each xv that is assigned true assign value 0 to the corresponding variable Xv in F For each xv that is assigned false assign value 1 to the corresponding variable Xv in F Then every polynomial in the set S has value 0 Each variable polynomial Xvl 7 Xv does because Xv 6 01 Each clause polynomial such as X1X2l 7 X3 has value 0 because one of the terms has value 0 Thus the polynomial p has value 0 lt Suppose p has an integer root that is a way of assigning an integer to each variable Xv so that p takes value 0 Fix such an assignment Since p has value 0 and p Eq ms 42 it follows that each polynomial in S also has value 0 Since there is a polynomial Xv l 7 Xv in S for each variable v it follows that each variable Xv must be assigned 0 or 1 If Xv 0 then take xv true If Xv 1 then take xv false For each clause in F there is a corresponding polynomial in S that takes value 0 From this fact it is easy to verify that one of the literals in the clause must have value true under the assignment above Thus F is satis ed by the assignment b The problem is that the integer roots may be arbitrarily large so that the size of the certi cate is not bounded by a polynomial in the size of D Thus the described veri er does not run in poly time Problem 4 problem 726 See the book Answer postponed until after hwk redo s are turned in on Wednesday Problem 5 problem 734 A legal coloring of a graph is an assignment of colors to the nodes so that no two adjacent nodes sharing an edge are assigned the same color De ne SCOLOR graph G can be legally colored With three colors Show that SCOLOR is NPcomplete For a hint see the problem statement in the book Here is a reduction from NAES SAT from Papadimitriou s book The input to NAES SAT is a Boolean formula F in 3cnf form a set of clauses C1C2HlCm each with three literals The question is whether there is an assignment to the variables that makes each clause have at least one true literal and at least one false literal For the reduction we produce the following graph G For each variable Ii make a triangle a Here a is a node shared among all triangles for all variables For each clause Ci we make another triangle C11 Gig C13 Here Cij represents the jth literal in the clause Finally there is an edge from each Cij to the corresponding node in the variable triangle for the literal Clearly the reduction is polytime We prove the formula F is NAE satis able C is 3colorable Suppose F has an assignment of values to the variables that makes every clause have at least one true literal and at least one false literal We will use the colors gray green and red Color node a gray For each variable triangle a Ii 1 if z is true in the assignment then color 1 green and f red Otherwise color 1 red and f green For each clause triangle Ci1C2Ci3 Color a Cij corresponding to a true literal red color a Cij corre sponding to a false literal green and color the remaining Cij gray It is easy to verify that this gives a legal 3coloring lt Suppose C has a legal 3coloring By renaming the colors we can assume that a is colored gray and each node is colored either gray green or red For each variable triangle a 133 either I is red and f is green or z is green and f is red In the former case set 1 false In the latter case set 1 true Now consider any clause Ci and consider the coloring of the clause triangle C11 C12 C13 These three nodes have to be colored di erent colors so there is at least one red node and at least one green node Since these nodes have edges to their corresponding literals in the variable triangles those three variables must have one that is not red which must be green so that its variable is true and one that is not green which must be red so that its variable is false Thus the assignment gives at least one true and one false literal to each clause Problem 6 problem 729 Show that if SAT is in P then there exists a polynomialtime algorithm that given any satis able Boolean formula zlzgi l l In outputs a satisfying assignment that is it outputs c1 c2 l l c7 6 true false such that 45c1l l l cn truei Hint SAT being in P means that there is a polynomialtime algorithm A that given any 45 outputs yes if 45 is satis able and no otherwisei But A doesn7t tell you the assignment Use A to construct a polytime algorithm A that calls A several times and uses the answers to nd an assignment Suppose SAT is in P Let A be a polytime algorithm that given a Boolean formula F tells whether it is satis able Then the following algorithm produces a satisfying assignment there is one in polytime 1 Use A to check ifF is satis able If not return 2 Pick a variable 1 Substitute true for z in F Simplify the result to obtain formula F without variable 5 Use A to check whether F is satis able 4 If F is then assign z the value true 5 Otherwise assign z the value false and take F to be the formula obtained from F by substituting false for z in F 6 Recurse to nd an assignment for the remaining variables that satis es F Problem 7 problem 733 What is Wrong With the following proof that Pa NP Here is an algorithm for SAT On input 45x1 i i i xn try every possible assignment c of true or false to the n variablesi If any assignment c satis es 45 ie true accept else rejecti77 This algorithm clearly requires exponential time Thus SAT has exponential time complexity Therefore SAT is not in P Because SAT is in NP we conclude that P7 NPi To prove that SAT requires exponential time we would have to show that all algorithms for SAT take expo nential time or worse All we ve shown is that this particular algorithm takes exponential time Problem 8 Recall that EQCFG Gl G2gt G1 and G2 are contextfree grammars With LG1 LG2i a problem 52 Prove EQCFG the complement of EQCFG is Turing recognizablei b problem 51 Prove EQCFG is undecidablei c Prove using a and that EQCFG is not Turing recognizable a Here is a TM that recognizes EQCFG On input G1 G2 1 Dovetail over all words w E 2 looking for a word w such that w 6 G1 but w g G2 or vice versa 2 If you nd such a word accept To dovetail means the following 1 for i 123 do 2 forjl2wi do 5 Spendi time units trying to nd out 6 G1 but w g G2 or vice versa If there is any word w that meets the condition then eventually it will be found b Recall Theorem 510 ALLCFG is undecidable Here is a reduction from ALLCFG to EQCFG 1 On input G output G G where LG 2 Then lt C gt6 ALLCFG gtlt 00 gt6 EQcpg By the reduction if EQCFG were decidable then ALLCFG would be too c Recall from a the complement of EQCFG is Turing recognizable It EQCFG were also Turing recognizable then they would both be decidable Theorem 416 Problem 9 problem 55 Prove that ATM is not mapping reducible to ETM From the de nition of mapping reducibility a language A mapping reduces to B then A mapping reduces to B by the same reduction So ifATM was mapping reducible to ETM then m would be mapping reducible to Since the latter language is Turing recognizable the former would be too But we know it is not That is ATM is not Turing recognizable We know this from Theorem 416 and the fact that ATM is Turing recognizable but not decidable Problem 10 problem 59 De ne a language B to be Turing complete if B is Turing recognizable and for every Turing recognizable language A A mapping reduces to El Show that ATM is Turing complete We have to show that for any Turing recognizable language L there exists a computable function f such that for all w E 2 w E L 42gt 6 ATM But this is easy take lt Mw gt where M is the recognizer for L verify that w E L 42gt 6 ATM Problem 11 a problem 518 De ne BINARYPCP to be the PCP problem restricted to pairs of binary strings lnput A collection of pairs ai bi each aibi E 0 Query ls there a sequence of indices i1 i2 ik such that ailai2 aik bilbi2 b 7 ik Show that BINARYPCP is undecidable Hint reduce PCP over the alphabet used in the book to it b problem 517 De ne UNARYPCP to be the PCP problem restricted to pairs of unary strings strings over the alphabet E lnput A collection of pairs aibi each aibi E Query As above Show that UNARYPCP is decidable a Given an instance ai of the general PCP problem over an arbitrary alphabet 2 construct an instance of BINARYPCP as follows Let E c1c2 ck For each ci de ne a corresponding string ai Oli Then for each ai construct a by replacing each character c in ai by its corresponding 1 as described above Likewise for each bi de ne bg Then ab is an instance of PCP over alphabet 01 We claim the above is a mapping reduction from PCP to BINARYPCP Clearly the reduction is computable It is easy to see that if aibi has a match then so does ab We leave verifying the other direction to the reader b We claim that the UNARYPGP instance has a match if and only there are pairs ab and a b where M 2 w and w s M This condition is easily checked by a TM Clearly the condition is not true then there can be no match Either all tops are larger than their bottoms or all tops are smaller than their bottoms On the other hand if the condition is true then consider taking some i copies of the domino a b andj copies of the domino ab The number of symbols on the top is then ila l jlal while the number on the bottom is ilbl jlbl Takingi lal 7 lbl andj lbl 7 la l we get the top and the bottom have the same number of symbols and ij 2 0 Thus there is a match Problem 12 Describe With proof a polynomialtime reduction from FlNlTETM to REGULARTM Where FlNlTETM M is a TM and LM is nite REGULARTM M is a TM and LM is regular Here is the reduction Given lt M gt construct the following TM M On input w 1 Ifw is of the form Onl where there exists w E LM with length lw l n then acceptquot Given M the encoding lt M gt can be output in time polynomial in IfLM is nite then LM is nite and hence regular On the other hand if LM is in nite it is not hard to verify that LM is not regular because it is an in nite subset of Onl We can easily prove by the pumping lemma that such a language is not regular Thus lt M gt6 FINITETM ltgtlt M gt6 REGULARTM Thus this is a polynomialtime reduction Problem 13 Give an example of a language that is a in P but not regular Answer Onln b in NP but not NP complete Answer 0 c decidable but not in NP and prove it Answer In fact we show something stronger De ne EXPTIME to be the set of languages decidable in exponential time That is L is in EXPTIME i there is a constant c gt 0 and a Turing machine M that decides L in time 2 on inputs of size We will construct a decidable language that is not in EXPTIME Since EXPTIME contains NP this is enough We construct such a language by diagonalization against all EXPTIME languages Let A be a Turing machine that recognizes ATM De ne the following Turing machine D On input lt M gt 1 Say a state s of M is useless if there are no transitions into s and s is not the start state Compute the number c of useless states Note we are using useless states to encode a constant c in the TM description 2 LetnlltMgtl 4 Simulate M on input lt M gt for 27f steps 5 IfM accepts within this time reject else accept By examination ofD we can see that it always halts So LD is decidable By inspection of D LD lt M gt1 Mlt M gt does not accept within 2lltMgtln steps 1 where c is the number of useless states in Next we show that LD is not in EXPTIME Suppose for contradiction that it is Then there is an integer c gt 0 and a TM MD such that LD lt M gt1 MDlt M gt accepts within 2lltMgtla steps1 By adding useless states to MD or removing them we can get another machine M D with c useless states such that LD lt M gt1 MDlt M gt accepts within 2lltMgtl4 steps 2 By 1 lt MD gt6 LD 42gt MDlt MD gt accepts within 2lltMDgtlE steps1 But by 2 lt MD gt6 LD 42gt MDlt MD gt does not accept within 2ltMl3gta steps This gives a contradiction d Turing recognizable but not decidable Answer ATM e not Turing recognizable Answer A TM f undecidable and unary unary means L Q

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.