Complexity of partial satisfaction. II. (Q452481): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / 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)]. | |||
Property / 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)]. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q17 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6084849 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
complexity | |||
Property / zbMATH Keywords: complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
hardness | |||
Property / zbMATH Keywords: hardness / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
maximum satisfiability problem | |||
Property / zbMATH Keywords: maximum satisfiability problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
NP-complete | |||
Property / zbMATH Keywords: NP-complete / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q106019114 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of Partial Satisfaction / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithmic extremal problems in combinatorial optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of satisfiability problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Local Versus Global Satisfiability / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.4171/em/202 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2070114427 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:51, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity of partial satisfaction. II. |
scientific article |
Statements
Complexity of partial satisfaction. II. (English)
0 references
21 September 2012
0 references
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)].
0 references
complexity
0 references
hardness
0 references
maximum satisfiability problem
0 references
NP-complete
0 references