The Inverse Satisfiability Problem

DOI10.1137/S0097539795285114MaRDI QIDQ4210141zbMATH OpenOpenAlexFDO

Authors Dimitris J. Kavvadias, Martha Sideri

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539795285114

zbMATH Keywords

Boolean satisfiabilitycomputational complexitycoNP-completenessmodelpolynomial-time algorithms

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Parallel algorithms in computer science (68W10)

Recommendations

• A dichotomy theorem for the inverse satisfiability problem
• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• The complexity of satisfiability problems
• A simplified NP-complete satisfiability problem
• scientific article; zbMATH DE number 496040

Cited in

(20)

• An efficient algorithm for Horn description
• The complexity of minimal satisfiability problems
• Deciding quantifier-free definability in finite algebraic structures
• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• Isomorphic implication
• Generating all maximal models of a Boolean expression
• \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete
• scientific article; zbMATH DE number 496040 (Why is no real title available?)
• On the strength of uniqueness quantification in primitive positive formulas
• A dichotomy theorem for the inverse satisfiability problem
• The Complexity of Satisfaction Problems in Reverse Mathematics
• Inverse Unfold Problem and Its Heuristic Solving
• Mathematical Foundations of Computer Science 2003
• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Computational Short Cuts in Infinite Domain Constraint Satisfaction
• On the Boolean connectivity problem for Horn relations
• The inverse satisfiability problem
• The inequality-satisfiability problem
• Structure identification of Boolean relations and plain bases for co-clones

This page was built for publication: The Inverse Satisfiability Problem

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