1. Indicate whether each of the following is true or false:

1. 2n = O(n)
2. n² = O(n)
3. n² = O(n log² n)
4. n log n = O(n²)
5. 3ⁿ = O(2ⁿ)
6. 2²ⁿ = O(2ⁿ)

3. What is the time complexity of the Turing machine in question 5 on Turing machines?

4. An undirected graph is one in which the edges are undirected. If there is an edge between nodes A and B in an undirected graph, then it is possible to go from A to B, and also from B to A. An undirected graph is connected if every node in the graph can be reached from every other node by travelling along the edges of the graph. Let CONNECTED = {G | G is a connected undirected graph}. The following algorithm can be used to determine whether or not a given undirected graph is connected:

1. Select the first node of G
2. Repeat the following step until no new nodes are marked
    3. For each node in G, mark it if it is attached by an edge to a node that is already marked
4. Scan all the nodes of G to determine whether they are all marked. If they are accept, otherwise reject.

5. Let G be an undirected graph and let SPATH = {(G,a,b,k) | G  contains a simple path of length at most k from a to b}. Show that SPATH Î P.

6. A literal is a Boolean variable or a negated Boolean variable. A clause is a disjunction of several literals (connected with Ús). A Boolean formula is in conjunctive normal form (i.e. it is a cnf-formula), if it is the conjunction of several clauses (connected with Ùs). A formula is a 2cnf-formula if all the clauses have two literals, for example: (x Ú Øy) Ù (yÚØz). Let 2SAT = {f| f is a satisfiable 2cnf-formula}. Show that 2SAT Î P.

7. In the SUBSET-SUM problem, we have a set of numbers {x₁...x_k} and a target number t. We want to determine whether the set contains a subset that adds up to t. Thus SUBSET-SUM = {(S,t) | S = {x₁...x_k} and ${y₁...y_n}Í {x₁...x_k}s.t. åy_i = t}. For example, ({4,11,16,21,27},25) Î SUBSET-SUM because 4+21=25. Show that SUBSET Î NP.

8. Let G be an undirected graph and let UHAMPATH = {G | G contains a Hamiltonian path}. Show that UHAMPATH Î NP-Complete.

9. Let G be an undirected graph and let LPATH = {(G,a,b,k) | G  contains a simple path of length at least k from a to b}. Show that LPATH Î NP-Complete (you can assume from the previous question that UHAMPATH Î NP-Complete).

10. A formula is a 3cnf-formula if all the clauses have three literals, for example: (x Ú Øy Ú z) Ù (ØxÚ yÚØz). Let 3SAT = {f| f is a satisfiable 3cnf-formula}. Show that 3SAT Î NP-complete.