Article

The complexity of counting functions with easy decision version

Authors:

Aris Pagourtzis,

Stathis ZachosAuthors Info & Claims

MFCS'06: Proceedings of the 31st international conference on Mathematical Foundations of Computer Science

Pages 741 - 752

https://doi.org/10.1007/11821069_64

Published: 28 August 2006 Publication History

Abstract

We investigate the complexity of counting problems that belong to the complexity class #P and have an easy decision version. These problems constitute the class #PE which has some well-known representatives such as #Perfect Matchings, #DNF-Sat, and NonNegative Permanent. An important property of these problems is that they are all #P-complete, in the Cook sense, while they cannot be #P-complete in the Karp sense unless P = NP.

We study these problems in respect to the complexity class TotP, which contains functions that count the number of all paths of a PNTM. We first compare TotP to #P and #PE and show that FP⊆TotP⊆#PE⊆#P and that the inclusions are proper unless P = NP.

We then show that several natural #PE problems — including the ones mentioned above — belong to TotP. Moreover, we prove that TotP is exactly the Karp closure of self-reducible functions of #PE. Therefore, all these problems share a remarkable structural property: for each of them there exists a polynomial-time nondeterministic Turing machine which has as many computation paths as the output value.

References

[1]

C. Àlvarez, B. Jenner. A very hard log space counting class. In Proceedings of Structure in Complexity Theory Conference 1990: 154-168.

[2]

A. Durand, M. Hermann, and P. G. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. Theoretical Computer Science 340(3): 496-513, 2005.

Digital Library

[3]

M. Dyer, L. A. Goldberg, C. Greenhill, and M. Jerrum. On the relative complexity of approximate counting problems. Algorithmica 38(3): 471- 500 (2003).

[4]

L.A. Hemaspaandra, C.M. Homan, S. Kosub, and K.W. Wagner. The complexity of computing the size of an interval. Technical Report cs.cc/0502058, ACM Computing Research Repository, February 2005. (Preliminary version: L.A. Hemaspaandra, S. Kosub, and K.W. Wagner, The complexity of computing the size of an interval, in Proceedings ICALP 2001, LNCS 2076, pp. 1040-1051, Springer 2001.).

Digital Library

[5]

M. Jerrum and A. Sinclair. The Markov chain Monte-Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Dorit Hochbaum, ed.), PWS, pp. 482- 520, 1996.

Digital Library

[6]

R.M. Karp, M. Luby, and N. Madras. Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms 10: 429-448 (1989).

Digital Library

[7]

A. Kiayias, A. Pagourtzis, K. Sharma, and S. Zachos. The complexity of determining the order of solutions. In Proceedings of the First Southern Symposium on Computing, Hattiesburg, Mississippi, 4-5 December 1998.

[8]

A. Kiayias, A. Pagourtzis, and S. Zachos. Cook Reductions Blur Structural Differences Between Functional Complexity Classes. In Proceedings of the 2nd Panhellenic Logic Symposium, pp. 132-137, Delphi, 13-17 July 1999.

[9]

On Self-Reducibility and Weak P-Selectivity. Journal of Computer and System Sciences, 26(2):209-221, 1983.

[10]

M. W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490-509, June 1988.

Digital Library

[11]

J. Köbler, U. Schöning, and J. Torán. On counting and approximation. Acta Informatica, 26(4):363-379, 1989.

Digital Library

[12]

A. Pagourtzis. On the complexity of hard counting problems with easy decision version. In Proceedings of the 3rd Panhellenic Logic Symposium, Anogia, Crete, 17-21 July 2001.

[13]

S. Saluja, K. V. Subrahmanyam, and M. N. Thakur. Descriptive Complexity of #P Functions. Journal of Computer and System Sciences, 50(3): 493-505 (1995).

Digital Library

[14]

J. Simon. On some Central Problems of Computational Complexity. PhD thesis, Cornell University, Ithaca, NY, 1975.

Digital Library

[15]

S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991.

Digital Library

[16]

S. Toda and O. Watanabe. Polynomial-time 1-Turing reductions from #PH to #P. Theoretical Computer Science, 100(1):205-221, 1992.

Digital Library

[17]

J. Toran. Structural Properties of the Counting Hierarchies. PhD thesis, Facultat d'Informatica de Barcelona, 1988.

[18]

L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, April 1979.

[19]

