Homework 10: Handed out: 4/26/01; Due: 5/3/01
Section Number Points Comments
36.2 1 4 The definition of graph isomorphism is on p. 88 36.2 2 3 36.2 8 4 36.2 10 3 36.3 2 3 36.3 5 5 36.3 6 4 36.4 4 2 36.4 4 5 For 2 points of extra credit: Why doesn't this say that SAT is in PTIME? Problems 36.1(a),(b),(d) 17 This is one of the supplementary problems on p. 961. Although you don't have to do (c), you should think about it.