We determined that inversion, search, and NP types of problems are
equivalent. Nobody knows whether *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:

- Linear Programming: Given integer
**n**by**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

*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]. - Primality test: Determine whether a given integer
**p**has a factor?Solution: A bad (exponential time) way is to try all possible integer factors of

**p**. More sophisticated algorithms, however, run fast (see section 5.1). - Graph Isomorphism:
Problem: Given two graphs
and , is isomorphic to ? i.e. Can the vertices of be re-numbered so that it becomes equal ?
Solution: Checking all enumerations of vertices is not practical (for

**n = 100**, this exceeds the number of particles in the known Universe). [Luks 1980] found an steps algorithm where**d**is the degree. This is a P-time for . - 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.

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:

- Linear Programming: All
known solutions produce rational
**x**. No reasonable algorithm is known to find integer**x**. - Factoring: Given an integer, find a factor. Can be done in about exponential time . Seems very hard: Centuries of quest for fast algorithm were unsuccessful.
- 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.
- Independent Nodes: Find a given number of independent (i.e., not sharing edges) nodes in a given graph. No P-time solution is known.

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?

Wed Aug 21 20:35:42 EDT 1996