\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