Complexity of partial satisfaction. II.
type: Item
instance of: scholarly article
title: Complexity of partial satisfaction. II.
zbMATH Open document ID: 1283.68165
DOI: 10.4171/EM/202
author: Karl J. Lieberherr
author: Ernst Specker
published in: Elemente der Mathematik
publication date: 2012-09-21T00:00:00Z
review text: Summary: 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 \(\psi\)-satisfiability problems we explicitly determine algebraic numbers \(\tau_{\psi}\), \(0<\tau_{\psi} < 1\), which separate NP-complete from polynomial problems. The fraction \(\tau_{\psi}\) of the clauses of a \(\psi\)-formula can be satisfied in polynomial time, while the set of \(\psi\)-formulas which have an assignment satisfying the fraction \(\tau'\), where \(\tau' > \tau_{\psi}\) and \(\tau'\) is rational, of the clauses is NP-complete. For Part I see [the authors, J. Assoc. Comput. Mach. 28, 411--421 (1981; Zbl 0456.68078)].
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6084849
zbMATH Keywords: complexity
zbMATH Keywords: hardness
zbMATH Keywords: maximum satisfiability problem
zbMATH Keywords: NP-complete
Wikidata QID: Q106019114
MaRDI profile type: Publication
cites work: Complexity of Partial Satisfaction
cites work: Algorithmic extremal problems in combinatorial optimization
cites work: The complexity of satisfiability problems
cites work: On Local Versus Global Satisfiability
full work available at URL: https://doi.org/10.4171/em/202
OpenAlex ID: W2070114427
description: scientific article; zbMATH DE number 6084849