|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 5 gevonden artikelen
| Titel: |
Analytic sets in Descriptive Set Theory and NP sets in Complexity Theory |
| Auteur: |
Sureson, Claude |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 50 (2003) nr. 1 pagina's 77-110 |
| Jaar: |
2003-07-11 |
| Inhoud: |
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 “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 Wfinite. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 5 gevonden artikelen
| << vorige | volgende >> |