Analytic sets in Descriptive Set Theory and NP sets in Complexity Theory

Abstract

Motivated by the analogy ``(NP/Poly)∼analytic'', we propose a co-analytic set W whose finite equivalent W_finite is coNP-complete. The complement of W is in fact a variant of ``infinite clique''. A combinatorial proof of the non-analyticity of W is produced and studied in order to be (eventually) ``finitized'' into a probabilistic proof of ``W_finite ∉ NP/Poly (this would imply NP≠CoNP). A reasonable objective could be to determine a specific class of nondeterministic circuits which allow a finitization of the arguments of the infinite case, and thus which cannot compute W_finite.