This chapter discusses the analysis of the computational complexity of enumeration problems, including the comparison among the complexity classes with respect to Counting Turing Machines. Enumeration problems constitute a major part of computational binatorial mathematics. The input of an enumeration problem is the description of a (finite) set; the required output is the cardinality of such a set. Combinatorial mathematics expresses the solution of enumeration problems by means of solving formulas, generally based on the usual arithmetic operations. The chapter presents a strong characterization theorem, stating that every problem in # P-SPACE can be solved in polynomial time by a random-access memory (RAM) with the operations of sum, product, integer subtraction, and integer division. © 1985, Elsevier Inc. All rights reserved.
Bertoni, A., Mauri, G., Sabadini, N. (1985). Simulations Among Classes of Random Access Machines and Equivalence Among Numbers Succinctly Represented. In G. Ausiello, M. Lucertini (a cura di), Analysis and Design of Algorithms for Combinatorial Problems (pp. 65-89). Amsterdam : North-Holland [10.1016/S0304-0208(08)73103-7].
Simulations Among Classes of Random Access Machines and Equivalence Among Numbers Succinctly Represented
MAURI, GIANCARLO;
1985
Abstract
This chapter discusses the analysis of the computational complexity of enumeration problems, including the comparison among the complexity classes with respect to Counting Turing Machines. Enumeration problems constitute a major part of computational binatorial mathematics. The input of an enumeration problem is the description of a (finite) set; the required output is the cardinality of such a set. Combinatorial mathematics expresses the solution of enumeration problems by means of solving formulas, generally based on the usual arithmetic operations. The chapter presents a strong characterization theorem, stating that every problem in # P-SPACE can be solved in polynomial time by a random-access memory (RAM) with the operations of sum, product, integer subtraction, and integer division. © 1985, Elsevier Inc. All rights reserved.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
