%% This LaTeX-file was created by <jl> Mon Apr 20 10:41:00 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 26 4/20/98


\section{Complexity theory!}


\subsection{definitions}

\begin{itemize}
\item CNF: an and of or's. Example: \( (x_{1}\bigvee x_{2}\bigvee x_{3})\wedge (x_{1}\bigvee x_{4})\wedge (x_{3}\bigvee x_{2}) \)
\item clique: a group of fully connected nodes in a graph
\end{itemize}

\section{np completeness}

\begin{itemize}
\item The 'can I satisify this CNF' problem is NP complete.
\item 'Is there a clique of size k' is also NP complete.
\end{itemize}

\section{reduction}

The CNF problem can be transformed into a clique problem by a polynomial transformation.
This means, \( CNFSat\leq ^{p}_{m}Clique \) or 'CNFSat reduces to clique'.

A common goal in complexity theaory is reducing one problem to another in polynomial
time. Basically, by reducing known NP-complete problem X to problem Y by a polynomial
transformation. Then Y is 'at least as hard as X' which mean Y is NP-hard.

The Clique problem can als be reduced to the CNF problem, implying \( Clique\leq _{m}^{p}CNF \). So 

\( Clique\equiv _{m}^{p}CNF \)


\section{definitions}

\begin{itemize}
\item \( A\leq ^{p}_{m}B \) means \( A \) can be solved by calling \( B \) once plus some polynomial work.
\item \( A\leq ^{p}_{m}B \) and \( B\leq ^{p}_{m}C \) then \( A\leq ^{p}_{m}C \)
\item \( A\leq ^{p}_{T}B \) The same as before except \( B \) can be called polynomial times.
\item \( P \) = set of problems solvable in polynomial time
\item \( NP \) = set of problems checkable in polynomial time for 'yes' answers.
\item \( NP-Complete \) = Can't? solve the problem in polynomial time.
\item \( NP-Hard=NP-Complete \) or harder.
\end{itemize}
If a problem is \( NP-Complete \) then every \( NP \) problem can reduce to it. 

The big question in computer science is 'does \( NP=P \)'?

\begin{itemize}
\item \( Co-NP \) = you can check 'No' answers in polynomial time.
\end{itemize}
factoring is in \( Co-NP \) and \( NP \).


\section{reductions}


\subsection{\protect\( 3CNFSat\leftrightarrow CNFSat\protect \)}

\begin{itemize}
\item \( 3CNFSat \) problems have the additional constraint that the CNF is an and of 'ors' of
at most 3 terms.
\end{itemize}
We have \( CNFSat\geq ^{p}_{m}3CNFSat \) automatically. So, let's show \( CNFSat\leq ^{p}_{m}3CNFSat \)

\begin{itemize}
\item general fact: \( (A\bigvee x)\wedge (\overline{x}\bigvee B)\Leftrightarrow (A\bigvee B) \) (resolution rule)
\end{itemize}
Using the resolution rule, \( CNFSat \) can be reduced to \( 3CNFSat \) by repeated application.


\subsubsection{\protect\( 2CNF\protect \)}

2CNF is easy to solve. \( x_{1}\bigvee x_{2} \) means \( \overline{x_{1}}\Rightarrow x_{2} \) so the terms of \( 2CNF \) can be turned into a graph
of implications on which it is easy to solve the \( 2CNF \) problem. In fact, it can
be solved in linear time.


\subsection{independent set \protect\( \leftrightarrow \protect \) clique}

\begin{itemize}
\item independent set = are there k nodes with no edges between any of them on a graph?
\end{itemize}
The reduction is done by solving the complement of the graph.


\subsection{Vertex cover \protect\( \leftrightarrow \protect \) independent set}

\begin{itemize}
\item Are there k nodes which touch every edge?
\end{itemize}
All of the nodes not in the vertex cover are in the independent set.

Vertex Cover \( \equiv _{m}^{p} \) Independent Set


\subsection{CNFSat \protect\( \equiv _{m}^{p}\protect \) 3 colorability}

\begin{itemize}
\item Can this graph be colored with 3 colors s.t. no edge has the same color at each
end?
\end{itemize}

\subsubsection{CNFSat \protect\( \leq ^{p}_{m}\protect \) 3 colorability}

\( (x_{1}\bigvee \overline{x_{2}}\bigvee x_{3}\bigvee \overline{x_{4}}\bigvee x_{5})\wedge ... \)

Draw a graph where every variable is forced to be 'red' or 'green'. Then build
a graph with several constraints.

\end{document}