Complexity Classes as Pure Sets

[Dragonfall]

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

 

[AUMathTutor]

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.

 

[gunch]

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.

 

[Dragonfall]

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.

 

[AUMathTutor]

... 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]

It's pretty trivial to define them as sets if they're decision problems: just code output in binary for inputs "", "0", "1", "00", "01", "10", "11", "000", ... If they're functions, just code numbers (in a self-delimiting format) rather than bits. Take the resultant binary string and code as the set of the set bits' usual set representations: 1 = {{}}, 2 = {{}, {{}}}, etc.

 

[Dragonfall]

Set as decision problems don't account for complexity. I guess you'd have to define some sort of complexity measure, and the measure would have to depend on the turing machine or whatever formality used. Then define some sort of equivalent class. My head hurts just thinking about it.