The weight in enumeration

DOI10.1007/978-3-319-53733-7_15MaRDI QIDQ5738998zbMATH OpenOpenAlexFDO

Authors

Publication date 1 June 2017

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityenumerationnon-decreasing weightpolynomial delayPost's lattice

Mathematics Subject Classification ID

Classical propositional logic (03B05) Exact enumeration problems, generating functions (05A15) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Nonnumerical algorithms (68W05)

Abstract: In our setting enumeration amounts to generate all solutions of a problem instance without duplicates. We address the problem of enumerating the models of B-formulae. A B-formula is a propositional formula whose connectives are taken from a fixed set B of Boolean connectives. Without imposing any specific order to output the solutions, this task is solved. We completely classify the complexity of this enumeration task for all possible sets of connectives B imposing the orders of (1) non-decreasing weight, (2) non-increasing weight; the weight of a model being the number of variables assigned to 1. We consider also the weighted variants where a non-negative integer weight is assigned to each variable and show that this add-on leads to more sophisticated enumeration algorithms and even renders previously tractable cases intractable, contrarily to the constraint setting. As a by-product we obtain complete complexity classifications for the optimization problems known as Min-Ones and Max-Ones which are in the B-formula setting two different tasks.

Recommendations

• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• Parameterized complexity of weighted satisfiability problems
• Paradigms for parameterized enumeration
• Counting All Solutions of Minimum Weight Exact Satisfiability

Cites work

• Complexity classifications for different equivalence and audit problems for Boolean circuits
• Complexity classifications for propositional abduction in Post's framework
• Enumerating All Solutions for Constraint Satisfaction Problems
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• Enumeration of the monomials of a polynomial and related complexity classes
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Mathematical Foundations of Computer Science 2003
• On generating all maximal independent sets
• On generating all solutions of generalized satisfiability problems
• Satisfiability problems for propositional calculi
• Subtractive reductions and complete problems for counting complexity classes
• The Complexity of Circumscriptive Inference in Post’s Lattice
• The complexity of propositional implication
• The complexity of satisfiability problems
• The complexity of weighted and unweighted \(\#\)CSP

Cited in

(1)

• Enumerating all solutions of a Boolean CSP by non-decreasing weight

This page was built for publication: The weight in enumeration

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