NP-Completeness by D. S. Johnson

NP-Completeness column started by D. S. Johnson in Journal of Algorithms in 1982 and stopped to exist at 1992 appeared again a semi-annual NP-completeness column in ACM Trans. Algorithms.
The main purpose of the NP-completeness column was to provide updates and addition to the compendium at the end of Garey & Johnson book. Besides a list of solved/appeared problems the column contained materials about new techniques and developments related to the theory of NP-completeness like PCP theorem, ZKP etc.
The first article of the revived columns is devoted to the problems solved in the last 13 years problems.
4 important problems are solved:

• COMPOSITE NUMBER is in PTIME was solved by M. Agrawal, N. Kayal, N. Saxena in 2002,


• IMPERFECT GRAPH is in PTIME If given graph G is not perfect. The problem was solved last year by Chudnovsky, Cornuejols, Liu, Seymour, Vuskovic


• EVEN COVER Given a collection C of subsets of a finite set X and k > 0, if there a nonempty subcollection C' of C of the size < k, such that ech element of X is in an even number of sets of a subcollection C'
The problem was proved to be NP-complete by Alexander Vardy in 1997

• SHORTEST VECTOR IN A LATTICE given a collection of n-vectors v_1, ..., v_n, over rational numbers and integer B > 0, is there a nonzero n-vector a over integers, such that if x = \sum a_i v_i, then the Euclidian distance (x,0) is B or less. The decission version of the problem is known to be NP-complete since 1981 (by van Emde Boas). In this article D. Johnson review approximation algorithms for an optimization version of the SVP. It was known since along time ago that this problem can be approximated in PTIME but with exponential approximation factor (Schnorr 1987). The best approximation factor known now is a constant factor and the SVP can be approximated by constant-factor algorithm if NP \setbseteq RP.

At the end of the article Johnson givew a review of three well-known problems which are still open.