\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