Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
77--110
Opis fizyczny
bibliogr. tab., wykr., bibliogr. 6 poz.
Twórcy
autor
- Equipe de Logique Mathématique, Université Paris 3, 2 Place Jussieu, 750005 Paris, France, sureson@logique.jussieu.fr
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0004-0005