Q1. We need to show that for any L in NP, L<=A_TM i.e. there exists a 
poly-time computible function f_L such that w is in L iff f_L(w) is in A_TM. 
Fix L to be any particular language in NP. By definition, there exists a 
non-deterministic polynomial-time decider M_L for L. Let f(w)=<M_L,w>.

It is clear that w is in L iff w is accepted by M_L iff A_TM accepts <M_L,w> 
(all of this follows by definition).

Further, since M_L is well-defined for any particular L, we claim that writing
 <M_L,w> to the time takes time linear in |<w>|, plus some constant time to 
write the constant-size encoding <M_L> to the tape. Note that this is 
something to realize: for any L, we have the machine M_L that decides it 
and the time it takes to write <M_L> to tape is independent of the size 
of the input <w> in which we are interested.

Q2. First we show AIS is in NP. To do so, we use a verifier:

On input <I,c>.... // Assume I=<G,k> is a proper encoding of an instance 
of AIS.
1) Verify that c encodes a set of k distinct vertices of the graph G.
2) Verify that there exists at most one edge among the vertices of c.
3) If either condition above fails, REJECT. Otherwise, ACCEPT.

The first step verifies that we a certificate encoding k distinct vertices, 
and the second step verifies that the set of vertices is independent except 
for the allowing the possibility of on edge among them. 

The running time of the first step is worst-case quadratic in the size of the 
input <I>: for each vertex in c, verify its existence in G; next we count the 
total number of unique vertices in c to verify its size is indeed equal to k. 
The second step takes worst-case quadratic time in <I> again, since <c> has 
size bounded by <I> and we perform a linear-time lookup in <I> for edges 
between the vertices of c.

Now for hardness, we reduce to INDEPENDENT SET. We will give a polynomial-time
 computible function f such that given <G,k> as input to INDEPENDENT SET, we 
output <G',k'> s.t. <G,k> is in INDEPENDENT SET iff G' has an 
almost-independent set of size k.

On input <G,k>...
1) Output <G',k+2>, where V(G')=V(G) U {x,y} and E(G')=E(G) U {x,y}. 

To clarify, we are adding exactly two new vertices to G and joining then by 
an edge.

Now, suppose G has an independent set S of size k. Then by construction, S 
is almost an independent set of size k in G'. Since the vertices x,y are not 
in G, the set S'=S U {x,y} is an almost-independent set of size k+2 since S 
and {x,y} are disjoint sets, S contains no edges among its vertices, and 
(x,y) is an edge in E(G').

Now suppose G' has an almost-independent set S'. We observe two scenarios.

First,  suppose S' a true independent set. Then S' contains at most one of x 
or y, not both, for otherwise it would not be independent by the existence of 
edge (x,y) in E(G'). Therefore, the set obtained by removing any instances of 
x,y from S' is an independent set of size at least k+1. Hence G would also 
contain an independent set of size k+1 since V(G') is identical to V(G) if we 
exclude x and y, and clearly the existence of an independent set of size k+1 
implies the existence of an independent set of size k by simply excluding any 
vertex.

Now suppose S' does contain an edge. If the edge is between x and y -- that 
is, {x,y} is a subset of S' -- then removal of x and y from S' yields an 
independent set of size k which is contained in both V(G) and V(G'). 
Otherwise, suppose the edge exists between two vertices u,v distinct from 
x and y. If neither of x or y are in S', then removal of u,v from S' yields 
a true independent set of size k that exists in both V(G) and V(G'). If 
either of x or y exists in S' (note that it cannot be the case that both 
x,y exist in S' or else this implies a second edge within the induced 
subgraph G[S']), then without loss of generality assume it is x that exists 
in S'. Then removal of u and x yields a set S of vertices that exists in both 
V(G) and V(G') and is a true independent set.

Hence G has an independent set of size k iff G' has an almost-independent set 
of size k+2.

Q3a)

Assume A is coNP-complete. Then A is in coNP by definition and hence it is the
 complement of a language B in NP. By definition, A^c=B and hence A^c is in NP.
 Further, every language L in coNP reduces to A since A is coNP-hard (since it
 is coNP-complete). Then let L be any language in NP. Then L^c is in coNP, 
hence L^c mapping reduces to A by hardness. From what we've seen in class, 
this implies that (L^c)^c mapping reduces to A^c, i.e. L mapping reduces to 
A^c. Thus every language L in NP mapping reduces to A^c, telling us that A^c 
is NP-hard. Since A^c is in NP and NP-hard, it is NP-complete.

The other direction follows by symmetry: If A^c is in NP then A=(A^c)^c is in 
coNP. Further, let B be any language in coNP. Then B^c is in NP by definition, and 
B^c mapping reduces to A^c since A^c is NP-hard. By properties in class, 
this implies B=(B^c)^c mapping reduces to A=(A^c)^c. Hence all coNP languages 
reduces to A, A is in coNP, and hence A is coNP-complete.

Q3b) 
Suppose P=NP. Then every language L in NP has a deterministic poly-time 
decider. Take any language A in coNP. Then A=L^c for some L in NP, and so L 
has a deterministic poly-time decider M. By reversing the accept/reject states
 of M, we obtain a deterministic polytime decider for L^c and hence for A. 
Therefore every language in coNP has a polytime decider, showing coNP is a 
subset of P. 

Now take any language L in P having decider M. Reverse the states of M to 
obtain M'. Note that L(M')=L^c is in NP since it has a non-deterministic 
polynomial-time decider M' (that simply chooses deterministic paths instead 
of using non-determinism). Then by definition the complement (L(M'))^c=L is 
in coNP, and so P is a subset of coNP.

Since coNP and P are subsets of each other, P=coNP under the given assumption.

Q3c) Let L be both NP-complete and coNP-complete. Since L is in NP, it has a 
non-deterministic polynomial-time decider M. Then given any language B in 
coNP, we build a non-deterministic polynomial time decider for B:

On input w...
1) Compute f(w), where f is the one-to-many reduction of B to L.
2) Run M on f(w) and do the same.

We verify: w is in B iff f(w) is in L iff M accepts f(w). So correctness follows. Now, 
the mapping reduction is polynomial and M is non-deterministic polynomial-time so the above 
decider is non-deterministic polynomial, hence every language B that is in coNP is also in NP.

Now given any language A in NP, obtain its complement B which is in coNP. From above, B is 
also in NP. Now observe that B^c=(A^c)^c=A and since B is in NP, B^c=A is in coNP by definition.

Hence coNP is a subset of NP and vice versa, so coNP=NP under the given assumption.

Q3d) 

To show FE is in coNP, consider its complement:

FE^c={<F1,F2>| there exists at least one truth assignment that gives F1 and F2 different values}

We show this is in NP by a verifier:

On input <I,c>... // Assuming I=<F1,F2> is proper encoding
1) Verify that <c> encodes an assignment of truth values to variables in F1,F2.
2) Resolve F1 and F2 under c, ACCEPT iff their OR is false.

