\newpage\subsection{Complexity of NP Problems.\label{compl}}

We determined that inversion, search, and NP types of problems are equivalent.
Nobody knows whether {\em all} such problems are solvable in P-time
(i.e.\ belong to P). This question (called P=?NP) is probably the most famous
one in Theoretical Computer Science.  All such problems are solvable in
exponential time but it is unknown whether any better algorithm generally
exists.  For many problems the task of finding an efficient algorithm may seem
hopeless, while similar or slightly relaxed problems can be solved.  Examples:

\begin{enumerate}
 \item Linear Programming: Given integer $n\times m$ matrix $A$ and
vector $b$, find a rational vector $x$ with $Ax<b$. Note, if
coefficients in $A$ have $k$-bits and $x$ exists then an $x$ with
$O(nk)$ bit numbers exists, too.

Solution: The Dantzig's {\em Simplex} algorithm finds $x$ quickly for most $A$.
Some $A$, however, take exponential time. After long frustrating efforts, a
worst case P-time Ellipsoid Algorithm was finally found in [Yudin Nemirovsky
1976].

\item Primality test: Determine whether a given integer $p$ has a factor?

Solution: A bad (exponential time) way is to try all $2^{|p|}$ possible
integer factors of $p$. More sophisticated algorithms, however, run fast (see
section~\ref{prime}).

\item     Graph Isomorphism:
 Problem: Given two graphs $G_1$ and $G_2$, is $G_1$ isomorphic to $G_2$? i.e.
Can the vertices of $G_1$ be re-numbered so that it becomes equal $G_2$?

Solution: Checking all $n!$ enumerations of vertices is not practical (for $n=
100$, this exceeds the number of particles in the known Universe).
 [Luks 1980] found an $O(n^d)$ steps algorithm where $d$ is the degree.
 This is a P-time for $d = O(1)$.

\item Independent Edges (Matching): Find a given number of independent
(i.e., not sharing nodes) edges in a given graph.

Solution: Max flow algorithm solves a bi-party graph case. The general
case is solved by a sophisticated algorithm by J. Edmonds.

 \end{enumerate}

Many other problems have been battled for decades or centuries and no P-time
solution has been found. Even modifications of the previous three examples
have no known answers:\begin{enumerate}
 \item Linear Programming: All known solutions produce rational $x$. No
reasonable algorithm is known to find integer $x$.
 \item Factoring:
 Given an integer, find a factor. Can be done in about exponential time
$n^{\sqrt{n}}$. Seems very hard: Centuries of quest for fast algorithm were
unsuccessful.
 \item Sub-graph isomorphism: In a more general case where one graph may
be isomorphic to a part of another graph, no P-time solution has been
found.

\item Independent Nodes: Find a given number of independent (i.e., not
sharing edges) nodes in a given graph. No P-time solution is known.

 \end{enumerate}

We learned the proofs that Linear Chess and some other games have exponential
complexity. None of the above or any other search/inversion/NP problem,
however, have been proven to require super-P-time. When, therefore, do we stop
looking for an efficient solution?

 \paragraph{NP-Completeness} theory is an attempt to answer this question. See
results by S.Cook, R.Karp, L.Levin, and others surveyed in [Garey, Johnson]
[Trakhtenbrot]. A P-time function $f$ reduces one NP-predicate $p_1(x)$ to
$p_2(x)$ iff $p_1(x) = p_2(f(x))$, for all $x$. $p_2$ is NP-complete if {\em
all} NP problems can be reduced to it. Thus, each NP-complete problem is as
least as worst case hard as all other NP problems. This may be a good reason to
give up on fast algorithms for it. Any P-time algorithm for one NP-complete
problem would yield one for all other NP (or inversion, or search) problems. No
such solution has been discovered yet and this is left as a homework (10 years
deadline). What do we do when faced with an NP-complete problem? Sometimes one
can restate the problem, find a similar one which is easier but still gives the
information we really want, or allow more powerful means. Both of these we will
do in Sec.~\ref{prime} for factoring. Now we proceed with an example of
NP-completeness.