\font\largerbold = cmbx10 scaled \magstep1
\font\largerrm =cmr10 scaled \magstep1
\font\largestrm =cmr10 scaled \magstep2
\nopagenumbers
\def\H{\char `\^}
\def\map{{\tt Maple}}
\font\sc=cmcsc10.tfm
\font\show = cmdunh10.tfm
%\magnification=\magstep1
\def\tiny{\vskip .036in}

\centerline{\largerbold Algorithms \raise .05em \hbox{\bf (fast and
slow)} and Oracles: a famous problem} 

\medskip\tiny

\def\e{$\ldots$\ }

%Here is a written version, slightly expanded, of what I said too
%rapidly in class. What's below describes the beginning of complexity
%theory, which to me has always seemed like philosophy mixed up with
%algebra.

\medskip\tiny

{\noindent \bf Algorithms} \tiny Algorithms could deal with almost
anything. As Knuth remarks, cookbook recipes are examples of
algorithms. I'll discuss math algorithms.  Math algorithms could deal
with geometry and many other topics but here algorithms will be
simple: their inputs will be positive integers and their outputs will
be other positive integers. Each number has a size. The size of
{\sc 345,772} is {\sc 6}. The size tells how many decimal digits are
used in the standard written description of the number. {\sc 845} and
{\sc 120} have the same size, 3.

\medskip\tiny

{\noindent \bf Work} \tiny Our algorithms will involve the usual
operations of arithmetic such as addition and multiplication. We'll
measure an algorithm's work by estimating the total number of single
digit arithmetic operations the algorithm must do. For example, we've
seen that {\sc Squaring} whose input is a number $X$ with size $m$
can be done by an algorithm taking at most $5m^2$ operations to
compute $X^2$: that's at most $m^2$ single digit multiplies and at
most $4m^2$ single digit adds. Our simple algorithm for the problem
{\sc Square Inquiry}, which answers ``Yes'' if the input, $X$ is a
square, needs at most $5m^2 X$ operations: square all integers from 1
to $X$ (there are $X$ integers, each up to $m$ digits long) and
compare the result to $X$.

\medskip\tiny

{\noindent \bf Easy and hard} \tiny The work done by an algorithm may
depend on its input. An algorithm is called {\sc polynomial time} if
the work is at most a multiple of some power of the input's
\underbar{size}. So {\sc Squaring} is polynomial time, but {\sc Square
Inquiry} as described above is not. A now-classical source ({\sl The
Design and Analysis of Computer Algorithms} by Aho, Hopcroft, and
Uhlman, Addison Wesley, 1974) declares (p.~364):

%\tiny
\tiny
{\narrower \noindent How much computation should a problem require
before we rate the problem as being truly difficult? There is general
agreement that if a problem cannot be solved in less than exponential
time, then the problem should be considered completely
intractable. The implication of this ``rating scheme'' is that problems
having polynomial-time-bounded algorithms are tractable. \e we say that
a problem is {\it intractable} if all algorithms to solve that problem
are of at least exponential time complexity.

}
\tiny
%\tiny

\noindent The algorithm for {\sc Square Inquiry} described above is
exponential because if $X$ has $m$ digits, then $X$ is about $10^m$ in
size (that's what it means to have $m$ digits) so that $5m^2 X$ is
$5m^2 10^m$, and this really will grow very
\raise-.04em\hbox{\largerrm very} 
\raise-.06em\hbox{\largestrm very} rapidly, faster
than any polynomial, as $m$ gets large.

\medskip\tiny

{\noindent \bf Oracles} 
\tiny
One dictionary entry for oracle is ``a person or thing regarded as an
infallible guide to future action'' and here I'll try to explain how
an oracle could help with an algorithm. Imagine that a very wise
and trustworthy being always knows the right answer to any question an
algorithm proposes to compute. For example, our oracle for {\sc
Squaring} responds instantaneously with 1600 when told 40, and our
oracle for {\sc Square Inquiry} responds immediately ``Yes'' when
asked ``Is 801025 a square?''

We could wonder how these oracles work, but we assume they are always
correct and always truthful. Someone who is not a true believer,
however, might want {\it evidence}\/ that the oracle's answer is
correct. The evidence the {\sc Square Oracle} could present is just
the multiplication of 40 by itself, a rather limited computation. The
{\sc Square Inquiry Oracle} could give very convincing evidence by
actually supplying a number, 895\footnote*{Calculator help was
accepted here!}, which we could then use to verify that 801025 is a
square.

In both cases the oracle could supply enough evidence so that mere
mortals can verify the oracle's correctness with a polynomial amount
of computation. Such oracles can be checked in polynomial time.

\medskip\tiny

{\noindent \bf The question}

\tiny
Suppose that a problem has answers which can always be checked in
polynomial time. More poetically, suppose there's an oracle for a
problem which can always supply evidence supporting its assertion
which can be verified in polynomial time. The central question of
complexity theory is:

\tiny

{\parindent=1.3\parindent \narrower \narrower \noindent\sc If an
oracle can be checked in polynomial time, must there always be some
algorithm which solves the problem directly in polynomial time?\par}

%{\narrower \narrower \narrower \noindent\sc If a problem has a
%polynomial time oracle, must there always be \underbar{some} algorithm
%which solves the problem itself in polynomial time?\par}

\tiny

\noindent That is, do we need an oracle's help?
This statement is a major part of what is called the {\sc
P=NP problem}. Many people have worked on this problem over the
last 10 or 15 years. They haven't solved it.

\medskip\tiny

{\noindent \bf Relevance to cryptography} \tiny Encrypting and
decrypting should not be too difficult, otherwise people won't use our
methods. So at worst, the descriptions of these processes should be
polynomial. Giving the recipient of a message the key for the
decryption process is logically the same as an oracle telling us a
solution to an inquiry, and decryption can be viewed as our polynomial
time verification of the oracle's response. The assertion that there
is \underbar{no} polynomial time method of ``breaking'' our encryption
scheme means that for all practical purposes communication is
secure\footnote{**}{Yes, everyone can get lucky, but luck isn't really
too reliable if the chance of being lucky is rather small. Such luck
is a much less likely way of getting the message than simply bribing
the message creator!}. We actually hope that the cryptosystem can only
be ``solved'' by an exponential time algorithm.

One famous {\sc NP} problem which has polynomial time oracles is
factoring integers -- that is, writing a given integer as a product of
two or more other integers greater than 1. Here's a version of the
factoring problem which we'll see lies at the foundation of the
security of many current cryptosystems:

\tiny

\indent \indent \indent {\sc Input} A number which is known to be the
product of two primes.

\indent \indent \indent {\sc Output} The two primes.

\tiny

So one input could be ``15'', and the corresponding output would be
``3 and 5''. On the other hand, if the input were a rather large (300
digit?)  product of two primes, then finding the factors might be
difficult, even with lots and lots of cleverly used computer
resources. Yet if the two primes are given, checking that their
product is what's specified is not very hard because multiplication
can be done in polynomial time.

\medskip\tiny

{\noindent \bf Appendix {\sc Square Inquiry} done in polynomial time}
\tiny

I'll describe another way to do {\sc Square Inquiry} so you won't
think I've solved a famous problem by displaying a question which is
{\sc NP} but not {\sc P}\footnote{***}{I wish that I knew one!}. That
is, I've shown you that {\sc Square Inquiry} has an oracle whose
answers can be supported by evidence in polynomial time. Now I'll show
you an ugly but polynomial way to do square inquiry. Please note that
I used a calculator here, also. I'll describe the process first with
an example: is the number 8765432 (a number of size 7) the square of
another number?

\tiny

\noindent{\bf Step 1} Square these numbers: {\bf 0}999999, {\bf
1}999999, \e, {\bf 8}999999, {\bf 9}999999. These are
each 7 digit numbers so their squaring takes at most $5\cdot 7^2$
operations, and there are 10 of them, so I've done $10\cdot 5\cdot
7^2$ operations. I compare the results to my original number, and
deduce that 8765432 is less than the square of {\bf 0}999999.

\tiny

\noindent {\bf Step 2} Square these numbers: 0{\bf 0}99999, 0{\bf
1}99999, 0{\bf 2}99999, \e, 0{\bf 9}99999. These are each 7 digit
numbers so their squaring takes at most $5\cdot 7^2$ operations, and
there are 10 of them, so I've done $10\cdot 5\cdot 7^2$ operations. I
compare the results to my original number, and deduce that 8765432 is
less than the square of 0{\bf 0}99999.

\tiny

\noindent {\bf Step 3} does the same, concentrating at the third
digit, reading from the right. It uses again at most $10\cdot 5\cdot
7^2$ operations.  We learn that the square of 00{\bf 0}9999 is also
larger than 8765432.

\tiny

\noindent {\bf Step 4} uses the same amount of work, but the
outcome is quite different: we learn that 8765432 must lie between the
squares of 000{\bf 1}999 and 000{\bf 2}999 (wow!).

\tiny

\noindent {\bf Step 5} considers the numbers 0002{\bf 0}99,
0002{\bf 1}99, \e 0002{\bf 9}99, and with the same amount of work
tells us that 8765432 must lie between the squares of 0002{\bf 8}99
and 0002{\bf 9}99.

\tiny

We do two more {\bf Steps} (each with the same amount of work), and
learn that 8765432 is between the square of 2960 and 2961, but is
equal to neither one of them. So the answer to {\sc Square Inquiry} is
``No''.

\tiny

This procedure answers {\sc Square Inquiry}. It uses the squares of 10
numbers for each decimal place in the original number. So we compute
10 squares with work $5m^2$ for every digit of a number whose size is
$m$. The total work is the product of these three terms, which is $40
m^3$, certainly a polynomial.  The implementation is certainly
unappealing, but our work estimate is valid. Therefore {\sc Square
Inquiry} has a polynomial time algorithm.

\vfil\eject\end
