# Complexity Classes as Pure Sets

• Dragonfall
In summary, complexity classes such as P, NP, NP-Hard, and NP-Complete are sets that represent different types of decision problems in terms of polynomial time algorithms and non-deterministic polynomial time algorithms. However, defining these sets in terms of basic set theory is not practical and it is more effective to use language and machine mechanisms. Additionally, these sets do not account for complexity and a specific complexity measure must be defined in order to determine equivalent classes.

#### Dragonfall

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.

AUMathTutor said:
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.

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.

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.