Expansions of pseudofinite structures and circuit and proof complexity
Jan Krajı́ček · arXiv (Cornell University) · 2015
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.