2. An input string of length 2k is processed in three phases. First, the middle is found changing all the symbols to upper case. Second, the first half of the input string is converted back to lower case, while moving the tape head back to the beginning. Third, the two halves are compared. In the first phase, 2k+1 moves are required to change the first symbol and find the rightmost symbol, and 2k more moves are required to change the symbol and return the tape head to the leftmost lower case symbol. Each subsequent pass deals with two fewer lower case symbols and therefore requires four fewer moves. The total number of moves in the first phase is 4k+1 + 4(k-1)+1 + ... + 4(0)+1 = 4S^k_i=1 i + (k+1) = 2k²+3k+1. The second phase requires k+1 moves. The time for the first two phases depends only on the input length, as long as the length is even. In the third phase, the maximum number of moves is obtained for inputs belonging to the language. This phase consists of k passes, one for each symbol in the first half. In each pass, there are k moves to the right, k to the left, and one more to the right, for a total of 2k+1 moves. Therefore, the third phase requires at most 2k²+k moves. Adding these three phases together, we obtain 4k²+5k+2 = n²+5n/2+2 moves. This formula does not apply when k=0. However, because the number of moves for odd length input is smaller, this algorithm is O(n²).

3. Suppose that the input is aⁿ = a^2k. 4k+1 moves are needed to go from xx^2k-1 to #xx^2k-3; 4(k-1)+1 to go to ##xx^2k-5; ...; and 4(1)+1 to go to #^k+1#. Add one move at the beginning and at the end and the result is S^k_i=1 (4i+1) = 2 + 4k(k+1)/2+k = 2k²+3k+2 = (n²+3n+4)/2. It can also be easily checked the same formula holds when n is odd.

4. Step 1 takes O(1) time. To analyse step 2, note that for a given node, checking all nodes can take at most O(n²) time (as at most, there are O(n²) edges). Since there are n nodes, marking once through for each node takes O(n³) time. Further, in the worst case, since only one new node is marked on each pass, we may have to repeat passing through all of the nodes n times. In total, step 2 has a running time of O(n⁴). Step 3 takes O(1) time. Hence, the algorithm has a running time of O(n⁴), and therefore CONNECTED Î P.

5. The following is a polynomial time algorithm to decide SPATH:

        1. Run a breadth first search on G starting from a.
        2. If the distance from a to b is less than or equal to k, then accept, otherwise reject.
 
This works because a breadth first search will find the shortest path from a to b in polynomial time. If the shortest path has a length less than or equal to k, then the instance (G,k) is in SPATH. If G contains a simple path of length at most k from a to b, then the shortest path from a to b will also be less than or equal to k.

6. Note that a clause of the form (x Ú y) is logically equivalent to the statement Øx Þ y (and also Øy Þ x). Further, note that a 2SAT formula is satisfiable except when a set of clauses leads to a contradiction. For example, (x Ú y) Ù (x Ú Øy) Ù (Øx Ú y) Ù (Øx Ú Øy) is unsatisfiable because for every possible assignment of truth values to x and y, there is some clause present which contradicts another clause. In terms of implications, this means that Øx Þ y Þ x and x Þ y Þ Øx. Hence there is a contradiction.

We use this set of implications based on clauses to create a graph as follows: for each variable in f, make two nodes in G, one for each literal. For every clause (x Ú y), add a directed edge from Øx to y and an edge from Øy to x. Once the graph is built, a satisfying assignment for f corresponds to a graph which contains no cycles containing both positive and negative literals, other than the trivial ones (from x to Øx). Searching the graph for cycles can be done in polynomial time. In other words, you are searching for a path from some literal x to Øx and from Øx to x. If both chains exist, then there is a contradiction, and then there is no satisfying assignment. Otherwise, there is a satisfying assignment. Paths can be searched for in polynomial time. Thus 2SAT Î P.

7. There are two ways in which we can prove this. Firstly, we can show that there is a polynomial time verifier in which the subset is the certificate. The following is a verifier for SUBSET-SUM with input ((S,t),c):

        1. Test whether c is a set of numbers that sum to t
        2. Test whether S contains all the numbers in c
        3. If both pass accept, otherwise reject

