Notes:

Problem : We can define co-NP-complete just like NP-complete: a problem $X$ is co-NP-complete if a) $X \in co-NP$, and b) for all $Y \in co-NP$, $Y \le_P X$. Show that if there is a co-NP-complete problem $X$ such that $X \in P$ then $P = NP$.

Problem : HAMILTONIAN-PATH (HP: the problem of, given an undirected graph $G$, determining whether $G$ has a Hamiltonian path) is NP-complete. But perhaps the problem becomes easier if we relax the requirements somewhat. Consider BURRIAN-PATH, which is the problem of, given an undirected, connected graph $G$, determining if $G$ has a simple path that visits at least $\Bigl\lfloor \frac{n}{2} \Bigr\rfloor$ vertices. Prove that this modified problem is not in fact any easier in some sense: BURRIAN-PATH is NP-complete. Give the same level of detail as in the $HC \le_P HP$ video when showing that things that need to be polynomial-time and polynomial-size are polynomial-time and polynomial-size.

Problem : FIND-HAMILTONIAN-CYCLE (FHC) is the search problem corresponding to the decision problem Hamiltonian Cycle (HC) – FHC is the problem of, given an undirected graph $G$, returning a Hamiltonian cycle in $G$, or nil if no such cycle exists. Prove that FHC and HC are in some sense equivalently difficult: there is a polynomial time algorithm for FHC if and only if there is a polynomial time algorithm for HC. Prove this by showing a) that $HC \le_P FHC$; b) $FHC \le_P HC$ by writing a polynomial-time algorithm for $FHC$ that uses a solution to $HC$ as a subroutine (counting a use of that subroutine as 1 step); and c) that your algorithm for (b) is correct by writing the invariant for it (you needn't prove that your invariant is correct, but it should be complete – sufficient to finish a proof if it had been required).

(There are several ways to do this, but generally the more concise algorithms will have trickier invariants. Grading will be adjusted to emphasize the harder part, whether that is the algorithm or the invariant.)