The Inverse Satisfiability Problem

DOI10.1137/S0097539795285114MaRDI QIDQ4210141zbMATHOpenAlexFDO

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

computational complexitymodelpolynomial-time algorithmscoNP-completenessBoolean satisfiability

Mathematics Subject Classification ID

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

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)

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

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)