NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k ) (Q3507322)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5290791
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k ) |
scientific article; zbMATH DE number 5290791 |
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
0 references
0.8695179
0 references
0.86028445
0 references
0.8509108
0 references
0.8464759
0 references
0.8457304
0 references
0.8452046
0 references
0.84276897
0 references
0.8426471
0 references
0.83787006
0 references
