===========================================================================
CSC 363H                        Exercise 6                        Fall 2007
===========================================================================

A.  For each language below, state whether or not it belongs to P and
    whether or not it belongs to NP.  Justify each answer, by giving a
    detailed description of an appropriate decider/verifier or by giving a
    short explanation of why you think there is none -- no proof required.

    Reminders:
    An undirected "weighted graph" G -- with vertex set V and edge set E --
    associates a "weight" w(e) (a real number) with each edge e in E.
    A "spanning tree" of an undirected graph G = (V,E) is any subset of
    edges T subset E that is connected (it is possible to get from any one
    vertex u in V to any other vertex v in V using only edges of T) and
    acyclic (it is not possible to start at some vertex u in V, travel
    along edges of T, and return to u, except by reusing edges) -- it is
    possible to show that any spanning tree contains exactly n-1 edges,
    where n = |V| is the number of vertices.
    The "degree" of a vertex v in a graph G is simply the number of edges
    that include v.

    (a) L_1 = { <G,W> : G is an undirected weighted graph that contains
                        a spanning tree with total weight <= W }

    (b) L_2 = { <G,W,K> : G is an undirected weighted graph that contains
                          a spanning tree with total weight <= W and in
                          which no vertex has degree larger than K }
        (the degree is measured with respect to the spanning tree only, not
        with respect to the entire graph)

B.  Show that NP is closed under concatenation, i.e., for all languages
    A, B in NP, A.B in NP, where A.B = { z : z = xy for x in A, y in B }.

C.  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 is the case that P is not equal to NP.