Subtractive Reductions and Complete Problems for Counting Complexity Classes

Abstract : We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes #.Pi_k P, k > 2, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class #.coNP) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.
Type de document :
Communication dans un congrès
M. Nielsen et B. Rovan. 25th International Symposium on Mathematical Foundations of Computer Science - MFCS'2000, 2000, Bratislava, Slovaquie, Springer-Verlag, 1893, pp.323-332, 2000, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00099381
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:53:27
Dernière modification le : lundi 5 février 2018 - 11:04:02

Identifiants

  • HAL Id : inria-00099381, version 1

Collections

Citation

Arnaud Durand, Miki Hermann, Phokion G. Kolaitis. Subtractive Reductions and Complete Problems for Counting Complexity Classes. M. Nielsen et B. Rovan. 25th International Symposium on Mathematical Foundations of Computer Science - MFCS'2000, 2000, Bratislava, Slovaquie, Springer-Verlag, 1893, pp.323-332, 2000, Lecture Notes in Computer Science. 〈inria-00099381〉

Partager

Métriques

Consultations de la notice

156