ÏPO9\5O¢�|ˆ|[NF}?Ã=£` S\û¸Ŀ`úC Ä�¯£UâQšz-�,PsǶÕ.˜‘ר‚œû7݇ýmͨ›=�oówdnôÍx5£æ“ZßòžÃÄÈÝ–¬N+3æÈ²×Úœ’'º q&|NJ·óÿuJÞI“@ƒ@£Öz¿°NŒéüË�û÷ Ð’A“AìŠlúþ X:Ô…Vöë
  1. Assignment 8.4.4 (only the first part concerning reduction of the languages in TIME(f(n)))
  2. Show that the following problem is in \Sigma_2 P:
    INSTANCE: A set of clauses S and a variable x
    QUESTION: Is there a truth assignment that is minimal for S and satisfies x?
    (A truth assignment T is minimal for a set of clauses S if T satisfies S and there is no other truth assignment T' which is smaller, i.e., for which T'(y) = true implies T(y) = true for all variables y.)
  3. Show that the following problem 'EXACT COVER BY 4-SETS' is NP-complete:
    INSTANCE: Finite set X with |X|=4q, q an integer, and a collection C of 4-element subsets of X
    QUESTION: Is there a subcollection C' of C such that every element of X occurs in exactly one member of C'?
  4. Show that the following problem 'SET SPLITTING' is NP-complete:
    INSTANCE: Collection C of subsets of a finite set S
    QUESTION: Is there a partitioÈJf³[’µ!ÖòJ�ûõ”‰ ýå¸ß:¬‚õŸù§þ¹õ÷¯è)T™d•‹z4¤Ž‡0«³ªˆ­êñåTï ’YT/N“wlqêRÉŠ?åx¬b¯›ÆÀ§2½ûN:e*SèÕ1`GY­ :”jö·å–:Aý.Ã2'ìtéçxƒæùZÞ/²6'oÌPfEs’:kÒ¸á³NVY”V¶ñ�÷ µ6ÕͲ�úÞé½£Èï?øã–¤NnÛ&jrÕ¹®% Í•V5\±29m�r‚lÕ]_Î €âiZã‡"ïËÉ(x¿ù3ÞÅÎP¥¹îË?QÆæÑ ‹,3 CBð °ÊÓð"³0�ü"÷ÑמØ'oÒNóC†L(=Fqž]¨`{Üz4žŒ±énjúß¹u¢#ëdœmn�ŽÍ0ó̦ƒàŸ%en"Ïs[a:úKžCù] K®’‰«Œ.ÞŸÜ’Žç|Z.}6蜷-È3Úo�4 Y¯ÝMìùÀ•‰Î.—dnÆšV¿^¶½2r§_ìÈú“