The complexity of facets resolved
From MaRDI portal
Publication:1109565
DOI10.1016/0022-0000(88)90042-6zbMath0655.68041OpenAlexW2158505527WikidataQ59795818 ScholiaQ59795818MaRDI QIDQ1109565
David Wolfe, Christos H. Papadimitriou
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6542
Related Items (60)
Witnesses for Answer Sets of Logic Programs ⋮ Knapsack polytopes: a survey ⋮ Computing Maximal Autarkies with Few and Simple Oracle Queries ⋮ DP-Complete Problems Derived from Extremal NP-Complete Properties ⋮ Local-search extraction of mUSes ⋮ Redundancy in logic. II: 2CNF and Horn propositional formulae ⋮ Redundancy in logic. III: Non-monotonic reasoning ⋮ Density condensation of Boolean formulas ⋮ The complexity of recognizing minimally tough graphs ⋮ Localising iceberg inconsistencies ⋮ Better approximations of non-Hamiltonian graphs ⋮ Understanding the complexity of axiom pinpointing in lightweight description logics ⋮ Using inconsistency measures for estimating reliability ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ A FRAMEWORK FOR HANDLING LOGICAL INCONSISTENCIES IN THE FUSION OF BOOLEAN KNOWLEDGE BASES ⋮ Super-reparametrizations of weighted CSPs: properties and optimization perspective ⋮ How Many Conflicts Does It Need to Be Unsatisfiable? ⋮ Justifications for Description Logic Knowledge Bases Under the Fixed-Domain Semantics ⋮ On measuring inconsistency in definite and indefinite databases with denial constraints ⋮ On getting rid of the preprocessing minimization step in MUC-finding algorithms ⋮ On the structure of some classes of minimal unsatisfiable formulas ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ Homomorphisms of conjunctive normal forms. ⋮ Towards a notion of unsatisfiable and unrealizable cores for LTL ⋮ Computing smallest MUSes of quantified Boolean formulas ⋮ Two tractable subclasses of minimal unsatisfiable formulas ⋮ Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases ⋮ On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas ⋮ Redundancy in logic. I: CNF propositional formulae ⋮ Faster Extraction of High-Level Minimal Unsatisfiable Cores ⋮ Complexity of stability ⋮ Finding read-once resolution refutations in systems of 2CNF clauses ⋮ On semidefinite least squares and minimal unsatisfiability ⋮ Computational complexity of quantified Boolean formulas with fixed maximal deficiency ⋮ Complexity of Stability. ⋮ On the complexity of non-unique probe selection ⋮ Removing redundancy from a clause ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ Selected topics on assignment problems ⋮ Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ The complexity of variable minimal formulas ⋮ An upper bound for the circuit complexity of existentially quantified Boolean formulas ⋮ The complexity of homomorphisms and renamings for minimal unsatisfiable formulas ⋮ Extension and equivalence problems for clause minimal formulae ⋮ A simplified way of proving trade-off results for resolution ⋮ How to recycle your facets ⋮ On the Complexity of Semantic Self-minimization ⋮ Dealing Automatically with Exceptions by Introducing Specificity in ASP ⋮ Finding Optimal Solutions With Neighborly Help. ⋮ An approach for extracting a small unsatisfiable core ⋮ Strong inconsistency ⋮ On the complexity of inconsistency measurement ⋮ A branch and bound algorithm for extracting smallest minimal unsatisfiable subformulas ⋮ Using local search to find MSSes and MUSes ⋮ On subclasses of minimal unsatisfiable formulas ⋮ Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. ⋮ Accelerated Deletion-based Extraction of Minimal Unsatisfiable Cores ⋮ Semantic relevance ⋮ On the query complexity of selecting minimal sets for monotone predicates
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- NP is as easy as detecting unique solutions
- On certain polytopes associated with graphs
- On the symmetric travelling salesman problem II: Lifting theorems and facets
- On the unique satisfiability problem
- On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Solution of a Large-Scale Traveling-Salesman Problem
This page was built for publication: The complexity of facets resolved
