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

• Autorzy: Sureson C.
• Języki publikacji: EN

Abstrakty

EN

Motivated by the analogy "(NP/Poly) ~ analytic'', we propose a co-analytic set W whose finite equivalent Wfinite 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 "Wfinite Ď 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 Wfinite.

Słowa kluczowe

EN

nondeterministic polynomial time; circuits; analytic sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 50, nr 1
• Strony: 77--110
• Opis fizyczny: bibliogr. tab., wykr., bibliogr. 6 poz.

Twórcy

autor

Sureson C.

• Equipe de Logique Mathématique, Université Paris 3, 2 Place Jussieu, 750005 Paris, France,