Step 1 is clearly worst-case quadratic in |<I>|, step 2 is polynomial using a 
SAT solver (same as the one used to show SAT is in NP).

Then by definition, FE^c^c=FE is in coNP.

Now, for completeness we need to show every language in coNP reduces to FE. 
Let L be any language in coNP, and w any input to L. We use a mapping 
reduction.

On input w...
1) Compute f(w), the mapping used from L^c to SAT.
2) Output <f(w), x^NOT(x)>.

Correctness: w is in L iff w is not in L^c. Now by definition of the mapping 
f,  w is in L^c iff f(w) is SAT. Equivalently, w is NOT in L^c iff f(w) is 
NOT in SAT. Interpreting what this means, we see that f(w) is NOT in SAT iff 
there is no satisfying assignment to f(w). Since the boolean formula 
(x ^ NOT(x)) is never satisfiable, f(w) is never satisfiable iff all of its 
truth assignments evaluate it to be FALSE.

Runtime: By definition of f, f is polynomial in |w|. Outputting <f(w)> and 
the constant-size boolean formula x^NOT(x) is polynomial.


Q4. Suppose we have a deterministic polytime decider D for PARTITION. We use 
the following algorithm.
Idea: We will take single elements of S one at a time, combine them into a 
larger "super-element" (their sum), and ask D if we can still partition S as 
required. If the answer is YES and we've combined, say, elements x and y into 
z=x+y, then we know a partition exists with elements x,y in the same partition.
 

The pseudocode follows below:

1. A = <empty set>
2. for each element e in S
3.   Add e to A
4.   Let z = the sum of elements in A
5.   Ask D if there exists a PARTITION in (S / A) U {z}
6.   If not, remove e from A
7. Return A

Correctness: We can argue that every element e is in a partition of S, and our
 algorithm maintains that the elements of A belong in the same partition. 
Inductively, each step of the algorithm builds A in such a way that all 
elements inside can be represented by a single element equal to their sum, 
and the set (S/A)U{z} can still be partitioned. Clearly, this requires {z} to 
be in one of two partitions, and hence all elements of A can all together be 
placed in that same partition as a solution for the original problem.

Runtime: Keep in mind that we should think of this w.r.t implementation on a 
TM. 

Step 1: Constant time (Store on a separate tape 2)
Step 2: Multiplies by a linear factor.
Step 3: Linear to add the element to tape 2.
Step 4: Polynomial to add O(|I|) elements together
Step 5: Polynomial since D runs in polytime, possibly with some time to set up
 the input tape for D (likely linear to copy appropriate elements of S to an 
input tape, together with z)
Step 6: Linear to remove the element.
Step 7: Constant time