%% This LaTeX-file was created by <jl> Wed Apr 22 16:09:52 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}


\section{Review}

\begin{itemize}
\item NP = easy to check ``yes''
\item coNP = easy to check ``no''
\item NP-hard = can reduce all of NP to this problem
\item coNP-hard = can reduce all of coNP to this
\item NP-complete = NP and NP-hard
\item CoNP-complete = CoNP and CoNP hard
\end{itemize}

\section{3-colorability \protect\( \equiv _{m}^{p}\protect \) Planar 3-colorability}


\subsection{3-colorability \protect\( \leq _{m}^{p}\protect \) planar 3-colorability}

There is a 13 node graph (``widget'') s.t. the 4 extreme points are constrained
so that each pair of opposite corner points must be the same color. Whenever
there is a crossing of lines in a planar drawing, insert one of these widgets.


\subsection{3-colorability \protect\( \geq ^{p}_{m}\protect \) planar 3-colorability}

obvious.


\section{Some problems}


\subsection{knapsack}

\begin{itemize}
\item S = a set of objects
\item \( w(a) \) = weight of \( a\in S \)
\item \( b(a) \) = benefit of \( a\in S \)
\end{itemize}
The knapsack problem is:


\[
max\sum _{a\in S^{'}}b(a)\]
 subject to:
\[
\sum _{a\in S'}w(z)\leq W\]


Phrased as a decision problem this is 'Is there a set \( S' \) where \( B\geq k \)'?


\subsection{subset sum}

Given a set of integers \( S \) is there a subset of \( S' \) such that \( \sum _{a\in S'}w(a)=B \).


\subsection{Partition}

Given a set of integers \( S \) is there a partition into 2 sets with equal sum?


\subsection{Bin packing}

Can this list be partitioned into k bins such that each bin sums to \( \leq B \).


\section{partition \protect\( \equiv _{m}^{p}\protect \) subset sum}


\subsection{partition \protect\( \leq ^{p}_{m}\protect \) subset sum}

let \( M=\sum _{s\in S}s \). Then let \( B=\frac{M}{2} \)


\subsection{partition \protect\( \geq _{m}^{p}\protect \) subset sum}

Add the numbers 

\begin{itemize}
\item \( N-B \)
\item \( N-(M-B) \)
\end{itemize}
For \( N \) large. Each of these 2 numbers will be in different partitions and one
of these partitions (minus \( N-B \)) is of the right size.


\section{partition \protect\( \leq _{m}^{p}\protect \) bin packing}

Just do 2 bin packing.


\section{Linear programming}

At one time people didn't think that linear programming was polynomial.


\subsection{the problem}

pick \( \{x_{i}\} \) to maximize \( \sum _{i}c_{i}x_{i} \) subject to \( \forall j\sum _{i}a_{ij}x_{j}\leq b_{j} \).


\subsection{integer programming}

Is there a choice of \( \{x_{i}\} \) that satisfies the inequalities with integers?

This problem is np complete


\subsection{subset sum \protect\( \leq _{m}^{p}\protect \) integer programming}

Put in the constraints:

\begin{itemize}
\item \( \sum _{i}a_{i}x_{i}\leq B \)
\item \( -\sum _{i}a_{i}x_{i}\leq -B \)
\end{itemize}
which implies: \( \sum _{i}a_{i}x_{i}=B \).

Also require: \( \forall i\textrm{ }0\leq x_{i}\leq 1 \) to reduce subset sum to integer programming.


\section{Hamiltonian circuit}

Does this graph have a path going through every node exactly once and returning
to the start?


\subsection{vertex cover \protect\( \leq _{m}^{p}\protect \) hamiltonian circuit}

There is a 4 node directed 'widget' with 2 inputs and 2 outputs s.t. a hamiltonian
path can enter through either (or both) input(s) and hit all nodes on a hamiltonian
circuit.

A similar widget exists for the undirected case.

Then, you use these widgets in a way which I can't easily describe. For every
node in the original graph a loop is created.


\section{Travelling salesman problem}

Is there a hamiltonian circuit such that:

Is there a hamiltonian circuit such that total cost \( \leq k \)?


\subsection{hamiltonian circuit \protect\( \leq _{m}^{p}\protect \) TSP}

Put weight one on all of the nodes then ask if there is a TSP with \( k=\#nodes \).


\section{Minimum node deletion bipartite subgraph}

Given a graph G, can I make it bipartite by only deleting k nodes?

Can clique \( \leq _{m}^{p} \) MNDBS?

reduction: Take the original graph, and complement it. Add the number of nodes
again, fully interconnecting a new node to the complemented graph. Is this a
reduction?


\section{New complexity classes}

\begin{itemize}
\item NC = problems that are parallelizable = solvable in polylog time \( =log(n)^{O(1)} \) with a polynomial
\( \# \) of processors.
\end{itemize}
Does P = NC? Probably not. Example: Does program A finish in time n?

The example is in P-complete.

\begin{itemize}
\item BPP = in polytime probably(with high probability) correct. (Bounded error probabilistic
problem)
\item BQP = same as BPP on a quantum computer.
\end{itemize}
\end{document}