Expansions of pseudofinite structures and circuit and proof complexity
arXiv:1505.00118
Abstract
I shall describe a general model-theoretic task to construct expansions of pseudofinite structures and discuss several examples of particular relevance to computational complexity. Then I will present one specific situation where finding a suitable expansion would imply that, assuming a one-way permutation exists, the computational class NP is not closed under complementation.
arXiv commentPreliminary version May 2015