Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: nondeterministic polynomial time

Sortuj według:

Ogranicz wyniki do:

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

Sureson C.

Fundamenta Informaticae

2002

Vol. 50, nr 1

77-110

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.