\documentclass[10pt]{article}

\usepackage{hevea,xspace,graphicx,paralist}

\oddsidemargin 0cm
\textwidth 17cm

\newcommand{\question}[1]{#1}
\newcommand{\answer}[1] { {\sf #1}  {\vspace{6ex}}  }
\newcommand{\ignore}[1] {}
\newcommand{\ie}{{\em i.e.},\xspace}
\begin{document}

\thispagestyle{empty}

\begin{center}
\begin{Large}
{\bf CS 3100 -- Models of Computation -- Fall 2010}\\
{\bf Notes for Lecture 24 on Reductions, NP-Completeness}
\end{Large}
\end{center}

\noindent How to solve hard problems?
\begin{compactitem}
  \item Solve them! If you can't, then
  \item Club all of them together!
\end{compactitem}

This is what $A_{TM}$ and $3SAT$ represent!
%
If a problem in NP has a poly algorithm, so do all in the NPC-land 
(thru the P-time mapping reduction!)

If a problem in the undecidable (Turing complete) class have a 
decider, so do all!

\subsubsection*{Notes on ``if'' and ``iff''}

$A \;if\; B$ stands for $B\Rightarrow A$.
%
Examples: $(x\%6=0) \Rightarrow (x\%3=0)$, 
or $(x\%3=0) \;\;if\;\; (x\%6=0)$.  
The set of 
points representing $(x\%6=0)$ is contained in those
representing $(x\%3=0)$.

$A \;\;iff\;\; B$ stands for $B\iff A$ or $A\iff B $.
%
``Iff'' represents ``equal truth'' in some sense. Examples:
\begin{compactitem}
\item One triangle with base B and height H has area A iff 
  any other triangle with the same B and H has the same area
\item Arithmetic induction iff complete induction
  (P(0) and P(n) implies P(n+1) implies for all x:P(x))
  {\bf IFF}
  ((for all m $\leq n$: P(m) implies P(n)) implies for all x:P(x))
\end{compactitem}

\noindent {\em (Negation law of $iff$.)} If $A \iff B$ then
    $A\Rightarrow B$ and     $B\Rightarrow A$.
    This means
    $\neg B\Rightarrow \neg A$ and     $\neg A\Rightarrow \neg B$.
    Thus $\neg A \iff \neg B$. 



\noindent{\bf {Chapter 15, Main Idea Behind Reductions}:\/}
The main idea is to reduce language $A$ into language $B$ through
a {\em mapping reduction.}
%
We will illustrate mapping reductions on the following undecidable problem:
{\sl It is undecidable whether a TM enters a specific state (or whether
a program has dead code at a particular location L).}
%
We call this the {\em state usage} problem and write it StateUsage sometimes.


\noindent{\bf Main Idea behind Mapping Reductions:\/}
Mapping reductions help model a problem in terms of another, such
that if the latter is decidable, so is the former.

The idea is that we must find a {\em Turing computable} function $f$ (for
example, a 
C function $f$ {\bf that itself does not loop}) such that

\[ w\in A \iff f(w) \in B\]

We capture this situation (of the existence of such an $f$) as $A\leq_m B$.
Here are some facts:
\begin{compactitem}
\item If $B$ is recursive, so is $A$.
\item If $A$ is not recursive, then $B$ is not (contrapositive form of the above).
\item $A\leq_m B$ implies $\overline{A}\leq_m \overline{B}$. How so?
  \begin{compactitem}
  \item From the negation law of $iff$ we have
    \( w\notin A \iff f(w) \notin B\)
  \item Or \( w\in \overline{A} \iff f(w) \in \overline{B}\)
  \item Or $\overline{A}\leq_m \overline{B}$.
  \end{compactitem}

\end{compactitem}

\noindent{\bf {StateUsage (whether some code is ``Deadcode'') is Undecidable}:\/}
\begin{compactitem}
  \item The input language $A$ is $A_{TM}$.
  \item Define the output language $B$
    \[ \{ \langle M,q\rangle \;\mid\; M\;visits\;state\;q\}\]
  \item Define the mapping reduction that takes an
    $\langle M,w\rangle$ and produces a
    $\langle M^{'},q\rangle$ where $q$ is a new state not
    used by $M$. {\em Further, we arrange
       $M$ to jump to $q$ whenever $M$ instead would
    have halted in one of the states $h_a$ (this is the
    description of the machine $M^{'}$)}.
 \item  This is a mapping reduction from the whole of $A$ into $B$.
   %
   \begin{compactitem}
     \item    ``There is a point $x$ in $A$'' means
       $x$ is of the form $\langle M,w\rangle$ such
       that $M$ accepts $w$.
     \item The manner in which we produce $M^{'}$ and $q$,
       we guarantee that $M^{'}$ indeed visits $q$ {\bf iff}
       $M$ accepts $w$.
   \end{compactitem}
   %
    What we ``hit'' in $B$ are only those instances produced 
    by ``massaging'' $M$ in the aforesaid manner. Thus
    we likely have a one-to-one but {\em into} map into $B$.
  \item Now
    if there is a decider for the whole of $B$, there must be
    a decider for $f(A)\subseteq B$ also.
  \item This means: we can decide the whole of $A$ by
    taking a
    $\langle M,w\rangle$ and produce a
    $\langle M,q\rangle$ where $q$ is a new state not in $M$,
    and asking the decider of $B$ whether this 
    $\langle M,q\rangle\in B$.
  \item We know that for 
    $\langle M,w\rangle\notin A$,
    $\langle M,q\rangle\notin B$.
  \item Thus by knowing whether
    $\langle M,q\rangle\in B$ or not, we can tell whether
    $\langle M,w\rangle\in A$ or not, thus deciding $A_{TM}$.
  \end{compactitem}

\noindent{\bf {Mapping Reduction from $A_{TM}$ to $Regular_{TM}$}:\/}
Define $Regular_{TM}$ to be the language of all TM codes such that the  TM
itself has a regular language.
%
Define the following mapping reduction from  $A_{TM}$ to $Regular_{TM}$:
\begin{footnotesize}
\begin{verbatim}
  M'(x) {
   if x is of the form 0^n 1^n then goto acceptM'; // 0 power n 1 power n
   Run M on w; // This may LOOP!!
   if M accepts w, then goto acceptM';
   if M rejects w, then goto rejectM';
  }
\end{verbatim}
\end{footnotesize}
%
Now the language of {\tt M'} is regular (actually $\Sigma^*$)
 iff $M$ accepts $w$.
%
Thus by testing for regularity we can solve $A_{TM}$.

\noindent{\bf {Rice's Theorem}:\/}
Every non-trivial partitioning of TM codes based on the language of the
TMs is undecidable. We saw two non-trivial partitionings above: (i)~based
on state visitation, (ii)~based on the language of the TM.
%
{\sl Colloquially, we are in the land of
``equal oppportunity TMs.'' That is,
``TMs'' can't be discriminated based on Race, Color, or Origin.  }

\noindent{\bf {Chapter 17, Time Complexity  and the class NP}:\/}
The same mapping reduction idea works for time complexity also.
%
In this case, we are working on looping-free TMs (deciders).
%
For TMs that may loop, their time complexity is infinite!
%
The time complexity of TMs is given by the number of steps they take
before they halt.


\noindent{\bf Class NP:\/} The
 class NP is those problems for which there are non-deterministic
algorithms that ``perform'' in polynomial time.
%
That is, there is an NDTM that, while taking those ``magical guesses''
is able to halt in a polynomial number  of steps.
%
Alternately, if a solution is given as a certificate, the solution
can be checked in polynomial time.
%
Examples of ND languages:
\begin{compactitem}
\item \( SAT = \{ \Gamma \;\mid\; \Gamma\; is\; a\; Boolean\; formula\;
  that\; is\; satisfiable\}\)
\item \( 3SAT= \{ \Gamma \;\mid\; \Gamma\; is\; a\; 3CNF \; Boolean\; formula\;
  that\; is\; satisfiable\}\)
\item \( Clique= \{ G \;\mid\; G\; is\; a\; graph\; with\; a\; clique\}\)
\end{compactitem}

\noindent{\bf {Chapter 19, NP-Completeness}:\/}
We don't know whether all ND languages have deterministic polynomial
time algorithms. That is whether the language family NP and P are
the same.
%
To attack this annoying ``gap'' between P and NP,
scientists have come up with the {\em hardest} members of NP
called NP-complete.

A language $L$ is NP-complete if
\begin{compactitem}
  \item (In NP) $L$ is in NP
  \item (NP-hard) 
    Every other language in NP can be poly-time mapping reduced to $L$
\end{compactitem}

Note that
there are undecidable NP-hard languages (e.g. Diophantines language!).
%
Thus we must show the ``In NP'' part for any meaningful dialog in this space!!

The first problem shown to be NP-complete is 3SAT.
%
This is done by showing that the ``work of any NDTM can be
represented as Boolean formula satisfaction.''

Now for any other language (e.g. Clique), we show it NP-complete by
\begin{compactitem}
  \item Showing that Clique is in NP
  \item Showing that there is a mapping reduction from 3SAT to Clique
\end{compactitem}


\end{document}

%--
