
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.
Complexity of computation (including implicit computational complexity), co-analytic set, Kleene hierarchy, nondeterministic polynomial time, circuits, Complexity classes (hierarchies, relations among complexity classes, etc.), Descriptive set theory, analytic sets
Complexity of computation (including implicit computational complexity), co-analytic set, Kleene hierarchy, nondeterministic polynomial time, circuits, Complexity classes (hierarchies, relations among complexity classes, etc.), Descriptive set theory, analytic sets
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
