![](/sites/default/files/styles/workshop_banner_sm_1x/public/satisfiability_theory_practice_and_beyond.png.jpg?itok=s4ZlXb5c)
Abstract
Strict NP is a syntactic fragment of existential second-order logic that can express fundamental NP-complete problems, such as 3-SAT and 3-Colorability. The aim of this talk is to give an overview of some facets of Strict NP, including 0-1 laws and connections between Strict NP on one side and approximation algorithms, constraint satisfaction, and sub-exponential algorithms on the other side.