4.2 Complexity of NP Problems.

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:

1. 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].

2. 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).

3. 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 .

4. 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:

1. Linear Programming: All known solutions produce rational x. No reasonable algorithm is known to find integer x.
2. 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.
3. 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.
4. 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?

NP-Completeness