Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Enumeration problems constitute a major part of combinatorial mathematics. Combinatorial mathematics expresses the solution of enumeration problems by means of solving formulas, generally based on the usual arithmetic operations [7]. These solving formulas can be formally represented as programs for a Random Access Machine (RAM) with arithmetical primitives, for which the natural complexity measure is the arithmetical complexity [1].

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Bertoni, A., Mauri, G., On efficient computation of the coefficients of some polynomials, with applications to some counting problems, Res. Rep. IC.78.3, Ist. di Cibernetica, Univ. di Milano, 1978
• 3: Borodin, A., Munro, I., The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York, 1975
• 4: Chandra, A., Stockmeyer, L.J., Alternation, Proc. 17th FOCS, 1976, 98-108
• 5: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 6: Garey, M.R., Johnson, D.S., Computers and Intractability, W.H. Freeman and Co., San Francisco, 1979
• 7: Hartmanis, J., Simon, J., On the power of multiplication in Random Access Machines, IEEE Conf. Rec. 15th Symp. on Switching Automata Theory, 1974, 13-23
• 8: Percus, J.K., Combinatorial Methods, Springer, Berlin, 1971
• 9: Vaughan R. Pratt , Michael O. Rabin , Larry J. Stockmeyer, A characterization of the power of vector machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.122-134, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803892]
• 10: Pratt, V., Stockmeyer, L., A characterization of the power of Vector Machines, JCSS, 12, 1976, 198-221
• 11: Arnold Schönhage, On the Power of Random Access Machines, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.520-529, July 16-20, 1979
• 12: Janos Simon, On some central problems in computational complexity., 1975
• 13: Janos Simon, On the Difference Between One and Many (Preliminary Version), Proceedings of the Fourth Colloquium on Automata, Languages and Programming, p.480-491, July 18-22, 1977
• 14: Simon, J., Division is good, Comp. Sci. Dept., Pennsylvania State University, 1979
• 15: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 16: Valiant, L.G., The complexity of computing the permanent, Theoretical Computer Science 8, 1979, 189-202
• 17: Valiant, L.G., The complexity of enumeration and reliability problems, Res. Rep. CSR-15 77, Dept. of Comp. Sci., Univ. of Edinburgh, 1977

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Recurrences and difference equations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Theory