Are there graph properties which produce complete problems for arbitrary PH classes? #10

jfinkels opened this Issue May 21, 2012 · 0 comments


None yet
1 participant

jfinkels commented May 21, 2012

npeqcompleteness.tex discusses C-complete properties for arbitrary structures. We have in mind graphs when proving things in this section. Do there exist graph properties which induce complete problems for arbitrary complexity classes in the polynomial hierarchy?

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