NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k ) (Q3507322)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k ) |
scientific article |
Statements
NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k ) (English)
0 references
19 June 2008
0 references
PCP theorem
0 references
linear CNF formula
0 references
LSAT
0 references
NP-completeness
0 references
reduction
0 references
minimal unsatisfiable (MU) formula
0 references
