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.  

 

Video Recording