Question 1 Given a solution S, we check that there is a {clique, independent set, clique and independent set} of size {k^2, n, n^2, k} . We check that the clique is {valid by verifying there is no edge between each clique vertex in G, valid by finding a clique in G and checking it against the provided solution, valid by verifying there is an edge between each clique vertex in G, is a valid clique} This takes {O(k 2), O(n), O(k), O(n^2)} We check that the independent set is fa valid independent set, valid by verifying there is an edge between each independent set vertex in G, valid by verifying there is no edge between each independent set vertex in G, valid by finding an independent set in G and checking it against the provided solution} This takes {polynomial time, O(n), O(k), O(n^2), O(k^2)} . We check that {|Clique|,|Independent Set|, |Clique = Independent Set), [V/} = {n^2, k, n, K 2} This takes {O(k 2), polynomial time, O(n), O(n^2), O(k)} . Overall, the runtime is {O(n), polynomial time, O(k), O(k^2), O(n^2)}