Consider a P-time function F. For convenience, assume 
,
(often it is enough if |x| and 
are bounded by polynomials of each
other). Inverting F means given y, find 
, i.e. such that
. 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 
. Assume F runs in linear time on a
Pointer Machine. What is the cost of inverting F? The space used is
|x|+|y|+ space
. But time is 
: absolutely
infeasible. No method is currently proven much better in the worst case. And
neither can we prove some inverting problems to require super-linear
time. This is the sad present state of Computer Science!
An Example: Factoring. Let 
be the the product
of integers 
. 
is almost |x|. For simplicity,
assume 
are primes. A fast algorithm in sec. 5.1 determines
if an integer is prime. If not, no factor is given, only its existence.
To invert F means to factor 
. How many primes we might have to check?
The density of prime numbers of length n is approximately 
.
So, factoring by exhaustive search takes exponential time!
In fact, even the best known algorithms for this ancient problem run in time
about 
, 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 unproven faith.
One-Way Functions: 
are those easy
to compute 
and hard to invert 
for most x.
Even their existence is sort of a religious belief in Computer Theory.
It is unproven, though many functions 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.
Let us compare the inverting problems with another type: the search problems.
They are, given x, to find w satisfying a given predicate 
computable in time 
. 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 
,
which outputs 
if C is in fact a Hamiltonian cycle of G.
Otherwise, 
. There are two parts to a search problem, (a)
decision problem: does w (called 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 
finds w satisfying 
(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 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. 
holds for some w. An NP language is the set
of all inputs acceptable by a P-time non-deterministic Turing
Machine (sec. 3.4). 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 
. Conversely,
which P corresponds to a non-deterministic TM M? 
just checks if
M accepts x, when the driver chooses the states reflecting the digits of
w.
Interestingly, polynomial 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
, where s is the space bound. Then we need to check 
:
whether the TM can be driven from the configuration x to w in time 
and space s. For this we need for every z, to check 
and
, which takes space 
. So, 
[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.