1. On input <M, w, 1^t>...
   1. for i from 1 to t
   2.    Run M on w for one step.
   3.    If M halts, we halt with the same result.
   4. REJECT if we have not halted yet

Justification: Correctness should follow easily based on what we've seen. Note that in the above, I am assuming input of the correct form.
The outer loop contributes a running time of O(|t|) since t is encoded in unary. Step 2 is polynomial in the size of <M,w> based on the UTM we have seen earlier in the course. Step 3 may be considered to be linear in <M>, but is a simple check of state. Step 4 is constant time. Since polynomials are closed under multiplication and addition, the running time is polynomial, and so by definition the language is in P since it is decided in time polynomial in the size of the input.

2. We will show this both ways: first by giving a poly-time verifier, second by giving a non-deterministic polynomial-time decider.

Verifier:

On input <I,c>... // I is an instance <G,s,t> and c a certificate cover and clique

1. Verify that c encodes two subsets C1,C2 of V(G), with C1 consisting of s distinct nodes and C2 consisting of t distinct nodes. If any conditions fail, REJECT.
2. for each e in E(G), verify that at least one of its end points is in C1. If not, REJECT.
3. for each pair (x,y) of vertices in C2, verify that there exists edge (x,y) in E(G). If not, REJECT
4. ACCEPT

Correctness: Step 1 verifies that we have two subsets of vertices from V(G), one representing what should be s distinct nodes forming a vertex cover and the other representing what should be t distinct nodes forming a clique. Steps 2 and 3 verify the respective properties of these structures. Note that our certificate size will certainly be linear in the size of the instance I.

Runtime: Step 1 is in the worst case quadratic in |I| since we must loop over C1,C2 and V(G), verifying the existence of nodes in V(G) and also counting for the correct numbers of nodes (s and t). Step 2 is again quadratic in |I| since we loop through E(G) and the vertices of C1, whose size is worst-case |I|. Step 3 is justified in a similar manner. Step 4 is constant.

Decider:

On input <G,s,t>... // Having already verified correct input form.
1. Verify s and t are both <= |V(G)|.
2. Non-deterministically choose two subsets C1 and C2 of s and t distinct vertices respectively.
3. If C1 satisfies that for each edge in E(G), at least one endpoint is in C1, then continue. Otherwise REJECT.
4. If C2 satisfies that for each pair of vertices (x,y) in C2, there exists edge (x,y) in E(G), then ACCEPT. Otherwise REJECT.

Correctness: Follows by definitions of vertex cover and clique. If there exists a vertex cover and clique as required, at least one non-deterministic choice will find one. 

Runtime: Step 1 is worst-case quadratic in the size of V(G) (two double-loops searching for vertices). Step 2 is linear in the size of V(G). Step 3 may be upper bounded by |E(G)|*|V(G)| in the obvious way (for each edge, search through the list of vertices of C1). Lastly, Step 4 is worst case |V(G)|^2 * |E(G)| since we choose subsets of C2 and verify edges in E(G), with |V(G)| >= |C2|.