Complexity of Partial Satisfaction
From MaRDI portal
Publication:3906440
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
NP-completesatisfiabilitygolden meandoubly transitive permutationspolynomial enumeration algorithmpolynomially constructive reductions
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
