Fine-grained structure of NP-hard SAT problems

Prelegent(ci)

Magnus Wahlström

Afiliacja

University of London

Termin

8 marca 2018 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Say that a problem SAT(\Gamma), for a constraint language \Gamma,
admits an improved algorithm if it can be solved in O(c^n) time on n
variables for some c<2, and that it is hard otherwise.  Many examples
exist, both of problems SAT(\Gamma) with improved algorithms and
problems hypothesised to be hard (by SETH, the strong exponential-time
hypothesis). But what is the furthest possible reach of languages
\Gamma with improved algorithms, and how could we characterise them?

The main insight here (from the study of the complexity of constraint
satisfaction problems) is that for these questions we should not study
the specific contents of a language \Gamma, but its "expressive power"
-- i.e., which other constraints can it express using appropriate
complexity-preserving gadget implementations? This expressive power 
is in turn characterised by algebraic invariants of \Gamma, which for
the fine-grained case are of a type called partial polymorphisms. 
Thus our question becomes: Which partial polymorphisms (or sets of
partial polymorphisms) are powerful enough to imply the existence of
an improved algorithm, and which ones leave a "SETH-hard" problem
(i.e., a problem which is hard assuming SETH)?

We focus on the weakest possible such restrictions, corresponding to
the most powerful problems SAT(\Gamma), and show the structure of the
set of such restrictions, and how it relates to previously studied 
problems such as k-SAT, Exact SAT, and the more recently investigated
case of constraints defined by roots of polynomial equations of
bounded degree.  We also show upper and lower bounds on the running
time of such problems; in particular, we give the first problem
SAT(\Gamma) which simultaneously has non-trivial upper and lower
bounds on its running time (under SETH).  

---