===========================================================================
CSC 363H                  Tutorial Exercises Week 9                  Spring 2007
===========================================================================


 -  Exercise 7.11: show that graph isomorphism (formalized as ISO) is in NP.


 -  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.


 -  Show that if B is any language such that B =/= {} and B =/= Sigma*,
   then A <=p B for all languages A in P.


 -  Show that for any language L in NP, L <=m A_TM.


 *  Consider the following problem: given a set of numbers S,
   partition S into two sets T_1 and T_2 such that
   the sum of the elements in T_1 equals the sum of the elements in T_2.

 -  Formalize this as a language membership problem by defining the language PARTITION.

 -  Show that PARTITION <=p SUBSETSUM

 -  Show that SUBSETSUM <=p PARTITION

   Recall: SUBSETSUM = { <S,t> : S has a subset summing to t }