arXiv Analytics

Sign in

arXiv:1505.00118 [math.LO]AbstractReferencesReviewsResources

Expansions of pseudofinite structures and circuit and proof complexity

Jan Krajicek

Published 2015-05-01Version 1

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.

Comments: Preliminary version May 2015
Categories: math.LO, cs.CC
Subjects: 03F20, 03C99, 68Q15
Related articles: Most relevant | Search more
arXiv:1311.2501 [math.LO] (Published 2013-11-11, updated 2014-08-22)
A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems
arXiv:1212.1789 [math.LO] (Published 2012-12-08, updated 2013-07-18)
On the computational complexity of finding hard tautologies
arXiv:1409.8635 [math.LO] (Published 2014-09-30)
Pseudofinite structures and simplicity

Links

Toolbox