Expansions of pseudofinite structures and circuit and proof complexity
classification
🧮 math.LO
cs.CC
keywords
complexitycomputationalexpansionspseudofinitestructuresassumingcircuitclass
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.