===========================================================================
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.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


1. In classs 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.
 
Let L = { <G> | G is n undirected graph that has no cycles}.
    Is L in P? 

2.  Let H be a language that can be decided by a Turing machine that runs in time 
    n^(Omega(log n)) and that cannot be decided by a faster machine. In other words,
    H cannot be decided by  Turing machine that runs in time n^(o(log n). 
    Is H in P?

3.  A set of vertices in an undeirected graph G is called "independent" if there are no edges between any pair of elements 
    of the set. In other words S subset V(G) is independent if for all i,j in S, ij is not n edge. Let
    I = {<G,t> | G is an undirected graph such that there is an independent set in G of size t}.
    Show that I is in NP.