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

Article type: Research Article

Authors: Sureson, Claude

Affiliations: Equipe de Logique Mathématique, Université PARIS 7, 2 Place Jussieu, 75005 Paris, France

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.

Keywords: Nondeterministic polynomial time, circuits, analytic sets

Journal: Fundamenta Informaticae, vol. 50, no. 1, pp. 77-110, 2002