===========================================================================
CSC 363                     Homework Exercise 6                 Winter 2008
===========================================================================

Due: Apr 4 in tutorial
Worth: 3%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  


1. We have defined coNP complete problems as languages in coNP so that 
every other in coNP polyreduces to them. Show that a language is coNP-complete 
iff it is the complement of an NP-complete problem.

2.   Show that TAUTOLOGY = {phi | phi is satisfied by any truth assignment} 
is coNP complete.

3. In class we saw that CLIQUE is self-reducible. The algorithm we used 
considered vertices one by one, removing redundant ones. Can you show another 
algorithm that removes edges instead? Give a detailed argument to show 
correctness and running time of your algorithm.
 
4. Show that MAX-SAT is self reducible. 
   Recall, in Max-SAT the input is a CNF formula, and the output is
a truth assignment that satisfies as many clauses as possible. Saying that 
MAX-SAT is self reducible is saying that if there is a polytime alg for SAT 
(decision problem) then there is a polytime alg for MAX-SAT.