An alternative proof is to give a non-deterministic Turing machine for SUBSET-SUM as follows:

        1. Non-deterministically select a subset c of the numbers in S
        2. Test whether c is a set of numbers that sum to t
        3. If the test passes accept, otherwise reject
 
Thus SUBSET Î NP.

8. We give a polynomial time reduction from HAMPATH. The reduction takes a directed graph G with nodes s and t, and constructs an undirected graph G' with nodes s' and t'. Graph G has a Hamiltonian path from s to t if and only if G' has a Hamiltonian path from s' to t'. We describe G' as follows. Each node u of G, except for s and t, is replaced by a triple of nodes uⁱⁿ, u^mid and u^out in G'. Nodes s and t in G are replaced by nodes s^out and tⁱⁿ in G'. Edges of two types appear in G'. First, edges connect u^mid with uⁱⁿ and u^out. Second, an edge connects u^out with vⁱⁿ if an edge goes from u to v in G. That completes the construction of G'.

We can demonstrate that this construction works by showing that G has a Hamiltonian path from s to t if and only if G' has a Hamiltonian path from s^out to tⁱⁿ. To show one direction, we observe that a Hamiltonian path P in G, s,u₁,u₂,...,u_k,t has a corresponding Hamiltonian path P' in G', s^out,u₁ⁱⁿ,u₁^mid,u₁^out,u₂ⁱⁿ,u₂^mid,u₂^out,...,tⁱⁿ. To show the other direction, we claim that any Hamiltonian path in G' from s^out to tⁱⁿ in G' must go from a triple of nodes to a triple of nodes, except for the start and finish, as does the path P' we just described. That would complete the proof because any such path has a corresponding Hamiltonian path in G. We prove the claim by following the path starting at node s^out. Observe that the next node in the path must be in u_iⁱⁿ for some i because only those nodes are connected to s^out. The next node must be u_i^mid, because no other way is available to include u_i^mid in the Hamiltonian path. After u_i^mid comes u_i^out because that is the only other one to which u_i^mid is connected. The next node must be u_jⁱⁿ for some j because no other available node is connected to u_i^out. The argument repeats until tⁱⁿ is reached. Thus UHAMPATH ÎNP-Complete.

9. First, note that LPATH is in NP. The certificate is simply the path of length at least k from a to b. To show LPATH is NP-Complete, we reduce from UHAMPATH to LPATH: on input (G=(V,E),a,b) return (G,a,b,|V|-1). This reduction clearly runs in polynomial time. If G has a Hamiltonian path from a to b, then that path is a simple path from a to b of length |V|-1 and is therefore in LPATH. Conversely, if there is a simple path of length at least |V|-1 from a to b, then it must pass through every other node in the graph, and is a Hamiltonian path. Thus LPATH Î NP-Complete.

10. Obviously 3SAT is in NP, so we only need to prove that all languages in NP reduce to 3SAT in polynomial time. One way to do so is by showing that SAT reduces to 3SAT in polynomial time. We do this by showing how to convert a formula in cnf into 3cnf. In each clause which currently has one or two literals, we replicate one of the literals until the total number is three. In each clause that has more than three literals we split it into several clauses and add several variables to preserve the satisfiability or nonsatisfiability of the original. For example, we replace clause (a₁ Ú a₂ Ú a₃ Ú a₄) with (a₁ Ú a₂ Ú z) Ù (Øz Ú a₃ Ú a₄) where z is a new variable. If some assignment of the a's satisfies the original clause, we can find some assignment of z so that the two new clauses are satisfied. In general, if the clause contains k literals, (a₁ Ú a₂ Ú ... Ú a_k), we can replace it with the k-2 clauses, (a₁ Ú a₂ Ú z₁) Ù (Øz₁ Ú a₃ Ú z₂) Ù (Øz₂ Ú a₄ Ú z₃) Ù ... Ù (Øz_k-3 Ú a_k-1 Ú a_k). We may easily verify that the new formula is satisifable if and only if the original formula was. To complete the proof it is sufficient to show that this conversion is computable in polynomial time. This follows immediately from the fact that the length of the new formula is bounded by a polynomial function of the length of the original. Thus 3SAT Î NP-complete.