12
$\begingroup$

Inspired by Joshua Grochow and Iddo Tzameret's answers in a post on http://cstheory.stackexchange.com , I would like to get more references on possible connections between complexity theory and set theory here in this post. My question simply is:

What are examples of those points where set theoretical axioms, concepts and tools like large cardinals and forcing appear in the complexity theory?

As a matter of fact note that the statement $\mathsf P=\mathsf{NP}$ (and other similar assertions) remains unaffected by most set theoretic methods and assumptions. So this may help you restrict the searching domain for finding possible connections between set theory and complexity theory through excluding straightforward independence results.

$\endgroup$
1
  • $\begingroup$ Not sure about how things work here! Should such open-ended questions be community Wiki?! $\endgroup$ Oct 24, 2016 at 11:34

2 Answers 2

16
$\begingroup$

See Diagonalizations over polynomial time computable sets in which two types of genericity introduced with which it examines complexity properties provable by simple diagonalizations over $P$.

See also An oracle builder's toolkit. The paper shows how various notions of genericity can be used to overcome difficulties arising out of interactions between coding and diagonalization techniques in oracle constructions. After an abstract definition of genericity in a general setting and a discussion of relativized genericity and some technical remarks for specialists, Cohen generics and forcing with finite functions are considered. General techniques to obtain results about Cohen generics are illustrated for some previously known oracle constructions, for example, for the existence of an oracle relative to which the isomorphism conjecture fails, but relative to which there are no one-way functions. To include requirements that can only be met by infinite extensions, the notion of SP-genericity (symmetric perfect genericity) is introduced.

Also the book Forcing with Random Variables and Proof Complexity is related and very useful. Here is the mathscinet review of the book:

A fundamental problem related to the NP versus co-NP question is to provide super-polynomial lower bounds on a given proposition proof system. This is equivalent to constructing certain extensions of models of bounded arithmetic. Jan Krajíček is the leading expert on these problems and in this book he provides a new approach to building models of bounded arithmetic which combines methods and techniques from model theory, forcing and computational complexity. This novel approach includes building models from random variables defined on a sample space, which is a non-standard finite set sampled by functions of some computational complexity. Personally, I find Krajíček's approach a highly stimulating collage of ideas. I recommend the book strongly to anyone interested in logical approaches to fundamental problems in complexity theory.

-- Let me add more references:

Analytic sets in descriptive set theory and NP sets in complexity theory.

Abstract. The sets in the complexity class NP are definable by existentially quantifying (with a polynomial bound on lengths) polynomial-time computable binary relations. In descriptive set theory, analytic sets are definable by existentially quantifying Borel relations. This analogy between NP and analytic sets suggests that one might be able to solve problems in complexity theory by adapting the methods of descriptive set theory. Toward this goal, the author introduces a closely related pair of sets—W a set of infinite graphs and Wfin a set of finite graphs. Each consists of the graphs that do not admit cliques of a certain sort. The author shows that W is a complete coanalytic set and Wfin is a complete coNP set. It follows, by the hierarchy theorem of descriptive set theory, that W is not analytic, but this proof, by diagonalization, does not carry over to the finite case. The author therefore gives an elegant alternative proof that W is not analytic, by a combinatorial method that avoids diagonalization. One can hope that this proof can be adapted to the finite case, to prove that Wfin is not in NP. Of course, a proof of this would imply that NP is not closed under complementation and, in particular, P≠NP. So it is not surprising that the hoped-for finitization of the proof is not achieved. Nevertheless, the author obtains some results in this direction, producing a probabilistic conjecture which, if proved, would complete the argument, proving that Wfin is not in NP and not even in the non-uniform complexity class NP/Poly. The paper ends with a discussion of some variants of W and Wfin.

Descriptive set theory and Boolean complexity theory

Abstract. We propose a co-analytic subset whose finite equivient is co-NP-complete, and we study how a combinatorial proof of its non analyticity may lead to a proof of: "(non-uniform) NP ≠ (non-uniform)Co-NP"

$\endgroup$
1
  • $\begingroup$ Really informative answer! Thank you, Mohammad! :-) $\endgroup$ Oct 24, 2016 at 4:06
6
$\begingroup$

As far as I'm aware, large cardinals have not found any application in complexity theory. The main concepts from set theory that have found some application in complexity theory are forcing and generic filters. In addition to the references mentioned by Mohammad Golshani, there is also the earlier book by Krajíček, Bounded Arithmetic, Propositional Logic and Complexity Theory, as well as Gaisi Takeuti's papers, e.g., Forcing on bounded arithmetic (with Yasumoto).

It is not clear, however, how useful these connections are for addressing the fundamental questions in complexity theory. In this MO question I raised this question and learned that there are some serious obstacles to using forcing to construct models of arithmetic that satisfy (or refute) arithmetic sentences of interest.

In a different direction, Joel Friedman has attempted to phrase certain problems about circuit lower bounds in the language of sheaves on a Grothendieck topology. I don't know if this counts as "set theory" in your book, but if you're interested, I commented briefly on Friedman's work at cstheory.stackexchange.com.

$\endgroup$
1
  • $\begingroup$ (+1) Many thanks for the useful references, Timothy! :-) $\endgroup$ Oct 24, 2016 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.