L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410-421, August 1979.

Digital Library

[20]

H. Vollmer. On different reducibility notions for function classes. In Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, volume 775 of Lecture Notes in Computer Science, pages 449-460, Caen, France, 24-26 February 1994. Springer.

Digital Library

[21]

K. W. Wagner. Some observations on the connection between counting and recursion. Theoretical Computer Science, 47(2):131-147, 1986.

Digital Library

Cited By

Bakali EChalki AKanellopoulos SPagourtzis AZachos S(2024)On the Power of Counting the Total Number of Computation Paths of NPTMsTheory and Applications of Models of Computation10.1007/978-981-97-2340-9_18(209-220)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2340-9_18
Bakali EChalki APagourtzis A(2020)Characterizations and Approximability of Hard Counting Classes Below Theory and Applications of Models of Computation10.1007/978-3-030-59267-7_22(251-262)Online publication date: 18-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-59267-7_22
Triommatis TPagourtzis A(2020)Approximate #Knapsack Computations to Count Semi-fair AllocationsTheory and Applications of Models of Computation10.1007/978-3-030-59267-7_21(239-250)Online publication date: 18-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-59267-7_21
Show More Cited By

Recommendations

Completeness, approximability and exponential time results for counting problems with easy decision version
Highlights
- The first TotP-complete problems under parsimonious reductions.
- Hardness of ...
Abstract
Hard counting problems with easy decision version, like computing the permanent and counting independent sets, are of particular importance in counting complexity theory. TotP is the class of all self-reducible problems in # P with ...
The Complexity of Planar Counting Problems

We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set,...
Nonuniformly hard boolean functions and uniform complexity classes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

MFCS'06: Proceedings of the 31st international conference on Mathematical Foundations of Computer Science

August 2006

813 pages

ISBN:3540377913

Editors:
Rastislav Královič
Department of Computer Science, Comenius University, Mlynská dolina, Bratislava, Slovakia
,
Paweł Urzyczyn
Institute of Informatics, University of Warsaw, Bratislava, Poland

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 28 August 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bakali EChalki AKanellopoulos SPagourtzis AZachos S(2024)On the Power of Counting the Total Number of Computation Paths of NPTMsTheory and Applications of Models of Computation10.1007/978-981-97-2340-9_18(209-220)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2340-9_18
Bakali EChalki APagourtzis A(2020)Characterizations and Approximability of Hard Counting Classes Below Theory and Applications of Models of Computation10.1007/978-3-030-59267-7_22(251-262)Online publication date: 18-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-59267-7_22
Triommatis TPagourtzis A(2020)Approximate #Knapsack Computations to Count Semi-fair AllocationsTheory and Applications of Models of Computation10.1007/978-3-030-59267-7_21(239-250)Online publication date: 18-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-59267-7_21
Calautti MConsole MPieris ASuciu DSkritek SKoch C(2019)Counting Database Repairs under Primary Keys RevisitedProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3294052.3319703(104-118)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3294052.3319703
Lorenz J(2019)On the Complexity of RestartingComputer Science – Theory and Applications10.1007/978-3-030-19955-5_22(250-261)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-19955-5_22
Arenas MMuñoz MRiveros CAceto LIngólfsdóttir A(2017)Descriptive complexity for counting complexity classesProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330085(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330085
Hermann MPichler R(2009)Complexity of counting the optimal solutionsTheoretical Computer Science10.1016/j.tcs.2009.05.025410:38-40(3814-3825)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.05.025
Bampas EGöbel APagourtzis ATentes A(2009)On the Connection between Interval Size Functions and Path CountingProceedings of the 6th Annual Conference on Theory and Applications of Models of Computation10.1007/978-3-642-02017-9_14(108-117)Online publication date: 12-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-02017-9_14
Hermann MPichler R(2008)Complexity of Counting the Optimal SolutionsProceedings of the 14th annual international conference on Computing and Combinatorics10.1007/978-3-540-69733-6_16(149-159)Online publication date: 27-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69733-6_16
Lifshits Y(2007)Processing compressed textsProceedings of the 18th annual conference on Combinatorial Pattern Matching10.5555/2394373.2394405(228-240)Online publication date: 9-Jul-2007
https://dl.acm.org/doi/10.5555/2394373.2394405

View Options

View options

Media

Figures

Other

Tables

View Table of Contents