=========================================================================== CSC 363H Tutorial Exercises for Week 9 Summer 2006 =========================================================================== - Show that PATH = { : G is a directed graph that has a directed path from s to t } is in NP. - Show that if B is any language such that B =/= {} and B =/= Sigma*, then A <=p B for all languages A in P. - Describe the error in the following fallacious "proof" that P =/= NP: Consider an algorithm for SAT: "On input F, try all possible assignments to the variables. Accept if any satisfy F." This algorithm clearly requires exponential time. Thus, SAT has exponential time complexity. Therefore, SAT is not in P. Because SAT is in NP, it must be true that P is not equal to NP.