\documentclass[11pt,letter]{article}
\pagestyle{plain}
\usepackage{latexsym}
\usepackage{epsfig}
%\textwidth15cm
%\newtheorem{lemma}{Lemma}
\newtheorem{statement}{Proposition}
\newtheorem{exercise}{Exercise}
%\newtheorem{theorem}{Theorem}
%\newtheorem{prop}{Proposal}
%\newtheorem{property}{Property}
%\newtheorem{corollary}{Corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% comments and stuff / temporary %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\lastcorrections}%
{{\vskip  0.2in
\begin{sloppypar}
    \baselineskip -0.2in
    \tiny\bf\noindent Last Corrections:\\   %%%%% keep this info
                                            %%%%% current

Tue Apr  5 15:24:15 PDT 2016
\end{sloppypar}
}}

\newcommand{\margincomment}[1]%
    {{%
      \marginpar{{\tiny\begin{minipage}{0.5in}
                       \begin{flushleft}
                          {#1}
                       \end{flushleft}
                       \end{minipage}
                }}
    }}

%\renewcommand{\cite}[1]{{[{\sf #1}]}}  % temporary, to avoid latex complaints
%\renewcommand{\ref}[1]{{[{\sf #1}]}}  % temporary, to avoid latex complaints

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% useful editing macros %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\etal}{{\em et al.~\/}}
\newcommand{\tH}{{\rm th}}
\newcommand{\etc}{{\em etc.\/}}
\newcommand{\ie}{{\em i.e.\/}}
\newcommand{\eg} {{\em e.g.\/}}
\newcommand{\larry}{$\calL^3$}
\newcommand{\mch}{\mbox{${\cal MC}h$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% lengths and sizes %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\setlength{\evensidemargin}{0.1in}
%\setlength{\oddsidemargin}{0.1in}
%\setlength{\textwidth}{6.7in}
%\setlength{\topmargin}{0.2in}
%\setlength{\textheight}{8.7in}
%\setlength{\headheight}{0in}
%%\setlength{\headsep}{0in}
%\setlength{\topsep}{0in}
%\setlength{\itemsep}{0in}

%\parskip=.080in
%\setlength{\evensidemargin}{0.0in}
%\setlength{\oddsidemargin}{0.0in}
%\setlength{\textwidth}{6.5in}
%\setlength{\topmargin}{0.0in}
%\setlength{\textheight}{8.8in}
%%\setlength{\headheight}{0in}
%\setlength{\headsep}{0in}
%\setlength{\topsep}{0in}
%\setlength{\itemsep}{0in}
\addtolength{\textheight}{1.0in}
\addtolength{\topmargin}{-0.6in}
\addtolength{\textwidth}{1.0in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\evensidemargin}{-0.5in}
%\addtolength{\textheight}{0.6in}
%\addtolength{\topmargin}{-0.4in}
%\addtolength{\textheight}{0.0in}
%\addtolength{\topmargin}{-0.6in}
%\addtolength{\textwidth}{1.0in}
%\addtolength{\oddsidemargin}{-0.5in}
%\addtolength{\evensidemargin}{-0.5in}
%\renewcommand{\baselinestretch}{1.16}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% all sorts of letters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bfx}{{\bf x}}

\newcommand{\bara}{{\bar a}}
\newcommand{\barm}{{\bar m}}
\newcommand{\barA}{{\bar A}}

\newcommand{\barx}{{\bar x}}
\newcommand{\bary}{{\bar y}}
\newcommand{\barz}{{\bar z}}
\newcommand{\barr}{{\bar r}}

\newcommand{\calA}{{\cal A}}
\newcommand{\calB}{{\cal B}}
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calE}{{\cal E}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calG}{{\cal G}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calI}{{\cal I}}
\newcommand{\calJ}{{\cal J}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calL}{{\cal L}}
\newcommand{\calM}{{\cal M}}
\newcommand{\calN}{{\cal N}}
\newcommand{\calO}{{\cal O}}
\newcommand{\calP}{{\cal P}}
\newcommand{\calQ}{{\cal Q}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calT}{{\cal T}}
\newcommand{\calU}{{\cal U}}
\newcommand{\calV}{{\cal V}}
\newcommand{\calW}{{\cal W}}
\newcommand{\calX}{{\cal X}}
\newcommand{\calY}{{\cal Y}}
\newcommand{\calZ}{{\cal Z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% maly %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\maly}[1]{{\scriptscriptstyle#1}}
\newcommand{\malyz}{{\maly{0}}}
\newcommand{\malyk}{{\maly{k}}}
\newcommand{\malyone}{{\maly{1}}}
\newcommand{\malytwo}{{\maly{2}}}
\newcommand{\malythree}{{\maly{3}}}
\newcommand{\malyhalf}{{\mbox{$\maly{\frac{1}{2}}$}}}
\newcommand{\malylambdahalves}{{\mbox{$\maly{\frac{\lambda}{2}}$}}}
\newcommand{\malyA}{{\scriptscriptstyle A}}
\newcommand{\malyB}{{\scriptscriptstyle B}}
\newcommand{\malyC}{{\scriptscriptstyle C}}
\newcommand{\malyD}{{\scriptscriptstyle D}}
\newcommand{\malyE}{{\scriptscriptstyle E}}
\newcommand{\malyF}{{\scriptscriptstyle F}}
\newcommand{\malyG}{{\scriptscriptstyle G}}
\newcommand{\malyH}{{\scriptscriptstyle H}}
\newcommand{\malyI}{{\scriptscriptstyle I}}
\newcommand{\malyJ}{{\scriptscriptstyle J}}
\newcommand{\malyK}{{\scriptscriptstyle K}}
\newcommand{\malyL}{{\scriptscriptstyle L}}
\newcommand{\malyM}{{\scriptscriptstyle M}}
\newcommand{\malyN}{{\scriptscriptstyle N}}
\newcommand{\malyO}{{\scriptscriptstyle O}}
\newcommand{\malyP}{{\scriptscriptstyle P}}
\newcommand{\malyQ}{{\scriptscriptstyle Q}}
\newcommand{\malyR}{{\scriptscriptstyle R}}
\newcommand{\malyS}{{\scriptscriptstyle S}}
\newcommand{\malyT}{{\scriptscriptstyle T}}
\newcommand{\malyU}{{\scriptscriptstyle U}}
\newcommand{\malyV}{{\scriptscriptstyle V}}
\newcommand{\malyW}{{\scriptscriptstyle W}}
\newcommand{\malyX}{{\scriptscriptstyle X}}
\newcommand{\malyY}{{\scriptscriptstyle Y}}
\newcommand{\malyZ}{{\scriptscriptstyle Z}}
\newcommand{\smallworkfs}{{\scriptstyle\workfs{}}}
\newcommand{\smalld}{{b}}
\newcommand{\smallrm}{{\rm\small}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% delimiters %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\parend}[1]{{\left( #1  \right) }}
\newcommand{\spparend}[1]{{\left(\, #1  \,\right) }}
\newcommand{\angled}[1]{{\left\langle #1  \right\rangle }}
\newcommand{\brackd}[1]{{\left[ #1  \right] }}
\newcommand{\spbrackd}[1]{{\left[\, #1  \,\right] }}
\newcommand{\braced}[1]{{\left\{ #1  \right\} }}
\newcommand{\leftbraced}[1]{{\left\{ #1  \right. }}
\newcommand{\floor}[1]{{\left\lfloor #1\right\rfloor}}
\newcommand{\ceiling}[1]{{\left\lceil #1\right\rceil}}
\newcommand{\barred}[1]{{\left| #1\right|}}
\newcommand{\doublebarred}[1]{{\left|\left|#1\right|\right|}}
\newcommand{\spaced}[1]{{\ #1\ }}
\newcommand{\suchthat}{{\spaced{:}}}
\newcommand{\spacedbar}{{\spaced{|}}}
\newcommand{\spacedromn}[1]{\spaced{\roman{#1}}}



\newcommand{\bracedtwo}[2]{\braced{\begin{array}{c}
                                        #1 \\ #2
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedtwo}[2]{\left\{\begin{array}{l}
                                        #1 \\ #2
                                    \end{array}\right.
                           }
\newcommand{\bracedthree}[3]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedthree}[3]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3
                                    \end{array}\right.
                           }
\newcommand{\bracedfour}[4]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3 \\ #4
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedfour}[4]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3 \\ #4
                                    \end{array}\right.
                           }
%%%%%%%%%%%%%%% DO NOT ALLOW ANY LINE TO GO BEYOND THIS LINE %%%%%%%%%%%%%%%%%%
\newcommand{\bracedfive}[5]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3 \\ #4 \\ #5
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedfive}[5]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3 \\ #4 \\ #5
                                    \end{array}\right.
                           }

\newcommand{\mycase}[1]{\smallskip\noindent \mbox{Case #1:}}

\newcommand{\ignore}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% environments %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newtheorem{observation}{Observation}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{conjecture}{Conjecture}
\newenvironment{proof}{{\it Proof:\/}}{$\Box$\vskip 0.1in}
\newenvironment{example}{\medskip\noindent{\it Example:\/}}{$\Box$\vskip 0.1in}
\newenvironment{problem}{\medskip\noindent{\it Problem:\/}}{$\Box$\vskip 0.1in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% some general mathematical symbols %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\half}{{\mbox{$\frac{1}{2}$}}}
\newcommand{\onehalf}{{\half}}
\newcommand{\threehalves}{{\mbox{$\frac{3}{2}$}}}
\newcommand{\onethird}{{\mbox{$\frac{1}{3}$}}}
\newcommand{\twothirds}{{\mbox{$\frac{2}{3}$}}}
\newcommand{\fourthirds}{{\mbox{$\frac{4}{3}$}}}
\newcommand{\fivethirds}{{\mbox{$\frac{5}{3}$}}}
\newcommand{\seventhirds}{{\mbox{$\frac{7}{3}$}}}
\newcommand{\onefourth}{{\mbox{$\frac{1}{4}$}}}
\newcommand{\fivefourths}{{\mbox{$\frac{5}{4}$}}}
\newcommand{\onesixth}{{\mbox{$\frac{1}{6}$}}}
\newcommand{\fivesixths}{{\mbox{$\frac{5}{6}$}}}
\newcommand{\sevensixths}{{\mbox{$\frac{7}{6}$}}}
\newcommand{\onetwelfth}{{\mbox{$\frac{1}{12}$}}}

\newcommand{\Comp}{{\parend{1+e^{-\malyhalf}}}}

\newcommand{\update}{{\wedge}}
\newcommand{\opt}{{\mbox{\it opt}}}
\newcommand{\cost}{{\mbox{\it cost}}}
\newcommand{\offset}{{\mbox{\it offset}}}
\newcommand{\back}{{\mbox{\it back}}}
\newcommand{\lood}{{\mbox{\it load}}}
\newcommand{\congestion}{{\mbox{\it congestion}}}
%%%%%%%%%%%%%%% DO NOT ALLOW ANY LINE TO GO BEYOND THIS LINE %%%%%%%%%%%%%%%%%%
\newcommand{\malyopt}{{\mbox{\tiny\it opt}}}
\newcommand{\adv}{{\mbox{\it adv}}}
\newcommand{\malyadv}{{\mbox{\tiny\it adv}}}

\newcommand{\eps}{\epsilon}
\newcommand{\adversary}{{\mbox{\it R}}}
\newcommand{\Exp}{{\mbox{\it Exp}}}
\newcommand{\reals}{{\bf R}}
\newcommand{\tendsto}{{\rightarrow}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% Temporary macros %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  \newcommand{\Ref}[1]{\ref{#1} {\rm \{#1\}}}
  \newcommand{\Ref}[1]{\ref{#1}}
%  \newcommand{\Cite}[1]{\cite{#1} {\rm \{#1\}}}
  \newcommand{\Cite}[1]{\cite{#1}}
% \newcommand{\Label}[1]{\label{#1} \mbox{$\backslash$ {\rm label\{#1\}}}}
  \newcommand{\Label}[1]{\label{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\today}{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{P and NP}
\author{Lawrence L Larmore}
%\maketitle
%\begin{abstract}
%potentials for online algorithms
%\end{abstract}
%{\bf Keywords:} online, competitiveness, potential \\

This version {\tt
Mon Dec  12 2016
 }%, and still under
%construction.
%Only a few typos are corrected from the
%version dated {\tt Tue Nov 25 06:57:01 PST 2003.}
%{\bf There are no changes from yesterday in the first eleven pages.
%{\bf There may be further changes before class today, but
%probably not major changes, mostly fixing typos.}
%One typo is already fixed.
%{\bf There will be further changes this weekend.}
%{\bf There will be further changes before class today.}

\section*{Easy Shortcut Definitions}
If you read and understand only this section, you'll understand
$\calP$ and $\calN\calP$.

A language $L$ is in the class $\calP$ if there is some
constant $k$ and some machine $M$
(A machine of any class: Turing machine, RAM, virtual C++ machine, or
whatever.) which decides whether a given string $w$ is a member of
$L$, in at most $n^k$ steps, where $n=\barred{w}$.

A language $L$ is in the class $\calN\calP$ if there is some constant $k$
and some non-deterministic machine $M$ such that, given any
string $w\in L$, there is a computation of $M$, with input $w$, which halts in
at most $n^k$ steps, where $n=\barred{w}$, and such that, for any string
$w\notin L$, there is no computation of $M$ with input $w$ which halts.
Note that, since $M$ is non-deterministic,
there could be lots of computations of $M$ with input $w$ that do not halt,
even if $w\in L$.

\subsection*{Verifier Definition of $\calN\calP$}
There is an equivalent definition of $\calN\calP$ which is much easier to
work with, the {\em verifier\/} definition, given below.

Let $L$ be a language.  Then $L$ is $\calN\calP$ if there is an integer $k$
and a program $V$ (called the verifier) such that

\begin{enumerate}
\item
The input of $V$ is an ordered pair of strings $(w,c)$.
\item
Let $n=\barred{w}$.
Then $V$, with input $(w,c)$, halts within $O(n^k)$ steps,
and outputs ``0'' or ``1,'' regardless of the string $c$.
\item
If $w\notin L$, the output of $V$ with input $(w,c)$ is ``0.'' regardless of
$c$.
\item
If $w\in L$, then there is some string $c$ such that $\barred{c}\le n^k$
and the output of $V$ with input $(w,c)$ is ``1.''
(We call $c$ a {\em certificate,} or a {\em witness.})
\end{enumerate}
Of course, you have to choose your witness carefully.

Example: The independent set problem.  For any graph $G$, a set $S$ of vertices
of $G$ is {\em independent\/} if no two members of $S$ are neighbors.
An instance of the independent set problem is an ordered pair $(G,k)$,
where $G$ is a graph and $k$ is an integer.  We can write the ordered pair
as a string: $\angled{G,k}$.
Let
$L_{IND} = \braced{\angled{G,k}
\suchthat\mbox{\ G
has an independent set of size\ } k}$.

For this example, a witness for the ordered pair $\angled{G,k}$ is
simply an independent set $S$ of $k$ vertices of $G$, or more properly,
a string $\angled{S}$ which encodes $S$.



\section*{$\calP$ And $\calN\calP$}

Throughout, if we say ``machine" we mean deterministic machine,
unless we specially say ``non-deterministic."
\vskip 0.1in
For a definition of the classes $\calP$-TIME and $\calN\calP$-TIME,
usually abbreviated as simply $\calP$ and $\calN\calP$, respectively,
read the file
\begin{verbatim}
    http://www.egr.unlv.edu/~larmore/Courses/CSC456/NP/npcomplete.html
\end{verbatim}
(There are, of course, many other discussions of this topic on the web.)
\vskip 0.1in
Recall that a language $L$ is in $\calP$ if and only if there is some
machine that accepts $L$ in polynomial time, and that
a language $L$ is in $\calN\calP$ if and only if there is some
non-deterministic machine that accepts $L$ in polynomial time.

\begin{theorem}\label{thm: accept = decide for p}
A language $L$ is in $\calP$ if and only if there is some
machine that decides $L$ in polynomial time.
\end{theorem}

Actually, this is usually the definition of the class $\calP$.

\begin{definition}\label{def: npcomplete}
{\rm
We say that a language $L$ is {\em $\calN\calP$-complete\/} if the
following two conditions are satisfied:
\begin{enumerate}
\item\label{cond: in np} $L\in\calN\calP$
\item\label{cond: reduces}
For any $L_2\in\calN\calP$, there exists a 
polynomial time reduction of $L_2$ to $L$.
\end{enumerate}
}
\end{definition}

\begin{theorem}\label{thm: npcomplete shortcut}
If $L_1$ is $\calN\calP$-complete, $L\in\calN\calP$, and
there is a polynomial time reduction of $L_1$ to $L$, then $L$
is $\calN\calP$-complete.
\end{theorem}

\begin{proof}
Condition \ref{cond: in np} of the definition is given.
To prove Condition \ref{cond: reduces}, let $L_2\in\calN\calP$.
Since $L_1$ is $\calN\calP$-complete, there is a polynomial time
reduction of $L_2$ to $L_1$.
By hypothesis, there is a polynomial time reduction of $L_1$  to $L$.
Composing these two reductions, we obtain a polynomial time reduction
of $L_2$ to $L$.
\end{proof}

\begin{theorem}\label{thm: npcomplete in p implies p = np}
If $L\in\calP$ and $L$ is $\calN\calP$-complete, then $\calP=\calN\calP$.
\end{theorem}

\begin{proof}
Trivially, $\calP\subseteq\calN\calP$.  We need only show that
any $L_2\in\calN\calP$ is in $\calP$.

Suppose that $L_2\in\calN\calP$.
Since $L\in\calP$, there is a machine $M_1$
that decides $L$ in polynomial time.
Since $L$ is $\calN\calP$-complete, there is a polynomial time
reduction of $L_2$ to $L$, computed by some machine $M_2$.
Connecting the input of $M_1$ with the output of $M_2$, we obtain a
machine that decides $L_2$ in polynomial time.  Thus, $L_2\in\calP$.
\end{proof}

\subsection*{Certificates}

Given an $\calN\calP$ language $L$, we define a {\em certificate system\/}
of $L$ as follows:
\begin{enumerate}
\item
There is a language $L_C$, which we call the {\em certificate language\/}.
\item
Let ``$\sharp$'' be some symbol which is not in the alphabet of either
$L$ or $L_C$.
There is a language $L_V\subset L_C\sharp L$, called the
{\em verification language\/},
such that $w\in L$ if and only if there is some $x\in L_C$ such that
$x\sharp w\in L_V$.
We call $x$ a {\em certificate\/} of $w$, because it certifies that
$w\in L$.
\newcounter{jump}
\setcounter{jump}{\value{enumi}}
\end{enumerate}

We define an {\em $\calN\calP$ certificate system\/} of $L$ to be
a certificate system of $L$ which has the following additional properties:

\begin{enumerate}
\setcounter{enumi}{\value{jump}}
\item
There is a polynomial function $F(n)$ such that, for any $w\in L$
such that $\barred{w}=n$, there is a certificate of $w$ of length at
most $F(n)$.
\item
The verification language $L_V$ is in $\calP$.
\setcounter{jump}{\value{enumi}}
\end{enumerate}

We define an {\em $\calP$ certificate system\/} of $L$ to be a $\calN\calP$
 certificate system of $L$ which has the following additional property:


\begin{enumerate}
\setcounter{enumi}{\value{jump}}
\item
There is a machine $M$ which computes some $x\in L_C$ in polynomial
time for any input string $w$, such that $x$ is a certificate for
$w$ if $w\in L$.
\end{enumerate}

\begin{theorem}\label{thm: np iff cert}
A language $L$ is in $\calN\calP$ if and only if it has an $\calN\calP$
certificate system.
\end{theorem}

We first need a definition.
\begin{definition}\label{def: valid comp}
{\rm
Let $M$ be an NTM.
A {\em configuration\/} of $M$ is defined to be a string which encodes
the state of $M$, the tape contents of $M$, and the position of the read/write
head of $M$.  The details do not really matter, but we can use the definition
given on page 129 of the first edition of {\em Introduction to the Theory of
Computation\/} by Michael Sipser, or on page 140 of the second edition,
or page 168 of the third edition.


If $x$ and $y$ are configurations of $M$, we say that $x$ {\em yields\/}
$y$, which we denote $x\vdash y$,
if, given that $x$ is the configuration of $M$ after $t$ steps,
$y$ could be the configuration of $M$ after $t+1$ steps.\footnote{Of course,
if $M$ is deterministic, for any $x$ there can be at most one choice of $y$.}

Without loss of generality, the symbol ``$\vdash$" is not a symbol of the tape
alphabet of $M$, nor the name of a state of $M$.
We define a {\em valid computation\/} of $M$ to be a string
$x^\malyz\vdash x^\malyone\vdash \ldots \vdash x^n$ such that each
$x^i$ is a configuration of $M$,
$x^\malyz$ is a start configuration of $M$, $x^n$ is an accepting
configuration of $M$, and $x^{t-1}\vdash x^t$ for each $t$.  In addition,
we say that this sequence is a {\em valid computation of $M$ with input $w$}
if $x^\malyz$ is the start configuration of $M$ on input $w$.  The {\em time
complexity\/} of the computation is defined to be $n$.

For convenience in our proofs, we shall say that $x\vdash x$ for
any configuration $x$.
}
\end{definition}
Note that, the way we have defined it, a valid computation is a string,
differing slightly from the definition given at the bottom of page
129 of the textbook.

\begin{proof} (of Theorem \ref{thm: bool sat is np complete})
Suppose that  $L$ is a language which has an $\calN\calP$
certificate system.  We can design a non-deterministic program that
accepts $L$ as follows.  First guess $x\in L_C$ in $F(n)$ steps.
Then verify that $x\sharp w\in L_V$ in polynomial time.

Conversely, suppose that $L\in\calN\calP$.  Let $M$ be an NTM which accepts
$L$ in $F(n)$ time, where $F(n)$ is some polynomial time function.
Let $L_C$ be the language of all valid computations of $M$.  We say
that $x\in L_C$ is a certificate of $w\in L$ if $x$ is a valid computation
of time complexity $F(n)$ of $M$ with input $w$, where $n=\barred{w}$.
Note that the length of $x$ is $O(F(n)\cdot(F(n)+n)$, since the space
complexity of a valid computation cannot exceed its time complexity,
plus the size of the input.  Thus, the length of $x$ is a polynomial
function of $n$.
Clearly, $w$ has a certificate in $L_C$ if and only if $w\in L$, and there
is a polynomial time algorithm that verifies that $x$ is a certificate
of $w$, simply by checking that $x$ is a valid computation of $M$ with
input $w$. Thus, we have constructed an $\calN\calP$ certificate system
for $L$.

This completes the proof of Theorem \ref{thm: np iff cert}.
\end{proof}

\begin{theorem}
A language $L$ is in $\calP$ if and only if it has a $\calP$
certificate system.
\end{theorem}

\begin{proof}
Suppose that $L$ has a $\calP$ certificate system.
If $w\in\Sigma^*$, where $\Sigma$ is the alphabet of $L$,
use $M$ to compute $x\in L_C$ is polynomial time.  If $w\in L$,
then it can be verified that $x\sharp w\in L_V$ is polynomial time.

Conversely, suppose $L\in\calP$.
Let $L_C = \braced{1}$, a language with just one string.
We say that 1 is a certificate of every $w\in L$.
Trivially, that certificate can be computed in polynomial time.
Since $L\in \calP$, the language $L_V=\braced{1\sharp w\spacedbar w\in L}$
is in $\calP$.
\end{proof}

% \subsection*{Time-Bounded Halting Problems}

\newcommand{\bool}{{\mbox{\rm bool}}}
\newcommand{\sat}{{\mbox{\rm sat}}}
\newcommand{\knap}{{\mbox{\footnotesize Knapsack}}}
\newcommand{\nph}{{\mbox{\rm nph}}}
\newcommand{\leaves}{{\mbox{\rm leaves}}}
\newcommand{\variable}{{\mbox{\rm variable}}}
\newcommand{\cnft}{{\mbox{\rm 3cnf}}}
\newcommand{\cnftsat}{{\mbox{\rm 3cnf-sat}}}
\newcommand{\mynot}{\sim}
\newcommand{\implies}{\Rightarrow}

% You know that the halting problem is undecidable, but the time-bounded
% version is not.  In general, the time-bounded halting problem is, given
% machine $M$, a recursive function $F(n)$, and a string $w$, does $M$
% accept $w$ in at most $F(n)$ steps?
% 
% Let $\Sigma=\braced{0,1}$, the binary alphabet.
% We must fix a system of encoding NTMs as binary strings, where each
% encoding ends in a recognizable end-of-file suffix.
% %We must also
% %fix a system of encoding polynomial functions, where each ends in
% %a recognizable end-of-file suffix.\footnote{For example, we could
% %encode the function $F(n)=3n^2+5n+1000$ as the binary string which
% %is the binary encoding of the Ascii string:
% %{\tt   3n$\wedge$2+5n+1000\$}}
% Fix an integer $k\ge 1$.
% We formally define the {\em $k$-non-deterministic polynomial time-bounded
% halting problem\/} to be the language $L^k_\nph$ consisting of all
% strings over $\Sigma$ of the form $\angled{M}w$, where
% $M$ is an NTM, $\angled{M}$ is an encoding of $M$,
% and $w$ is an arbitrary
% string, such that $M$ accepts $w$ in $n^k$ time.
% 
% 
% \begin{theorem}\label{thm: nph is np complete}
% $L^k_\nph$ is $\calN\calP$-complete.
% \end{theorem}
% 
% \begin{proof}
% We first prove that $L_\nph\in\calN\calP$, using Theorem
% \ref{thm: np iff cert},
% by showing that $L_\nph\in\calN\calP$ has an $\calN\calP$ certificate system.
% If $<M>w\in L^k_\nph$, then a certificate of $<M>w$ is a valid computation
% $x^\malyz\vdash x^\malyone\vdash \cdots \vdash x^T$ where
% $x^\malyz$ is the start configuration of $M$ with input $w$ and
% where $T\le n^k$, where $n=\barred{n}$.
% This certificate has length $O(n^{2k}$ and can be verified in $O(n^{2k}$
% time, each configuration has length $O(n^k)$, and ``yields" can be checked
% in linear time.
% 
% We now show that every $\calN\calP$ problem can be reduced to
% $L^k$.
% 
% \end{proof}


\subsection*{Boolean Satisfiability}

Generally, we define a {\em Boolean expression\/} to be an expression
involving variables and operators, where all variables have Boolean
type and all operators have Boolean type.\footnote{This definition is much
more restrictive than
the definition of a Boolean expression in a programming language, which
could contain other things, such as the C++ expression
``{\tt n == 5}" where {\tt n} is a variable of integer type.}
A {\em satisfying assignment\/} of a Boolean expression is an assignment
of truth values (there are only two truth values, {\em true\/} and
{\em false\/}) to each variable so that the value of the expression
is {\em true\/}.  If a Boolean expression has a satisfying assignment, we
say it is {\em satisfiable}; otherwise, we say it is a {\em contradiction}.
The {\em Boolean satisfiability problem\/} is to determine that a given
boolean expression is satisfiable.  This problem is $\calN\calP$-complete,
and in fact is our ``base" $\calN\calP$-complete problem, the one we shall
use to determine that other problems are $\calN\calP$-complete.

\subsubsection*{Formal Definition of Boolean Satisfiability}
We first define a context-free language $L_\bool$ to consist of all
boolean expressions using the following rules:
\begin{enumerate}
\item
All variables are written in alphanumeric style, \ie, are strings
containing letters and digits and starting with a letter.
\item
The only operators permitted are
\begin{enumerate}
\item ``$+$" denoting {\em or}.
\item ``$\cdot$" denoting {\em and}.
\item ``$\mynot$" denoting {\em not}.
\item ``$=$" denoting {\em if and only if}.
\item ``$\implies$" denoting {\em implies}.
\end{enumerate}
We apply the following precedence rules:
\begin{enumerate}
\item ``$\mynot$" has precedence over all other operators.
\item ``$\cdot$" has precedence over all operators except ``$\mynot$"
\item ``$+$" has precedence over all operators except ``$\mynot$" and
``$\cdot$"
\item ``$=$" and ``$\implies$" have equal precedence and cannot associate,
to avoid confusion.
That is, $a=b=c$, $a\implies b\implies c$, $a=b\implies c$,
and $a\implies b=c$ are disallowed.
\end{enumerate}
\end{enumerate}
It is an easy exercise to design a context-free grammar for $L_\bool$,
using the alphabet consisting of the operator symbols listed above,
letters and digits, and right and left parentheses.\footnote{In class,
I did not list the operators ``$=$" and ``$\implies$"
but I have decided that including
these operators makes the later discussion easier.}

\paragraph{Certificates for $L_\sat$}
A certificate for any $w\in L_\sat$ is a satisfying assignment.
For example, $x=1,y=0$ is a certificate for the boolean expression
$(x+y)\cdot(\mynot x+\mynot y)$, while the boolean expression
$(x+\mynot x)$ has no certificate.
Since a certificate for any $w\in L$ is no longer than $w$ itself,
and since it can be verified in linear time, we have an
$\calN\calP$ certificate system for $L_\sat$.

\paragraph{Conjunctive normal form.}
We say that $w\in L_\bool$ is in {\em conjunctive normal form\/}
(abbreviated CNF) if it is the conjunction of clauses, where each
clause is the disjunction of terms, and each term is either a variable
or the negation of a variable.

\begin{definition}\ 

\begin{enumerate}
\item
$L_\sat$ is the subset of $L_\bool$ consisting of all
satisfiable boolean expressions.
\item
$L_\cnft$ is the subset of $L_\bool$ consisting of all
boolean expressions in conjunctive normal form where each clause has
exactly three terms.
\item
$L_\cnftsat = L_\cnft\cap L_\sat$.
\end{enumerate}
\end{definition}

We give context-free grammars for both $L_\bool$ and $L_\cnft$ in the
appendix.

\begin{theorem}\label{thm: bool sat is np complete}
$L_\sat$ is $\calN\calP$-complete.
\end{theorem}

We define a {\em simple clause\/} of a boolean expression to be
a boolean expression of one of the following three forms:
\begin{enumerate}
\item $(v)$ for some variable $v$
\item $(\mynot v)$ for some variable $v$
\item $(u=v)$ for some variables $u,v$
\end{enumerate}

If $M$ is an NTM, then a {\em configuration\/} of $M$ is a string
of the form $xqy$, where $x$ and $y$ are strings of tape symbols (including
the symbol which represents blank) and $q$ is a state.  We can ``pad"
a configuration, making it longer, by adding as many additional blanks
as we wish to $y$.

A configuration can then be translated into a string over the boolean
alphabet $\Sigma=\braced{0,1}$, by fixing binary encodings of the tape symbols
and states.  It is important for our purposes that there is some fixed $k$
such that each tape symbol and each state is encoded by exactly $k$ binary
symbols.

A string of binary symbols of length $n$ can then be thought of as an ordered
$n$-tuple of truth values, where 0 represents {\em false\/} and 1 represents
{\em true}.  If $v[1..n]$ is an array of type boolean, we can think of
a string of binary symbols of length $n$ as an {\em assignment\/}
of that array, where $v[i]$ is assigned the truth value corresponding to
the $i^\tH$ symbol of the string.

If $x,y$ are binary encodings of configurations of $M$ of the same length,
say $n$, (which can
always be made true by padding) then the statement that $x$ yields $y$,
written $x\vdash y$, is then a function of boolean type with $2n$
boolean parameters, which we call
{\tt yields(x[1],\ldots x[kn],y[1], \ldots y[kn])}, or simply
{\tt yields(x,y)}.  For any fixed $n$, you could write that function
using a single statement in the body, which would be a return statement
where the right hand side is a boolean expression with $2n$ variables.
(You probably wouldn't do it that way, but you could.)

%Suppose that each symbol of each configuration of $M$ is represented by
%$k$ bits, where $k$ is a constant (\ie, dependent only on $M$).

If a configuration is of the form $aqb$ where $a,b$ are tape symbols
(including possibly the blank symbol) and $q\in Q$, we say that it is
a {\em window\/} configuration.  We also say that $qb$ is a window
configuration.  (We need this case to handle the situations where the
head is on the rightmost cell.)

\begin{lemma}\label{lem: boolean func for one rule yield 3}
For any one transition rule of $M$, there is a boolean function $W$
with $6k$ boolean parameters such that
$W(x[1],\ldots x[3k],y[1],\ldots y[3k])$ has the value true if and
only if $x$ is a 3-symbol window configuration of $M$ and $x\vdash y$, where
that one transition rule is used to derive $y$ from $x$.
Further, $W$ is the conjunction of no more than $5k$ simple clauses.
\end{lemma}

\begin{proof}
The tape head is over the cell that contains $b$, and the state is $q$.
If the transition
rule is to write $c$, move right, and change to state $r$, then
the boolean function $W$ will be designed to be true if and only
if there is some $a$ such that $x=aqb$ and $y=acr$.

If the transition
rule is to write $c$, move left, and change to state $r$, then
the boolean function $W$ will be designed to be true if and only
if there is some $a$ such that $x=aqb$ and $y=rac$.

In either case, $W$ is the conjunction of $5k$ simple clauses,
and has $6k$ terms.
\end{proof}

\begin{lemma}\label{lem: bool func for one rule yield 2}
For any one transition rule of $M$ which causes a right movement of the
head, there is a boolean function $W$
with $4k$ boolean parameters such that
$W(x[1],\ldots x[2k],y[1],\ldots y[2k])$ has the value true if and
only if $x$ is a 2-symbol window configuration of $M$ and $x\vdash y$, where
that one transition rule is used to derive $y$ from $x$.
Further, $W$ is the conjunction of no more than $4k$ simple clauses.
\end{lemma}

We omit the proof of Lemma \ref{lem: bool func for one rule yield 2}, which
is similar to that of Lemma \ref{lem: boolean func for one rule yield 3}.

\begin{lemma}\label{lem: boolean func for rule yield 3}
If $M$ has $R$ transition rules, there is a boolean function $W$
with $6k$ boolean parameters such that
$W(x[1],\ldots x_[3k],y[1],\ldots x[3k])$ has the value true if and
only if $x$ is a window configuration of $M$ and $x\vdash y$.
Further, $W$ has no more than $6k(R+1)$ terms.
\end{lemma}

\begin{proof}
Let $W_1,\ldots W_R$ be the boolean functions given by Lemma
\ref{lem: boolean func for one rule yield 3} for each rule.
Let $W_0$ be the boolean function that says that $x=y$, namely
$(x[1]=y[1])\cdot\ (x[2]=y[2])\cdot\  \cdots\  \cdot(x[3k]=y[3k])$.
Now let $W=W_0+W_1+\cdots +W_R$.
\end{proof}

\begin{lemma}\label{lem: bool func for rule yield 2}
If $M$ has $R$ transition rules, there is a boolean function $W$
with $4k$ boolean parameters such that
$W(x[1],\ldots x_[2k],y[1],\ldots x[2k])$ has the value true if and
only if $x$ is a window configuration of $M$ and $x\vdash y$.
Further, $W$ has no more than $4k(R+1)$ terms.
\end{lemma}

We omit the proof of Lemma \ref{lem: bool func for rule yield 2}, which
is similar to that of Lemma \ref{lem: boolean func for rule yield 3}.

\begin{lemma}\label{lem: boolean func for yield}
For each $n$, there is a boolean function
$e(x_1,\ldots x_{kn},y_1,\ldots y_{kn})$
where, if $x,y$ are binary encodings of configurations of $M$
of the same length $n$,
$e(x[1],\ldots x[kn],y[1],\ldots y[kn])$ is true
if and only if $x\vdash y$, and if the last symbol of $x$ is not a state
symbol.
Furthermore, the function $e$ can be written as a boolean expression whose
number of terms is polynomial in $n$.
\end{lemma}


\begin{proof}
For each $1< i< n$, let $w^x_i$ be the substring of $x$
consisting of the three symbols in positions $i-1$ through $i+1$.
Let $e$ be the boolean function given by Lemma
Lemma \ref{lem: boolean func for rule yield 3}.
Then define
$e_i(x[1],\ldots x[kn],y[1],\ldots y[kn])$ to be
the function
$((x[1]=y[1])\cdot\ \cdots\ \cdot(x[ki-2k]=y[ki-2k]))\cdot e(x[ki-2k+1],
\ldots x[ki+k],y[ki-2k+1],\ldots,y[ki+k])\cdot
((x[ki-2k+1]=y[ki-2k+1])\cdot\ \cdots\ \cdot(x[kn]=y[kn]))$
which is true if and only if $x$ is a configuration of $M$, $x\vdash y$,
and $x$ has a state symbol in position $i$.
Similarly, using
Lemma \ref{lem: bool func for one rule yield 2}, we can define a function

$e_\malyone(x[1],\ldots x[kn],y[1],\ldots y[kn])$
which is true if and only if $x$ is a configuration of $M$, $x\vdash y$,
and $x$ has a state symbol in position $1$.
By construction, we can see that each $e_i$ can be written as a boolean
expression whose number of terms is polynomial in $n$.
We now define $e = e_\malyone + e_\malytwo + \cdots + e_{n-1}$.
\end{proof}

\begin{proof} (of Theorem \ref{thm: bool sat is np complete}.)
Our method is to show that, for any NTM $M$,
for any polynomial function $F$, and for every
string $w$, where we write $n=\barred{w}$, there is a boolean expression
$E = E_{M,w,F}$ whose length is $O(F(n)^3\log(F(n)))$,
and which is satisfiable if and
only if $M$ accepts $w$ in $F(n)$ time.  Furthermore, $E_{M,w,F}$
can be calculated, given input $w$, in $G(n)$ time for some polynomial
function $G$.  Our method will be that $E$ is satisfiable if
and only if there is a valid computation of $M$ of length at most $F(n)$
which starts with the initial configuration of $M$ with input $w$.

We can assume that each configuration has length exactly $F(n)+2$,
no configuration in a valid computation than the length of the computation
plus 2, and we can ``pad" any shorter configuration by adding blanks.
Pick a constant $k$ such that $2^k$ is at least the sum of the number of
states of $M$ and the size of the tape alphabet of $M$, including the blank
symbol.  Then, encode all states and tape symbols, including blank, as
unique binary strings of length $k$.  Let $N=k(F(n)+2)$.  We can thus
represent every configuration of $M$ that could be used in our proof as
a binary string of length $N$.

Write $T=F(n)$.
We can assume that a valid computation of at most length $T$ has
length exactly $T$, and thus exactly $T+1$ configurations,
by repeating the accepting configuration as many times as necessary.

A binary string of length $N$ can be considered to be an array of length $N$
of boolean type, \ie, an array of $N$ boolean variables.  $E$ will have
exactly $N(T+1)$ distinct variables, where the variable
$\braced{v_{t,i}}$ represents the $i^\tH$ bit of the configuration $x^t$.

There is then a one-to-one correspondence between assignments of these
variables, and strings of the form
$x^\malyz\vdash x^\malyone\vdash \cdots \vdash x^T$,
where each $x^t$ is a boolean string of length $N$.
The boolean expression $E$ will be designed in such a way that a particular
assignment of its variables is satisfying if and only if the corresponding
string is a valid computation of $M$ with input $w$.

%{\sc Under construction, but almost finished.}
\end{proof}

\begin{theorem}\label{thm: 3cnf sat is np complete}
$L_\cnftsat$ is $\calN\calP$-complete.
\end{theorem}

\begin{proof}
We will use Theorems \ref{thm: npcomplete shortcut} and
\ref{thm: bool sat is np complete}.

It is trivial that $L_\cnftsat\in\calN\calP$, since a satisfying
assignment of any $w\in L_\cnftsat$ can be verified in linear time.
We now give a polynomial time reduction of $L_\sat$ to $L_\cnftsat$.
We will use the context-free grammar for $L_\bool$ given in the appendix.
Let $\Sigma$ be the alphabet of $L_\bool$.
For any $w\in L_\bool$, we will construct a string $F(w)\in L_\cnft$
such that $w\in L_\sat$ if and only if $F(w)\in L_\cnftsat$, and such
that $F$ can be computed in polynomial time.

To use Theorem \ref{thm: npcomplete shortcut}, we need to compute $F(w)$ for
all $w\in\Sigma^*$.  If $w\not\in L_\bool$, we define $F(w)=\epsilon$.
Since $L_\bool$ is a context-free language, this part of the program
can be done in polynomial time.

Henceforth, we assume that $w\in L_\bool$.
Let $\calT$ be a parse tree for $w$, using the grammar given in the
appendix.  If $\calN$ is any internal node of the parse tree, we write
$\leaves(\calN)\in\Sigma^*$ to be the string of all the terminals in the
subtree rooted at $N$, in left-to-right order.  Thus, for example,
if $\calN$ is the root of $\calT$, then $\leaves(\calN)=w$.

We first assign a unique name to each internal node of $\calT$, which
will be a subscripted grammar symbol.  For example, the nodes whose grammar
symbol is $S$ will be given the names $S_1, S_2, \ldots $ and so forth.
We can assume that $S_1$ is the root node of $\calT$.

Each internal node whose grammar symbol is $S$, $E$, $T$, or $F$, corresponds
to a derivation where the variable grammar symbols have subscripts.
For example, the internal node $E_5$ might correspond to the subscripted
derivation $E_5\to E_6+T_9$.

We then assign a string $\variable(\calN)$, which we will use as the name
of a variable of boolean type,
to each internal node of $\calN$ of $\calT$ whose grammar symbol
is $S$, $E$, $T$, $F$, or $V$.  (We do not assign strings to the
internal nodes whose grammar symbols are $P$, $A$, or $N$.)  We use
the following rules in making this assignment:
\begin{enumerate}
\item $\variable(S_i) = s\angled{i}$ for each $i$,
where $\angled{i}$ is the decimal numeral for $i$.
(For example, $\variable(S_{27}) = s27$.)
\item $\variable(E_i) = e\angled{i}$ for each $i$.
\item $\variable(T_i) = t\angled{i}$ for each $i$.
\item $\variable(F_i) = f\angled{i}$ for each $i$.
\item\label{rule: V}
$\variable(V_i)=\leaves(V_i)$
%\item\label{rule: unique}
%All values of $\variable$ are unique as much as possible, subject
%to rule \ref{rule: V}.  That is, the list of variable names
%$\variable(S_1),\ldots \variable(E_1),\ldots
%\variable(T_1),\ldots \variable(F_1),\ldots$ contains no duplication,
%and none are equal to $\leaves(V_i)$ for any $i$.
%\item\label{rule: short}
%None of the variable names
%$\variable(S_1),\ldots \variable(E_1),\ldots
%\variable(T_1),\ldots \variable(F_1),\ldots$ are longer than $\log n$,
%where $n$ is the length of $w$.
%(It is possible to enforce this rule because the number of available
%names of this length exceeds the number of internal nodes of the
%parse tree.)
\end{enumerate}
We call the variables assigned to the $S$, $E$, $T$, and $F$ nodes
{\em internal parse tree variables}.

We now define a string $u\in L_\bool$ which consists of the conjunction
of a number of clauses, one corresponding to each internal node
of the parse tree, plus one more, which we call the {\em top clause\/}.
Those clauses are defined as follows:
\begin{enumerate}
\item
$(s1)$ is a clause of $u$.  This is the top clause of $u$.
\item
If there is a subscripted derivation $S_i\to E_j=E_k$, then
$(s\angled{i}=(e\angled{j}=e\angled{k}))$ is a clause of $u$.
\item
If there is a subscripted derivation $S_i\to E_j\implies E_k$, then
$(s\angled{i}=(e\angled{j}\implies e\angled{k}))$ is a clause of $u$.
\item
If there is a subscripted derivation $S_i\to E_j$, then
$(s\angled{i}=e\angled{i})$ is a clause of $u$.
\item
If there is a subscripted derivation $E_i\to T_j$, then
$(e\angled{i}=t\angled{j})$ is a clause of $u$.
\item
If there is a subscripted derivation $E_i\to E_j+T_k$, then
$(e\angled{i}=(e\angled{j}+t\angled{k}))$ is a clause of $u$.
\item
If there is a subscripted derivation $T_i\to F_j$, then
$(t\angled{i}=f\angled{j})$ is a clause of $u$.
\item
If there is a subscripted derivation $T_i\to T_j\cdot F_k$, then
$(t\angled{i}=t\angled{j}\cdot f\angled{k})$ is a clause of $u$.
\item
If there is a subscripted derivation $F_i\to \mynot F_j$, then
$(f\angled{i}=\mynot f\angled{k})$ is a clause of $u$.
\item
If there is a subscripted derivation $F_i\to (S_j)$, then
$(f\angled{i}=s\angled{j})$ is a clause of $u$.
\item
If there is a subscripted derivation $F_i\to V_j$, then
$(f\angled{i}=\variable(V_j))$ is a clause of $u$.
\end{enumerate}
All the clauses of $u$ other than the top clause we call {\em internal
clauses\/}.  The variable to the left side of the first ``$=$" in an
internal clause we call the {\em left hand side\/} of the clause.
The expression to the right of the first ``$=$" in an
internal clause we call the {\em right hand side\/} of the clause.

\begin{lemma}\label{clm: u sat iff w sat}
$u$ is satisfiable if and only if $w$ is satisfiable.
\end{lemma}

\begin{proof}
The set of variables in $u$ is the set of variables of $w$ together
with the internal parse tree variables.  For any assignment of truth values
of the variables of $w$, there is a unique assignment of the internal
parse tree variables that makes all the internal clauses true, which
can be computed as follows.  There is one internal clause for each
internal node of the tree labeled $S$, $E$, $T$, or $F$.  Visit these
in bottom-up order.  For each such clause, we evaluate the right hand side,
since the truth values of all variables in the right hand side have been
assigned.  We then assign that same value to the left hand side of the
clause.  These assignments, together with the assignments of the
truth values of the variables of $w$, constitute an assignment of the truth
values of all variables of $u$.  All internal clauses of $u$ are satisfied
by this assignment, so the assignment satisfies $u$ if and only if it
satisfies the top clause $(s1)$.  But that is true if and only if
the original assignment of the variables of $w$ is a satisfying assignment.

This concludes the proof of Lemma \ref{clm: u sat iff w sat}.
\end{proof}

We now construct a boolean expression $v$ in conjunctive normal form
which is equivalent to $u$, by replacing each internal clause of $u$ with an
equivalent boolean expression in conjunctive normal form, and where each
clause has at most three terms.

\begin{itemize}
\item
The top clause (s1) is not replaced.
\item
A clause of the form $(x=y)$ is replaced by $(x+\mynot y)\cdot(y+\mynot x)$.
\item
A clause of the form $(x=\mynot y)$ is replaced by
$(x+y)\cdot(\mynot y+\mynot x)$.
\item
A clause of the form $(x=y+z)$ is replaced by
$(x+\mynot y)\cdot(x+\mynot z)\cdot(\mynot x+y+z)$.
\item
A clause of the form $(x=y\cdot z)$ is replaced by
$(x+\mynot y+\mynot z)\cdot(\mynot x+y)\cdot(\mynot x+z)$.
\item
A clause of the form $(x=(y=z))$ is replaced by\\
$(x+y+z)\cdot(x+\mynot y+\mynot z)\cdot(\mynot x+y+\mynot z)\cdot
(\mynot x+\mynot y+z)$
\item
A clause of the form $(x=(y\implies z))$ is replaced by
$(x+y)\cdot(x+\mynot z)\cdot(\mynot x+\mynot y+z)$.
\end{itemize}

Since $v$ is equivalent to $u$, then, by Lemma \ref{clm: u sat iff w sat},
$v$ is satisfiable if and only if $w$ is satisfiable.
We now define $F(w)$ by expanding each clause of $v$ so that it has
exactly three terms, \eg, we replace $(x+y)$ by $(x+x+y)$.
Thus, $F(w)$ is satisfiable if and only if $w$ is satisfiable.

Finally, we must show that $F(w)$ can be computed in polynomial time.
Suppose $\barred{w}=n$.  Then $\calT$ has $O(n)$ nodes, and can be
computed in $O(n)$ time by a lexical analyzer followed by an LALR parser.
Then $u$ can be computed from $\calT$ in $O(n)$ time, $v$ can be computed
from $u$ in $O(n)$ time, and $F(w)$ can be computed from $v$ in $O(n)$
time.

This concludes the proof of Theorem \ref{thm: 3cnf sat is np complete}.
\end{proof}

\subsection*{Other $\calN\calP$-Complete Problems}
The most common method of proving that a given problem (\ie, language)
is $\calN\calP$-complete is to use Theorem \ref{thm: npcomplete shortcut},
where $L_1$ is taken to be a problem (\ie, language) already known to be
$\calN\calP$-complete.  The problem $L_\cnftsat$ is one of the more
popular choices used for this purpose.\footnote{The precise
definition of the problem described in this handout as $L_\cnftsat$
differs from book to book, but they are all equivalent.}

\subsubsection*{The Independent Set Problem}
Given a graph $G$ and a number $k$, an {\em independent set\/} of $G$
is defined to be a set $\calI$ of vertices of $G$ such that no two
members of $\calI$ are connected by an edge of $G$.  The {\em order\/}
of $\calI$ is defined to be its size, \ie., simply how many vertices
it contains.

An instance of the {\em independent set problem\/} consists of a graph
$G$ and a number $k$.  The question is, "Does $G$ have an independent set
of order $k$?"

\newcommand{\ind}{{\mbox{\rm ind}}}
\newcommand{\iind}{{\mbox{\rm instance-ind}}}

\paragraph{The language $L_\ind$.}
Pick an alphabet $\Sigma$ (without loss of generality, $\Sigma$ is
set of Ascii symbols, including an ``end-of-file" symbol) and decide
on a method of encoding graphs.  For any graph $G$, let $\angled{G}$
be the encoding of $G$ by that method.  We insist that $\angled{G}$
have a recognizable and unique end of file suffix, \ie, it has
a suffix that appears as a substring nowhere else in $\angled{G}$.
For any number $k$, let $\angled{k}$ be an encoding of $k$.

Now, let $L_\iind=\braced{\angled{G}\angled{k}}$, and let
$L_\ind\subseteq L_\iind$
be the set of all $\angled{G}\angled{k}$ such that $G$ has an independent
set of order $k$.  The purpose of the end of file suffix is to enable
a machine reading $w=\angled{G}\angled{k}\in L_\iind$ to 
tell where $\angled{G}$ ends and $\angled{k}$ begins.\footnote{If
$\Sigma$ is the Ascii alphabet,
we can require that the end of file suffix be the single end-of-file
symbol, and that the encoding of a number be its decimal numeral.
Alternatively, we could have said that
$G$ and $k$ must be encoded in binary, and that the end of file suffix
is the string `111111', or some other string we choose in advance.  But
whether we use Ascii or binary or some other encoding does not matter.}

\begin{theorem}\label{thm: ind set np complete}
$L_\ind$ is $\calN\calP$ complete.
\end{theorem}

\begin{proof}
We first define a certificate system for $L_\ind$.  For any
$w=\angled{G}\angled{k}\in L_\ind$, a certificate for $w$ is
an encoding $\angled{\calI}$ of some independent set $\calI$
of $G$ of order $k$.  Since that encoding can be made shorter than
$\angled{G}$ itself, and since a simple program can easily verify
a certificate, we have, by Theorem \ref{thm: np iff cert}, that
$L_\ind\in\calN\calP$.

We will use Theorems \ref{thm: npcomplete shortcut} and
\ref{thm: 3cnf sat is np complete} to complete the proof, by
showing that there is a polynomial time reduction of $L_\cnftsat$
to $L_\ind$.  Let $\Sigma$ be an alphabet which includes the
alphabet of $L_\cnft$ and also the alphabet of $L_\iind$.
For any $w\in\Sigma^*$, we will define a string $F(w)\in\Sigma^*$
such that:
\begin{enumerate}
\item If $w\in L_\cnft$, then $F(w)\in L_\iind$, else $F(w)$ is
the empty string.
\item $w\in L_\cnftsat$ if and only if $F(w)\in L_\ind$.
\end{enumerate}
We now proceed to define $F(w)$ for a given $w\in L_\cnft$.
We write $w=C_\malyone\cdot C_\malytwo\cdot \cdots \cdot C_k$,
where $C_i=\parend{t_{i,\malyone}+t_{i,\malytwo}+t_{i,\malythree}}$,
where each $t_{i,j}$ is either $x$ or $\mynot x$, where $x$ is
a string which represents a variable.

We now define a graph $G=(V,E)$, and then define $F(w)=\angled{G}\angled{k}$.
We let $V$ be a set of vertices $\braced{v_{i,j}|1\le i\le k, 1\le j\le 3}$.
$E$ is defined as follows:
\begin{enumerate}
\item
For each $i$, there is an edge from $v_{i,j}$ to $v_{i,j'}$
for all $1\le j < j' \le 3$.
\item
If $t_{i,j} = x$ and $t_{i',j'}=\mynot x$ for some string $x$,
there is an edge from $v_{i,j}$ to $v_{i',j'}$.
\item There are no other edges.
\end{enumerate}

We now show that $F(w)\in L_\ind$ if and only if $w$ is satisfiable.
For each $i$, let $K_i$ be the subgraph of $G$ consisting of the
three vertices $v_{i,\malyone}$, $v_{i,\malytwo}$, $v_{i,\malythree}$,
and the edges connecting them.
Suppose that $\calI$ is an independent set of $G$ of order of $k$.
Since $\calI$ is independent, it cannot contain more than one vertex
from each $K_i$.  Since it has order $k$, it must then contain exactly
one vertex from each $K_i$.
For each $i$, let $j(i)\in\braced{1,2,3}$ be defined such that
$v_{i,j(i)}\in\calI$.
We now define an assignment of $w$, as follows:
\begin{enumerate}
\item
For any $i$, if
$t_{i,j(i)} = x$ for some variable $x$, we assign $x = $ {\em true}.
\item
For any $i$, if
$t_{i,j(i)} = \mynot x$ for some variable $x$, we assign $x = $ {\em false}.
\item
If a variable $x$ used in $w$ is not assigned using the above two rules,
we assign $x = $ {\em false}.  (Actually, we could assign $x$ either truth
value.)
\end{enumerate}
We claim that the above assignment is well-defined and satisfies $w$.
Suppose the assignment is not well-defined, \ie, the same variable $x$
is assigned to be both {\em true\/} and {\em false}.
That implies that $t_{i,j(i)} = x$ and $t_{i',j(i')} = \mynot x$,
where $i\ne i'$.  But this is impossible since, in $G$, there is an edge from
$v_{i,j(i)}$ to $v_{i',j(i')}$.
The assignment satisfies $w$ because it satisfies every clause;
for each $i$, $C_i$ is satisfied because the term $t_{i,j(i)}$ is true
under the assignment.

Conversely, suppose that $w$ has a satisfying assignment.
For each $i$, at least one term of $C_i$ must be true under the assignment.
Let $j(i)\in\braced{1,2,3}$ be defined such that
$t_{i,j(i)}$ is true under the assignment.  If more than one term of $C_i$
is true under the assignment, $j(i)$ can be chosen arbitrarily.
Now, define $\calI = \braced{v_{i,j(i)}}$, which clearly has order $k$.
If $\calI$ were not independent, there would have to be an edge between
two members of $\calI$.  Since $\calI$ contains just one member of each
$K_i$, this edge would have to be from $v_{i,j(i)}$ to $v_{i',j(i')}$,
where $t_{i,j(i)}=x$ and $t_{i',j(i')=\mynot x}$ for some variable $x$,
and where $i\ne i'$.  Under the given assignment, both of those terms
must be true, which is a contradiction.

This completes the proof of Theorem \ref{thm: ind set np complete}.
\end{proof}

\subsection*{The Knapsack Problem}
Informally, the knapsack problem is whether there is a subset of a given
set of items that fits exactly into a given knapsack.  Formally, an
instance of the knapsack problem is a finite sequence
$x_\malyone, \ldots x_\malyk$ of non-negative numbers
and a single number $B$.  This instance is
a member of the language $L_{\mbox{\footnotesize Knapsack}}$ if
there is some subsequence of $\braced{x_\maly{i}}$ whose sum is $B$.

\begin{theorem}
The knapsack problem is $\calN\calP$-complete.
\end{theorem}

\begin{proof}
Trivially, the knapsack problem satisfies the verifiability definition
of $\calN\calP$.

We reduce the independent set problem to the knapsack problem.

Suppose $\angled{G}\angled{k}$ is an instance of the independent set
problem.  Let $v_\malyz, \ldots v_\maly{n-1}$ and
 $e_\malyz \ldots e_\maly{m-1}$ be the vertices and edges of $G$.
Our technique is to choose a number $B$, and to make each vertex and each
edge of $G$ into an item, assigning weights in such a way that a set of items
$S$ has weight $B$ if and only if the following conditions hold:
\begin{enumerate}
\item
If $e_\maly{j}$ is any edge, then $e_\maly{j}$ is either in $S$
or is incident to a vertex in $S$, but not both.
\item
$S$ contains exactly $k$ vertices.
\end{enumerate}
We assign weights as follows.
\begin{itemize}
\item
$w(e_\maly{j}) = 4^j$
\item
The weight of any vertex is $4^m$, plus
the sum of the weights of its incident edges.
\item
$B=4^m\,k+\sum_{j=0}^{m-1}4^j$
\end{itemize}
It helps to write all numbers in base 4.  Then $B=k111\ldots1111$,
where we allow the $k$ on the left end to overflow into other places.
The $j^\tH$ edge has weight $0000\ldots0001000\ldots00000$, where the single
digit 1 is in the $j^\tH$ place.  The weight of vertex is written as
a base 4 numeral with $(\delta+1)$ 1's, where $\delta$ is the degree of
the vertex.  For example, if $m=9$ and
$v_4$ is incident to $e_2$, $e_5$, and $e_6$, then $w(v_4)$ is written
is base 4 as $1000110010$.
\end{proof}

\subsection*{Appendix}

\subsubsection*{Context-free grammar for $L_\bool$}

\noindent
The start symbol is $S$.

$S\to E=E\spacedbar E\implies E\spacedbar E$

$E\to E+T\spacedbar T$


$T\to T\spaced{\cdot}F\spacedbar F$


$F\to\ \mynot F\spacedbar V\spacedbar (S)$

$V\to AP$

$P\to AP\spacedbar NP\spacedbar \epsilon$

$A\to a\spacedbar b\spacedbar c\spacedbar d\spacedbar e\spacedbar f
\spacedbar g\spacedbar h\spacedbar i\spacedbar j\spacedbar k\spacedbar l
\spacedbar m\spacedbar n\spacedbar o\spacedbar p\spacedbar q
\spacedbar r\spacedbar s\spacedbar t\spacedbar u\spacedbar v
\spacedbar w\spacedbar x\spacedbar y\spacedbar z$

$N\to 0\spacedbar 1\spacedbar 2\spacedbar 3\spacedbar 4\spacedbar 5
\spacedbar 6\spacedbar 7\spacedbar 8\spacedbar 9$

\subsubsection*{Context-free grammar for $L_\cnft$}

\noindent
The start symbol is $E$.

$E\to E\spaced{\cdot}C\spacedbar C$

$C\to (T+T+T)$

$T\to\ \mynot V\spacedbar V$

$V\to AP$

$P\to AP\spacedbar NP\spacedbar \epsilon$

$A\to a\spacedbar b\spacedbar c\spacedbar d\spacedbar e\spacedbar f
\spacedbar g\spacedbar h\spacedbar i\spacedbar j\spacedbar k\spacedbar l
\spacedbar m\spacedbar n\spacedbar o\spacedbar p\spacedbar q
\spacedbar r\spacedbar s\spacedbar t\spacedbar u\spacedbar v
\spacedbar w\spacedbar x\spacedbar y\spacedbar z$

$N\to 0\spacedbar 1\spacedbar 2\spacedbar 3\spacedbar 4\spacedbar 5
\spacedbar 6\spacedbar 7\spacedbar 8\spacedbar 9$

\eject

\subsubsection*{Completing the Lecture of November 30, 2016}

The notation I used during this semester (Fall 2016) differs slightly from
the notation in the $\calN\calP$ document,
but not so much that you should be confused by it.

The problem was to show a reduction of SAT to 3SAT.  In the $\calN\calP$
document
I refer to 3SAT $L_\cnftsat$.  That reduction $R$ is completely explained
in the $\calN\calP$ document.  However, I did not finish with the one example
I had on the board on November 30.


That was to give $R(e)$, where:

$$e \equiv \parend{x1 + \mynot x2} \Rightarrow \mynot x1 * x3$$
The parse tree for $e$, using an ambiguous version
of context-free grammar given in the $\calN\calP$ handout:
\vskip 0.3in
\centerline{\epsfig{file=f161130.eps,width=2in}}
\vskip 0.3in
\noindent
Our next step is to translate the parse tree into the conjunction of clauses:
$$
\parend{u4 = x1 + u3}*
\parend{u3 = \mynot x2}*
\parend{u6 = \mynot x1}*
\parend{u8 = u6 * x3}*
\parend{u9 = u4 \Rightarrow u8}*
u9
$$
\vskip 0.3in
\noindent
Finally, we translate into 3-CNF form by replacing each of those clauses by the
conjunction of CNF clauses of at most three terms:

\noindent
$
\parend{u4 + \mynot x1}*\parend{u4 + \mynot u3}*\parend{\mynot u4 + x1 + u3}*\\
\parend{u3 + x2}*\parend{\mynot u3 + \mynot x2}*\\
\parend{u6 + x1}*\parend{\mynot u6 + \mynot x1}*\\
\parend{u8 + \mynot u6 + \mynot x3}*\parend{\mynot u8 + u6}*
\parend{\mynot u8 + x3}*\\
\parend{u9 + u4}*\parend{u9 + \mynot u8}*\parend{\mynot u9 + \mynot u4 + u8}*\\
u9
$

\vskip 0.3in
\noindent
We can then ``pad" each clause of length less than three by duplicating terms,
so that each clause has exactly three terms.
For example, we can replace $\parend{u4 + \mynot x1}$
with $\parend{u4 + u4 + \mynot x1}$, and $u9$ with $\parend{u9 + u9 + u9}$.

\section*{Reduction of Knapsack to Partition}

The knapsack problem can be shown to be $\calN\calP$-complete by reducing
3-SAT to Knapsack.  I did not do this in class during the Fall 2016 semester.
We can then show that the partition problem is $\calN\calP$-complete by
reducing Knapsack to Partition.

Recall that an instance of the Knapsack problem is a number followed by
a sequence of positive numbers, namely $\angled{K,x_1,x_2,\ldots x_m}$,
and the answer to such an instance is {\bf true} if and only if
there is some subsequence of $x_1, \ldots x_m$ whose total is $K$.

Similarly, an instance of the Partition problem is a sequence of positive
numbers,
namely $\angled{y_1, \ldots y_\ell}$, and the answer to such an instance
is {\bf true} if and only if there is some subsequence of $y_1,\ldots y_\ell$
whose sum is half the total, {\ie} $\half\sum_{j=1}^\ell y_j$.

The partition problem is trivially in the class $\calN\calP$, since the
solution, if any, can be verified in polynomial time.

\subsection*{Reduction}
Given an instance $I_K=\angled{K,x_1, x_2, \ldots x_m}$ of Knapsack, define
$L=\sum_{i=1}^m x_i - K$.  Let $R(I_K)=I_P$ be the following instance of
Partition: $$I_P=\angled{K+1,x_1,\ldots x_m,L+1}$$

That is, $I_P=\angled{y_1, \ldots y_\ell}$ where $\ell=m+2$,
$y_1 = K+1$, $y_\ell=L+1$, and $y_j=x_{i+1}$ for all other $j$.

We need to prove that this reduction works, that is, that $I_P$ is true
if and only if $I_K$ is true.  There are thus two directions to the proof.

Note that the sum of the items of $I_P$ is $2K+2L+2$.

Suppose that $I_K$ is true.  There is some subsequence of $\braced{x_i}$
whose total is $K$.  The items of this subsequence, together with $L+1$,
have total $K+L+1$, and thus $I_P$ is true.

Conversely, suppose some subsequence $S$ of $K+1,x_1, \ldots x_m,L+1$
has total $K+L+1$.  Clearly that subsequence cannot contain both $K+1$
and $L+1$, since they would exceed the needed value.  Similarly, and by
symmetry, $S$ must contain either $K+1$ or $L+1$.
Without loss of generality, $S$ contains $L+1$.  The remaining members of
$S$ are a subsequence of $x_1, \ldots x_m$ whose total is $K$, and we are done.





\end{document}
