Complexity of Partial Satisfaction II
Copyright policy )Complexity of Partial Satisfaction II
What is easy and when does it become hard to find a solution of a problem? We give a sharp answer to this question for various generalizations of the well-known maximum satisfiability problem. For several maximum ψ -satisfiability problems we explicitly determine algebraic numbers τ_ψ (0 < τ_ψ < 1) , which separate NP-complete from polynomial problems. The fraction τ_ψ of the clauses of a ψ -formula can be satisfied in polynomial time, while the set of ψ-formulas which have an assignment satisfying the fraction τ' (τ' > τ_ψ, τ' rational) of the clauses is NP-complete.
- Massachusetts Institute of Technology United States
- Northwestern University United States
- ETH Zurich Switzerland
Analysis of algorithms and problem complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), maximum satisfiability problem, complexity, hardness, NP-complete
Analysis of algorithms and problem complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), maximum satisfiability problem, complexity, hardness, NP-complete
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!