Complexity of Partial Satisfaction

DOI10.1145/322248.322260zbMath0456.68078OpenAlexW2005180798MaRDI QIDQ3906440

Ernst Specker, Karl J. Lieberherr

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322248.322260

zbMATH Keywords

NP-completesatisfiabilitygolden meandoubly transitive permutationspolynomial enumeration algorithmpolynomially constructive reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items

Implications of forbidden structures for extremal algorithmic problems, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, A new bound for 3-satisfiable MaxSat and its algorithmic application, Unnamed Item, Partial Satisfaction of k-Satisfiable Formulas, Sublinear-space approximation algorithms for Max \(r\)-SAT, Complexity of partial satisfaction. II., Probabilistic bounds and algorithms for the maximum satisfiability problem, On existence theorems, A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications, Pseudo-Boolean optimization, Solving weighted MAX-SAT via global equilibrium search, Checking robust nonsingularity is NP-hard, A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application, Algorithms for the maximum satisfiability problem, Tight bound on Johnson's algorithm for maximum satisfiability, Locally consistent constraint satisfaction problems