Strict NP: Expressive Power, Structure, and Complexity
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Defines Strict NP (SNP) as the fragment of existential second‑order logic with only universal first‑order quantifiers and shows SNP is a proper subset of ESO by preservation arguments; gives concrete encodings: 3SAT, 3‑colorability and Monochromatic Triangle are in SNP, MAX‑3SAT is MAX‑SNP complete, and MAX‑SNP problems admit constant approximations via Papadimitriou–Giannakakis L‑reductions (PCP then rules out PTAS for complete cases). Proves a zero‑one law for SNP with decision problem in NEXPTIME, relates MMSNP to CSP via MMSNP↔CSP reductions (randomized, then derandomized using expanders and twisted products), and connects SNP completeness to subexponential lower bounds using the sparsification lemma.
AI-written summary · about
chapters (23)
- 0:00Intro
- 1:44Logic as a Specification Language
- 3:39First-order and Second-Order Logic
- 4:40Existential Second-Order Logic
- 7:22Strict NP (Strict ESO)
- 8:49SNP and 3-SAT
- 10:43SNP and 3-Colorability
- 11:38SNP and Monochromatic Triangle
- 12:30The Many Facets of SNP
- 13:55Asymptotic Probabilities
- 15:570-1 Laws
- 20:48Complexity of 0-1 Law for Extended SNP
- 22:38Approximation Algorithms
- 26:44MAX 3-SAT
- 27:38MAX CUT
- 28:36Properties of MAX SNP
- 30:17MAX SNP Complete Problems
- 32:37Constraint Satisfaction
- 33:23CSP and the Homomorphism Problem
- 35:08CSP and Monotone Monadic SNP
- 43:57Sub-Exponential Complexity and SNP
- 48:22Synopsis
- 50:37Dichotomy Theorems and their Limits