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

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

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)

Cites Work

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

Cited In (8)

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

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)