Expansions of pseudoinfinite structures and circuit and proof complexity

MaRDI QIDQ5224696zbMATH OpenFDO

Authors Jan Krajíček

Publication date 24 July 2019

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) Complexity of proofs (03F20) Nonstandard models of arithmetic (03H15)

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.

Recommendations

• P versus NP and computability theoretic constructions in complexity theory over algebraic structures
• On relativizations of the P =? NP question for several structures
• Logical Approaches to Computational Barriers
• Combinatorics of first order structures and propositional proof systems
• A model-theoretic proof for P ≠ NP over all infinite abelian group

Cited in

(3)

• Directed free pseudospaces
• scientific article; zbMATH DE number 5295822 (Why is no real title available?)
• scientific article; zbMATH DE number 1086678 (Why is no real title available?)

This page was built for publication: Expansions of pseudoinfinite 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)