The Inverse Satisfiability Problem
From MaRDI portal
Publication:4210141
DOI10.1137/S0097539795285114zbMath0917.68079OpenAlexW2034069868MaRDI QIDQ4210141
Dimitris J. Kavvadias, Martha Sideris
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
Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Number-theoretic algorithms; complexity (11Y16) Parallel algorithms in computer science (68W10)
Related Items (13)
Generating all maximal models of a Boolean expression ⋮ The complexity of minimal satisfiability problems ⋮ On the Boolean connectivity problem for Horn relations ⋮ \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete ⋮ Deciding quantifier-free definability in finite algebraic structures ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ Structure identification of Boolean relations and plain bases for co-clones ⋮ Isomorphic implication ⋮ Unnamed Item ⋮ An efficient algorithm for Horn description ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ A Dichotomy Theorem for the Inverse Satisfiability Problem ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction
This page was built for publication: The Inverse Satisfiability Problem