If there exists a kernel-complete problem, must that class be closed under complement? #6

Open
jfinkels opened this Issue May 21, 2012 · 0 comments

Comments

Projects
None yet
1 participant
Owner

jfinkels commented May 21, 2012

If there exists a kernel-complete equivalence relation for a complexity class, must that class be closed under complement? Under polynomially-bounded universal quantification? Both?

This is the converse of thm:generalcompleteness in generalcompleteness.tex.

The next question would be this: if there is a kernel-complete equivalence relation for NPEq, does NP equal coNP?

This problem was suggested by Josh.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment