# Complexity Classes as Pure Sets

What are complexity classes (P, NP, etc) in terms of pure sets? ZFC, I mean.

I thought they were just sets. Like

P = {problem q | there is a polynomial time algorithm for solving q}
NP = {problem q | there is a non-deterministic polynomial time algorithm for solving q}
NP-Hard = {problem q | any problem q' in NP can be reduced to q in polynomial time}
NP-Complete = NP (intersect) NP-Hard

etc.

I depends on how you define decision problem, Turing computation, etc. Take any book on computation theory, start with the definition of complexity classes given by AUMathTutor and work backwards by substituting each concept by its definition and eventually you should end up with an ugly expression for that set. Note however that the result is likely to vary depending on our definitions so there is no universal way to express such sets, and I expect that they will be fairly meaningless to humans.

I thought they were just sets. Like

P = {problem q | there is a polynomial time algorithm for solving q}

etc.

"problem q" would also have to be a set.

... since when can there not be sets of sets? Am I missing the point?

Are you asking for the definition of these sets in terms of elementary set theoretic notions? Like somebody said, doing that would be counterproductive. I think the way to bridge the gap from this to more basic notions is via the mechanism of language and machine.

CRGreathouse