Expansions of pseudoinfinite structures and circuit and proof complexity

zbMATH Open1418.03170arXiv1505.00118MaRDI QIDQ5224696FDOQ5224696

Authors: 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

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

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)

Cited In (3)

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

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)