\newpage \section {Nondeterminism; Inverting Functions; Reductions.\label{np}}
\subsection{Example of a Narrow Computation: Inverting a Function.\label
{invert}}

Consider a P-time function $F$. For convenience, assume $|F(x)|=|x|$,
(often it is enough if $|x|$ and $|F(x)|$ are bounded by polynomials of each
other). Inverting $F$ means given $y$, find $x\in F^{-1}(y)$, i.e.\ such that
$F(x) = y$. There may be multiple solutions if $F$ is many-to-one; we need to
find only one. How?

We may try all possible $x$ for $F(x)=y$. Assume $F$ runs in linear time on a
Pointer Machine. What is the cost of inverting $F$? The {\em space} used is
$|x|+|y|+ $space$_F(x)= O(|x|)$. But time is $O(|x|2^{|x|})$: absolutely
infeasible. No method is currently proven much better in the worst case. And
neither can we prove some inverting problems to require {\em super-linear}
time. This is the sad present state of Computer Science!

{\bf An Example: Factoring.} Let $F(x_1,x_2)=x_1x_2$ be the the product
of integers $x_1,x_2$ $|x_1|=|x_2|$. $|F(x)|$ is almost $|x|$. For simplicity,
assume $x_1,x_2$ are primes. A fast algorithm in sec.~\ref{prime} determines
if an integer is prime. If not, no factor is given, only its existence.
 To invert $F$ means to factor $F(x)$. How many primes we might have to check?
The density of $n$-bit prime numbers is approximately $1/(n\ln2)$.
 So, factoring by exhaustive search takes {\em exponential} time!
 In fact, even the best known algorithms for this ancient problem run in time
about $2^{\sqrt{|y|}}$, despite centuries of efforts by most brilliant people.
The task is now commonly believed infeasible and the security of many famous
cryptographic schemes depends on this {\em unproven} faith.

{\bf One-Way Functions:} \(x\,{\stackrel F\longrightarrow}\, y\) are those easy
to compute $(x\mapsto y)$ and hard to invert $(y\mapsto x)$ for most $x$.
 Even their existence is sort of a religious belief in Computer Theory.
It is unproven, though many functions {\em seem} to be one-way.
 Some functions, however, are proven to be one-way, IFF one-way functions
EXIST. Many theories and applications are based on this hypothetical existence.

\subsubsection*{Search and NP Problems.\label{search}}

Let us compare the inverting problems with another type: the search problems.
They are, given $x$, to find $w$ satisfying a given predicate $P(x,w)$
computable in time $|x|^{O(1)}$. Any inverting problem is a search problem and
any search problem can be restated as an inverting problem. E.g., finding a
Hamiltonian cycle $C$ in a graph $G$, can be stated as inverting a $f(G,C)$,
which outputs $G,0\ldots 0$ if $C$ is in fact a Hamiltonian cycle of $G$.
Otherwise, $f(G,C) = 0\ldots 0$. There are two parts to a search problem, (a)
decision problem: does $w$ (called {\em witness}) exists, and (b) a
constructive problem: actually find $w$.

A time bound for solving one of these types of problems gives a similar bound
for the other.

Suppose a P-time $A(x)$ finds $w$ satisfying $P(x,w)$ (if $w$ exists).
If $A$ does not produce $w$ within the time limit then it does not exist. So we
can use the ``witness'' algorithm to solve the decision problem.

On the other hand, each predicate $P$ can be extended to $P'((x,y),w)=
P(x,w)\&w<y$ for which any algorithm deciding if witnesses exist can be
used to find them (by binary search, in $|w|$ iterations).
Unfortunately, for many problems such algorithm is not known to exist.

The {\em language} of a problem is the set of all acceptable inputs. For the
inverting problem it is the range of $f$. For the search problem it is the set
of all $x$ s.t.\ $P(x,w)$ holds for some $w$. An {\em NP language} is the set
of all inputs acceptable by a P-time {\em non-deterministic} Turing
Machine (sec.~\ref{paral}). All three classes of languages -- search,
inverse and NP -- coincide. What NP machine accepts $x$ if the search
problem with input $x$ and predicate $P$ is solvable? This is just the machine
which prompts the driver for digits of $w$ and checks $P(x,w)$. Conversely,
which $P$ corresponds to a non-deterministic TM $M$? $P(x,w)$ just checks if
$M$ accepts $x$, when the driver chooses the states reflecting the digits of
$w$.

Interestingly, polynomial {\em space} bounded deterministic and
non-deterministic TMs have equivalent power. It is easy to modify TM to have a
unique accepting configuration. Any acceptable string will be accepted in time
$s2^s$, where $s$ is the space bound. Then we need to check $A(x,w,s,k)$:
whether the TM can be driven from the configuration $x$ to $w$ in time $<2^k$
and space $s$. For this we need for every $z$, to check $A(x,z,s,k\!-\!1)$ and
$A(z,w,s,k\!-\!1)$, which takes space $t_k\le t_{k\!-\!1} + |z|$. So, $t_k=
O(sk)= O(s^2)$ [Savitch 1970].

Search problems are games with P-time transition rules and one move
duration. A great hierarchy of problems results from allowing more moves and/or
other complexity bounds for transition rules.