L. G. Valiant
ABSTRACT
In the theory of recursive functions and computational complexity it has been demonstrated repeatedly that the natural problems tend to cluster together in “completeness classes”. These are families of problems that (A) are computationally interreducible and (B) are the hardest members of some computationally defined class. The aim of this paper is to demonstrate that for both algebraic and combinatorial problems this phenomenon exists in a form that is purely algebraic in both of the respects (A) and (B). Such computational consequences as NP-completeness are particular manifestations of something more fundamental.
The core of the paper is self-contained, consisting as it does essentially of the two notions of “p-definability” and the five algebraic relations that are proved as theorems. In the remainder our aim is to elucidate the computational consequences of these basic results. Hence in the auxiliary propositions and discussion for convenience we do assume familiarity with algebraic and Boolean complexity theory.
- 1.A.V.Aho, J.E. Hopcroft and J.D. Ullman. The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass. (1974). Google Scholar
Digital Library
- 2.M.N. Barber and B.W. Ninham. Random and Restricted Walks. Gordon and Breach, New York (1970).Google Scholar
- 3.A. Borodin and I. Munro. The Computational Complexity of Algebraic and Numeric Problems. American Elsevier, New York (1975).Google Scholar
- 4.S. Chaiken and D.J. Kleitman. Matrix tree theorems. J. Combinatorial Theory, Series A 24 (1978) 377-381.Google ScholarCross Ref
- 5.S.A. Cook. The complexity of theorem proving procedures. Proc. 3rd ACM Symp. on Theory of Computing (1971) 151-158. Google ScholarDigital Library
- 6.L. Csanky. Fast parallel inversion algorithms. SIAM J. on Computing, 5:4 (1976) 618-623.Google ScholarDigital Library
- 7.M.E. Fisher. Statistical mechanics of dimers on a plane lattice. Phys. Rev. 124 (1961) 1664-1672.Google ScholarCross Ref
- 8.H. Frank and I.T. Frisch. Communication, Transmission and Transportation Networks. Addison-Wesley (1971).Google Scholar
- 9.H.N. Frisch and J.M. Hammersley. Percolation processes and related topics. J. Siam Appl. Math. 11 (1963) 894-918.Google Scholar
- 10.M.R. Garey, D.S. Johnson and L.J. Stockmeyer. Some simplified NP-complete problems. Proc. 6th ACM Symp. on Theory of Computing. (1974) 47-63. Google ScholarDigital Library
- 11.M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems. Proc. 8th ACM Symp. on Theory of Computing (1976) 10-22. Google ScholarDigital Library
- 12.H.S. Green and G.A. Hurst. Order-Disorder Phenomena. Interscience. London (1964).Google Scholar
- 13.J.M. Hammersley. Existence theorems and Monte Carlo methods for the monomer-dimer problem. Research Papers in Statistics 125-146.Google Scholar
- 14.L. Hyafil. On the parallel evaluation of multivariate polynomials. Proc. Tenth ACM Symp. on Theory of Computing (1978) 193-195. Google ScholarDigital Library
- 15.R.M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, eds.) Plenum Press, New York (1972).Google Scholar
- 16.P.W. Kasteleyn. Graph theory and crystal physics. In Graph Theory and Theoretical Physics, (F. Harary, ed.), Academic Press (1967).Google Scholar
- 17.M. Marcus and H. Minc. On the relation between the determinant and the permanent. Illinois J. Math 5 (1961) 376-381.Google ScholarCross Ref
- 18.G. Polya. Aufgabe 424. Arch. Math. Phys (3) 20 (1913) 27.Google Scholar
- 19.H.J. Ryser. Combinatorial Mathematics. Carus Math. Monograph no. 14 (1963).Google Scholar
- 20.J.E. Savage. The Complexity of Computing, Wiley, New York (1976). Google ScholarDigital Library
- 21.L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science. (to appear).Google Scholar
- 22.L.G. Valiant. The complexity of enumeration and reliability problems. SIAM J. on Computing, (to appear).Google Scholar
- 23.D.J.A. Welsh. Percolation and related topics. Science Progress, Oxford 64 (1977) 65-83.Google Scholar
Index Terms
- Completeness classes in algebra
Recommendations
Measure Theoretic Completeness Notions for the Exponential Time Classes
MFCS '00: Proceedings of the 25th International Symposium on Mathematical Foundations of Computer ScienceThe resource-bounded measure theory of Lutz leads to variants of the classical hardness and completeness notions. While a set A is hard (under polynomial time many-one reducibility) for a complexity class C if every set in C can be reduced to A, a set A ...
Completeness in approximation classes beyond APX
We present a reduction that allows us to establish completeness results for several approximation classes mainly beyond APX. Using it, we extend one of the basic results of S. Khanna, R. Motwani, M. Sudan, and U. Vazirani (On syntactic versus ...
Comments