The Complexity of Counting Functions with Easy Decision Version

DOI10.1007/11821069_64MaRDI QIDQ5756679zbMATH OpenOpenAlexFDO

Authors Aris Pagourtzis, Stathis Zachos

Publication date 5 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11821069_64

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the Connection between Interval Size Functions and Path Counting
• On the connection between interval size functions and path counting
• Completeness results for counting problems with easy decision
• scientific article; zbMATH DE number 1953880
• Polynomial Space Counting Problems

Cited in

(15)

• Completeness, approximability and exponential time results for counting problems with easy decision version
• A structured view on weighted counting with relations to counting, quantum computation and applications
• On the connection between interval size functions and path counting
• Complexity of Counting the Optimal Solutions
• On the Connection between Interval Size Functions and Path Counting
• scientific article; zbMATH DE number 1953880 (Why is no real title available?)
• Counting of Teams in First-Order Team Logics
• Descriptive complexity for counting complexity classes
• Completeness results for counting problems with easy decision
• Stathis Zachos at 70!
• On the power of counting the total number of computation paths of NPTMs
• Counting of teams in first-order team logics
• Closure properties and characterizations of TotP
• Complexity of counting the optimal solutions
• On the autoreducibility of functions

This page was built for publication: The Complexity of Counting Functions with Easy Decision Version

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5756679)