A complexity theory for hard enumeration problems

DOI10.1016/j.dam.2019.02.025zbMath1419.05016arXiv1610.05493OpenAlexW2766363310MaRDI QIDQ2274092

Reinhard Pichler, Heribert Vollmer, Markus Kröll, Sebastian Skritek, Nadia Creignou

Publication date: 19 September 2019

Published in: Discrete Applied Mathematics, Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.05493

zbMATH Keywords

computational complexityenumerationreductionscomplexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Unnamed Item ⋮ Enumerating teams in first-order team logics ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ The statistical analysis for Sombor indices in a random polygonal chain networks ⋮ Enumerating \(k\)-arc-connected orientations ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Incremental delay enumeration: space and time ⋮ A complexity theory for hard enumeration problems ⋮ Unnamed Item ⋮ On the dualization in distributive lattices and related problems ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Enumeration complexity of conjunctive queries with functional dependencies

Cites Work

• Unnamed Item
• Unnamed Item
• On enumerating monomials and other combinatorial structures by polynomial interpolation
• A theory of diagnosis from first principles
• On generating all maximal independent sets
• Candidate keys for relations
• A complexity theory for hard enumeration problems
• Subtractive reductions and complete problems for counting complexity classes
• Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting
• PP is as Hard as the Polynomial-Time Hierarchy
• Enumeration of the Monomials of a Polynomial and Related Complexity Classes
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• The complexity of logic-based abduction
• On generating all solutions of generalized satisfiability problems
• The Complexity of Mining Maximal Frequent Subgraphs
• On the Enumeration of Minimal Dominating Sets and Related Notions
• On the Complexity of Enumerating the Answers to Well-designed Pattern Trees
• First-order queries on structures of bounded degree are computable with constant delay
• Computational Complexity
• The complexity of satisfiability problems
• A Complete Classification of the Complexity of Propositional Abduction

This page was built for publication: A complexity theory for hard enumeration problems