CSE 431: HW #6

Out: Tuesday, 13-Feb

Due: Tuesday, 20-Feb before class

Assignment

1. coNP

   For a language \(L \subseteq \Sigma^*\), we define \(\textrm{co-}L\) as the "semantic complement" of \(L\). This is slightly different from the set-theoretic complement \(\Sigma^* \setminus L\). As an example, \(\mathsf{HAMPATH} = \{ \langle G \rangle : G \textrm{ has a Hamiltonian path}\}\). The set theoretic complement of \(\mathsf{HAMPATH}\) contains all the strings \(\langle G\rangle\) such that \(G\) does not have a Hamiltonian path, but it also contains the strings that don't encode any graph at all.

   On the other hand, \[ \textrm{co-}\mathsf{HAMPATH} = \left\{ \langle G \rangle : G \textrm{ does not have a Hamiltonian path} \right\}. \] Now we can define the complexity class \(\mathsf{coNP} = \{ \textrm{co-}L : L \in \mathsf{NP} \}\). For instance, \(\textrm{co-}\mathsf{HAMPATH} \in \mathsf{coNP}\).

   Say that a language \(L\) is \(\mathsf{coNP}\)-complete if \(L \in \mathsf{coNP}\) and for every language \(L' \in \mathsf{coNP}\), it holds that \(L' \leq_P L\).

   1. Prove that \(\textrm{co-}\mathsf{3SAT}\) is \(\mathsf{coNP}\)-complete.

   2. Prove that if \(\mathsf{NP} \neq \mathsf{coNP}\), then \(\mathsf{P} \neq \mathsf{NP}\),

   3. Give a characterization of \(\mathsf{coNP}\) in terms of polynomially-verifiable certificates.

   4. Most people expect that \(\mathsf{NP} \neq \mathsf{coNP}\). Explain why the question \(\mathsf{NP} =^{?} \mathsf{coNP}\) is non-relativizing.

2. NL

   Recall the language \(\mathsf{BIPARTITE} = \left\{ \langle G \rangle : G \textrm{ is a bipartite graph} \right\}\). Show that \(\mathsf{BIPARTITE} \in \mathsf{NL}\), where \(\mathsf{NL}\) is the class of languages that can be decided in logarithmic space on a non-deterministic TM.

Extra credit

1. A an undirected graph \(G\) is a forest if the connected components of \(G\) are trees. Define the language \(\mathsf{FOREST} = \left\{ \langle G \rangle : G \textrm{ is a forest} \right\}\). Prove that \(\mathsf{FOREST} \in \mathsf{L}\), where \(\mathsf{L}\) is the class of languages that can be decided in logarithmic space.