\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[colorlinks=true]{hyperref}
\usepackage{parskip}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\usepackage{enumerate}

\title{Oblig 3}
\author{IN2080}
\date{\textbf{Deadline:} May 10, 2023}

\setcounter{secnumdepth}{0}

\begin{document}

\maketitle

\section{Hand-in and deadline}
Hand in a single PDF file in \href{https://devilry.ifi.uio.no/}{Devilry}. The deadline is \textbf{May 10, at 23:59}.

We recommend \LaTeX{}, but all major text editors allows exporting to PDF. You can get help with \LaTeX{} at the group sessions. You can also download the \LaTeX{} source (\texttt{.tex}) for this assignment at the assignments page.


\section{Definitions}
A \emph{literal} is a formula on the form $x$ or $\overline{x}$, where $x$ is a variable. A formula $\varphi$ is on \emph{Conjunctive Normal Form} (CNF) if
\[
\varphi = \left(l_1^1 \lor \cdots \lor l_{k_1}^1\right) \land \cdots \land \left(l_1^n \lor \cdots \lor l_{k_n}^n \right),
\]
where $l_i^j$ is the $i$-th literal of the $j$-th clause, and $k_m$ is the number of literals in the $m$-th clause. A formula $\varphi$ is on \emph{Disjunctive Normal Form} (DNF) if
\[
\varphi = \left(l_1^1 \land \cdots \land l_{k_1}^1\right) \lor \cdots \lor \left(l_1^n \land \cdots \land l_{k_n}^n \right).
\]

We define the following languages:
\begin{align*}
\mathsf{CNFSAT} &= \{\varphi \mid \text{$\varphi$ is on CNF, and $\varphi$ is satisfiable}\} \\
\mathsf{DNFSAT} &= \{\varphi \mid \text{$\varphi$ is on DNF, and $\varphi$ is satisfiable}\} \\
\mathsf{CNFUNSAT} &= \{\varphi \mid \text{$\varphi$ is on CNF, and $\varphi$ is unsatisfiable}\} \\
\mathsf{DNFUNSAT} &= \{\varphi \mid \text{$\varphi$ is on DNF, and $\varphi$ is unsatisfiable}\} \\
\mathsf{CNFTAUT} &= \{\varphi \mid \text{$\varphi$ is on CNF, and $\varphi$ is a tautology}\} \\
\mathsf{DNFTAUT} &= \{\varphi \mid \text{$\varphi$ is on DNF, and $\varphi$ is a tautology}\}
\end{align*}

The complexity class $\mathsf{coNP}$ consists of complements of languages in $\mathsf{NP}$. More formally, $\mathsf{coNP} = \{\overline{A} \mid A \in \mathsf{NP}\}$.

A language $A$ is $\mathsf{coNP}$-complete if
\begin{enumerate}[i)]
\item $A \in \mathsf{coNP}$
\item For every language $B \in \mathsf{coNP}$, $B \leq_p A$.
\end{enumerate}

You may use, without proof, that $\mathsf{SAT}$ and $\mathsf{3SAT}$ are $\mathsf{NP}$-complete.

\section{Problem 1}

At least one of the above languages is in $\mathsf{P}$. Identify them, and prove that they are in $\mathsf{P}$.

\section{Problem 2}

At least one of the above languages is $\mathsf{NP}$-complete. Identify them, and prove that they are $\mathsf{NP}$-complete.

\section{Problem 3}

\begin{enumerate}[a)]
\item Show that for all languages $A$ and $B$, $A \leq_p B$ implies $\overline{A} \leq_p \overline{B}$.
\item Show that a language $A$ is $\mathsf{NP}$-complete if and only if $\overline{A}$ is $\mathsf{coNP}$-complete.
\item At least one of the above languages is $\mathsf{coNP}$-complete. Identify them, and, using what you have shown in 3a) and 3b), prove that they are $\mathsf{coNP}$-complete.
\end{enumerate}


\end{document}
