David S. Johnson
Skip Abstract Section
Abstract
This is the 24th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman & Co., New York, 1979, hereinafter referred to as “[G&J].”” Previous columns, the first 23 of which appeared in J. Algorithms, will be referred to by a combination of their sequence number and year of appearance, e.g. “[Col 1, 1981].” This edition of the column describes the history and purpose of the column and the status of the open problems from [G&J] and previous columns.
- Aaronson, S. 2003. The prime facts: From Euclid to AKS. Manuscript available from http://www. scottaaronson.com/writings/prime.pdf.Google Scholar
- Adleman, L. M., and Huang, M.-D. 1992. Primality testing and Abelian varieties over finite fields. Lecture Notes in Mathematics, vol. 1512. Springer-Verlag, New York.Google Scholar
- Adleman, L. M., Pomerance, C., and Rumely, R. S. 1983. On distinguishing prime numbers from composite numbers. Ann. Math. 117, 173--206.Google ScholarCross Ref
- Agrawal, M., Kayal, N., and Saxena, N. 2002. PRIMES is in P. Manuscript available from http:// www.cse.iitk.ac.in/primality.pdf.Google Scholar
- Agrawal, M., Kayal, N., and Saxena, N. 2004. PRIMES is in P. Ann. Math. 160, 781--793.Google ScholarCross Ref
- Aharonov, D., and Regev, O. 2004. Lattice problems in NP ∩ coNP. In Proceedings of the 45th IEEE Symposium on Foundations of Computing. IEEE Computer Society, Los Alamitos, Calif., 362--371. Google ScholarDigital Library
- Ajtai, M. 1996. Generating hard instances of lattice problems. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, New York, 99--108. (Full version available from http://eccc.uni-trier.de/eccc as ECCC technical report TR96-007.) Google ScholarDigital Library
- Ajtai, M. 1998. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, New York, 10--19. Google ScholarDigital Library
- Ajtai, M. 2003. The worst-case behavior of Schnorr's algorithm approximating the shortest nonzero vector in a lattice. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. ACM, New York, 396--406. Google ScholarDigital Library
- Ajtai, M., and Dwork, C. 1997. A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM, New York, 284--293. (Full version available from http://eccc.uni-trier.de/eccc as ECCC technical report TR96-065.) Google ScholarDigital Library
- Ajtai, M., Kumar, R., and Sivakumar, D. 2001. A seive algorithm for the shortest lattice vector problem. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, New York, 601--610. Google ScholarDigital Library
- Arora, S., Babai, L., Stern, J., and Sweedyk, E. Z. 1997. The hardness of approximating optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54, 317--331. (Preliminary version in Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (1993), 724-- 733.) Google ScholarDigital Library
- Babai, L. 1986. On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica 6, 1--13. Google ScholarDigital Library
- Babai, L., and Luks, E. 1983. Canonical labelling of graphs. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing. ACM, New York, 171--183. Google ScholarDigital Library
- Banaszczyk, W. 1993. New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296, 625--635.Google ScholarCross Ref
- Berlekamp, E. R., McEliece, R. J., and van Tilborg, H. C. A. 1978. On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory IT-24, 384--386.Google ScholarCross Ref
- Berman, P., and Karpinski, M. 2002. Approximating minimum satisfiability of linear equations. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA., 74--83. Google ScholarDigital Library
- Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., and Tan, T. S. 1993. Edge insertion for optimal triangulations. Disc. Comput. Geom. 10, 47--65.Google ScholarDigital Library
- Bern, M., and Eppstein, D. 1997. Approximation algorithms for geometric problems. In Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum, Ed. PWS Publishing Company, Boston, Mass., 296--345. Google ScholarDigital Library
- Bernstein, D. J. 2004. Proving primality in essentially quartic random time. (Manuscript, available from http://cr.yp.to/primetests/quartic-20041203.pdf.)Google Scholar
- Berrizbeitia, P. 2002. Sharpening PRIMES is in P for a large family of numbers. (Manuscript, available from arxiv.org/abs/math.NT/0211334.)Google Scholar
- Bienstock, D. 1991. On the complexity of testing for odd holes and induced odd paths. Disc. Math. 90, 85--92. (Corrigendum in Disc. Math. 102 (1992), 109.) Google ScholarDigital Library
- Boppana, R., Hastad, J., and Zachos, S. 1987. Does co-NP have short interactive proofs? Inf. Process. Lett. 25, 27--32. Google ScholarDigital Library
- Brickell, E. F. 1985. Breaking iterated knapsacks. In Advances in Cryptology: Proceedings of CRYPTO 84. Lecture Notes in Computer Science, vol. 196. Springer-Verlag, Berlin, Germany, 342--358. Google ScholarDigital Library
- Bruck, J., and Naor, M. 1990. The hardness of decoding linear codes with preprocessing. IEEE Trans. Inf. Theory 36, 381--385.Google ScholarDigital Library
- Cai, J.-Y. 1998. A relation of primal-dual lattices and the complexity of shortest lattice vector problem. Theor. Comput. Sci. 207, 105--116. Google ScholarDigital Library
- Cai, J.-Y. 1999. Some recent progress on the complexity of lattice problems. In Proceedings of the 14th IEEE Conference on Computational Complexity. IEEE Computer Society, Los Alamitos, Calif., 158--179. Google ScholarDigital Library
- Cai, J.-Y., and Nerurkar, A. 1997. An improved worst-case to average-case connection for lattice problems. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computing. IEEE Computer Society, Los Alamitos, Calif., 468--477. Google ScholarDigital Library
- Cai, J.-Y., and Nerurkar, A. 2000. A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. Inf. Process. Lett. 76, 61--66. Google ScholarDigital Library
- Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., and Vušković, K. 2005a. Recognizing Berge graphs. Combinatorica 25, 143--186. Google ScholarDigital Library
- Chudnovsky, M., Kawarabayashi, K., and Seymour, P. 2005b. Detecting even holes. J. Graph Theory 48, 85--111. Google ScholarDigital Library
- Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. 2005c. The strong perfect graph theorem. Annual of Math., to appear.Google Scholar
- Conforti, M., Cornuéjols, G., Kapoor, A., and Vušković, K. 2002. Even hole-free graphs, Part II: Recognition algorithm. J. Graph Theory 40, 238--266. Google ScholarDigital Library
- Coppersmith, D. 1993. Modifications to the number field sieve. J. Graph Theory 6, 169--180.Google Scholar
- Crandall, R., and Pomerance, C. B. 2001. Prime Numbers: A Computational Perspective. Springer, New York.Google ScholarCross Ref
- D'Azevedo, E. F., and Simpson, R. B. 1989. On optimal interpolation triangle incidences. SIAM J. Sci. Statist. Comput. 10, 1063--1075. Google ScholarDigital Library
- Dinur, I., Kindler, G., Raz, R., and Safra, S. 2003. Approximating CVP to within almost polynomial factors is NP-hard. Combinatorica 23, 205--243. (Preliminary version in Proceedings of the 39th IEEE Symposium on Foundations of Computing (1998), 475--484.) Google ScholarDigital Library
- Downey, R. G., and Fellows, M. R. 1999. Parameterized Complexity. Springer-Verlag, Heidelberg, Germany. Google ScholarDigital Library
- Dumer, I., Micciancio, D., and Sudan, M. 2003. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory 49, 22--37. (Preliminary version in Proceedings of the 40th IEEE Symposium on Foundations of Computing (1999), 475--484.) Google ScholarDigital Library
- Edelsbrunner, H., and Tan, T. S. 1993. A quadratic time algorithm for the minmax length triangulation. SIAM J. Comput. 22, 527--551. Google ScholarDigital Library
- Edelsbrunner, H., Tan, T. S., and Waupotitsch, R. 1992. An o(n2log n) time algorithm for the minmax angle triangulation. SIAM J. Sci. Statist. Comput. 13, 994--1008. (Preliminary version in Proceedings of the 6th ACM Symposium on Computational Geometry. ACM, New York, 1990, 44--52.) Google ScholarDigital Library
- Eppstein, D. 1994. Approximating the minimum weight Steiner triangulation. Disc & Comp. Geom. 11, 163--191. (Preliminary version in Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA., 1992, 48--57.) Google ScholarDigital Library
- Feige, U., and Micciancio, D. 2004. The inapproximability of lattice and coding problems with preprocessing. J. Comput. Syst. Sci. 69, 1, 45--67. (Preliminary version in Proceedings of the 2002 IEEE Computational Complexity Conference. IEEE Computer Society Press, Los Alamitos, Calif., 44--52.) Google ScholarDigital Library
- Fouvry, E. 1980. Théorème de Brun-Titchmarsh; application au théorème de Fermat. J. Numb. Theory 12, 128--138.Google Scholar
- Goldreich, O., and Goldwasser, S. 2000. On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. 60, 540--563. (Preliminary version in Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, New York, 1998, 1--9.) Google ScholarDigital Library
- Goldreich, O., Micali, S., and Widgerson, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 691--729. (Preliminary version in Proceedings of the 27th Annual IEEE Symposium on Foundations of Computing. IEEE Computer Society Press, Los Alamitos, Calif., 1986, 174--187.) Google ScholarDigital Library
- Goldreich, O., Micciancio, D., Safra, S., and Seifert, J. P. 1999. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inf. Process. Lett. 71, 55--61. Google ScholarDigital Library
- Goldwasser, S., and Kilian, J. 1986. Almost all primes can be quickly certified. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing. ACM, New York, 316--329. (Journal version is Goldwasser and Kilian {1991}.) Google ScholarDigital Library
- Goldwasser, S., and Kilian, J. 1999. Primality testing using elliptic curves. J. ACM 46, 4, 450--472. Google ScholarDigital Library
- Golumbic, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York. Google ScholarDigital Library
- Granville, A. 2004. It is easy to determine whether a given integer is prime. Bull. AMS 42, 3--38.Google ScholarCross Ref
- Grötschel, M., Lovász, L., and Schrijver, A. 1981a. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169--197.Google ScholarCross Ref
- Grötschel, M., Lovász, L., and Schrijver, A. 1981b. Polynomial algorithms for perfect graphs. Ann. Disc. Math. 21, 322--356.Google Scholar
- Guruswami, V., Micciancio, D., and Regev, O. 2005. The complexity of the covering radius problem. Comput. Complex. 14, 90--120. (Preliminary version in Proceedings of the 19th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., 2004, 161--173. Google ScholarDigital Library
- Guruswami, V., and Vardy, A. 2005. Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. IEEE Trans. Inf. Theory 51, to appear. Google ScholarDigital Library
- Hsu, W.-L. 1987. Recognizing planar perfect graphs. J. ACM 34, 255--288. Google ScholarDigital Library
- JáJá, J., and Venkatesan, S. 1981. On the complexity of a parity problem related to coding theory. Report CS-81-5, Department of Computer Science, Pennsylvania State University.Google Scholar
- Kaibel, V., and Schwartz, A. 2003. On the complexity of polytope isomorphism problems. Graphs Combin. 19, 215--230.Google Scholar
- Kannan, R., Lenstra, A. K., and Lovász, L. 1988. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Math. Comput. 50, 235--250.Google ScholarCross Ref
- Khot, S. 2004. Hardness of approximating the shortest vector problem in lattices. In Proceedings of the 45th IEEE Symposium on Foundations of Computing. IEEE Computer Society, Los Alamitos, Calif., 126--135. Google ScholarDigital Library
- Kumar, R., and Sivakumar, D. 2001. Complexity theory column 33 (Guest Column): Complexity of SVP---A reader's digest. SIGACT News 32, 3, 40--52.Google Scholar
- Lagarias, J. C. 1985. The computational complexity of simultaneous Diophantine approximation problems. SIAM J. Comput. 14, 196--209. Google ScholarDigital Library
- Lagarias, J. C., Lenstra, Jr., H. W., and Schnorr, C.-P. 1990. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10, 333--348.Google Scholar
- Lenstra, A. K., Lenstra, H. W., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 515--534.Google ScholarCross Ref
- Lenstra, H. W., and Pomerance, C. 2005. Primality testing with Gaussian periods. To appear.Google Scholar
- Lenstra, Jr., H. W. 1983. Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538--548.Google ScholarDigital Library
- Levcopoulos, C., and Krznaric, D. 1998. Quasi-greedy triangulations approximating the minimum weight triangulation. J. Algorithms 27, 303--338. (Preliminary version in Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA., 1996, 392--401.) Google ScholarDigital Library
- Mathon, R. 1979. A note on the graph isomorphism counting problem. Inf. Process. Lett. 8, 131--132.Google ScholarCross Ref
- Micciancio, D. 2001. The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput. 30, 2008--2035. Google ScholarDigital Library
- Micciancio, D. 2004. Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor. SIAM J. Comput. 34, 118--169. (Preliminary version in Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, New York, 2002, 609--618.) Google ScholarDigital Library
- Micciancio, D., and Regev, O. 2004. Worst-case to average-case reductions based on Gaussian measures. In Proceedings of the 45th IEEE Symposium on Foundations of Computing. IEEE Computer Society Press, Los Alamitos, Calif., 372--381. Google ScholarDigital Library
- Micciancio, D., and Vadhan, S. 2003. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In Advances in Cryptology---CRYPTO 2003, Proceedings of the 23rd Annual International Cryptology Conference. Lecture Notes in Computer Science, vol. 2729. Springer-Verlag, Berlin, Germany, 282--298.Google Scholar
- Mihailescu, P., and Avanzi, R. M. 2003. Efficient “quasi”-deterministic primality test improving AKS draft. Manuscript, available from the first author at [email protected].Google Scholar
- Miller, G. L. 1976. Riemann's hypothesis and test for primality. J. Comput. Syst. Sci. 13, 300--317.Google ScholarDigital Library
- Pomerance, C. 1996. A tale of two sieves. AMS Notices 43, 1473--1485.Google Scholar
- Pratt, V. 1975. Every prime has a succinct certificate. SIAM J. Comput. 4, 214--220.Google ScholarDigital Library
- Rabin, M. 1976. Probabilistic algorithms. In Algorithms and Complexity: New Directions and Recent Results, J. F. Traub, Ed. Academic Press, New York, 21--39.Google Scholar
- Rabin, M. 1980. Probabilistic algorithm for testing primality. J. Number Theory 12, 128--138.Google ScholarCross Ref
- Regev, O. 2004a. Improved inappoximability of lattice and coding problems with preprocessing. IEEE Trans. Inf. Theory 50, 2031--2037. (Preliminary version in Proceedings of the 18th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., 2002, 315--322.) Google ScholarDigital Library
- Regev, O. 2004b. New lattice-based cryptographic constructions. J. ACM 51, 899--942. (Preliminary version in Proceedings of the 35th Annual ACM Symposium on Theory of Computing. ACM, New York, 2003, 407--416.) Google ScholarDigital Library
- Rivest, R., Shamir, A., and Adleman, L. 1978. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120--126. Google ScholarDigital Library
- Schnorr, C.-P. 1987. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201--224. Google ScholarDigital Library
- Schönhage, A. 1984. Factorization of univariate integer polynomials by Diophantine approximation and an improved basis reduction algorithm. In Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 172. Springer-Verlag, Berlin, Germany, 436--447. Google ScholarDigital Library
- Shawe-Taylor, J., and Pisanski, T. 1994. Homeomorphism of 2-complexes is graph isomorphism complete. SIAM J. Comput. 23, 120--132. Google ScholarDigital Library
- Shor, P. W. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484--1509. Google ScholarDigital Library
- Sibson, R. 1978. Locally equiangular triangulations. Comput. J. 21, 243--245.Google Scholar
- Solovay, R. M., and Strassen, V. 1978. A fast Monte-Carlo test for primality. SIAM J. Comput. 6, 84--85.Google ScholarCross Ref
- Toran, J. 2004. On the hardness of graph isomorphism. SIAM J. Comput. 33, 1093--1108. Google ScholarDigital Library
- van Emde Boas, P. 1981. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Report 81-04, Department of Mathematics, Univ. Amsterdam, Amsterdam, The Netherlands.Google Scholar
- Vardy, A. 1997. The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43, 1757--1766. Google ScholarDigital Library
Index Terms
- The NP-completeness column
Recommendations
The NP-completeness column: Finding needles in haystacks
This is the 26th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. ...
The NP-completeness column: The many limits on approximation
This is the 25th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book Computers and Intractability: A Guide to the Theory of NP-Completeness, W. ...
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational ComplexityThe Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...
Reviews
Lane A. Hemaspaandra
It has been quite a wait between this last (24th) installment of David Johnson's NP-completeness column and the 23rd [1], which came out in 1992. This one is the first to appear in the new journal ACM Transactions on Algorithms . Fortunately, the clarity, command, informativeness, and sense of excitement in Johnson's writing remains truly superb, a model for anyone wishing to write about progress in theoretical computer science. This particular column covers what progress has been made on the open problems from the famous book by Garey and Johnson [2], and from the first 23 columns. The bulk of the column focuses on the four problems that have been resolved, but whose resolutions were not already covered in the first 23 columns: composite number, even cover/minimum weight codeword, imperfect graph, and shortest vector in a lattice. The discussions are a joy to read. The column concludes with a brief discussion of "still open after all these years" problems. The roughly 90 citations give readers a rich set of resources to further explore the literature related to progress on the covered problems. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments