Spring 2021

Strict NP: Expressive Power, Structure, and Complexity

Thursday, April 22nd, 2021, 9:30 am10:30 am

Add to Calendar


Phokion Kolaitis (UC Santa Cruz  & IBM Research)



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.