Completeness results for counting problems with easy decision

DOI10.1007/978-3-319-57586-5_6zbMATH Open1486.68078OpenAlexW2606244929MaRDI QIDQ5283355FDOQ5283355

Authors Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos, Stathis Zachos

Publication date 21 July 2017

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

Full work available at URL https://doi.org/10.1007/978-3-319-57586-5_6

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational aspects of satisfiability (68R07)

Recommendations

• The Complexity of Counting Functions with Easy Decision Version
• The relative complexity of approximate counting problems
• scientific article; zbMATH DE number 1670534
• On the connection between interval size functions and path counting
• On the Connection between Interval Size Functions and Path Counting

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1953880 (Why is no real title available?)
• A very hard log-space counting class
• An FPTAS for #Knapsack and Related Counting Problems
• Approximate counting by dynamic programming
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Computational Complexity
• Descriptive complexity of \(\#\)P functions
• Estimating the Efficiency of Backtrack Programs
• Monte-Carlo approximation algorithms for enumeration problems
• On counting and approximation
• On the connection between interval size functions and path counting
• On the solution-space geometry of random constraint satisfaction problems
• Random formulas have frozen variables
• The Complexity of Computing the Size of an Interval
• The Complexity of Counting Functions with Easy Decision Version
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Ferromagnetic Ising with Local Fields
• The complexity of computing the permanent
• The relative complexity of approximate counting problems

Cited in

(8)

• On the Connection between Interval Size Functions and Path Counting
• Completeness, approximability and exponential time results for counting problems with easy decision version
• On the existence of n but not n + 1 easy combinators
• On the connection between interval size functions and path counting
• The relative complexity of approximate counting problems
• The Complexity of Counting Functions with Easy Decision Version
• Stathis Zachos at 70!
• Tally NP sets and easy census functions.

This page was built for publication: Completeness results for counting problems with easy decision

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