next up previous contents
Next: 4.3 An NP-Complete Problem: Up: 4 Nondeterminism; Inverting Functions; Previous: 4.1 Example of a

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

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 to iff , for all x. is NP-complete if 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 the next section for factoring. Now we proceed with an example of NP-completeness.



next up previous contents
Next: 4.3 An NP-Complete Problem: Up: 4 Nondeterminism; Inverting Functions; Previous: 4.1 Example of a



Leonid Levin
Wed Aug 21 20:35:42 EDT 1996