Expansions of pseudofinite structures and circuit and proof complexity

zbMATH Open1418.03170arXiv1505.00118MaRDI QIDQ5224696

Jan Krajíček

Publication date: 24 July 2019

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.

Full work available at URL: https://arxiv.org/abs/1505.00118

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonstandard models of arithmetic (03H15) Complexity of proofs (03F20)

Related Items (2)

Directed free pseudospaces ⋮ Title not available (Why is that?)

This page was built for publication: Expansions of pseudofinite structures and circuit and proof complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224696)