Complexity Classes as Pure Sets

Click For Summary

Discussion Overview

The discussion revolves around the definition of complexity classes (such as P, NP, NP-Hard, and NP-Complete) in the context of pure set theory, specifically within Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC). Participants explore the implications of defining these classes as sets and the challenges associated with such definitions.

Discussion Character

  • Exploratory
  • Debate/contested
  • Technical explanation

Main Points Raised

  • Some participants propose that complexity classes can be defined as sets, providing specific formulations for P, NP, NP-Hard, and NP-Complete based on the existence of algorithms.
  • Others argue that the definition of complexity classes depends heavily on the foundational definitions of decision problems and Turing computation, suggesting that any attempt to express these classes in set-theoretic terms may lead to complex and potentially meaningless expressions.
  • A participant questions the notion of sets of sets and suggests that defining these classes in elementary set-theoretic terms might be counterproductive, advocating for a connection through language and machine mechanisms instead.
  • One participant mentions that defining complexity classes as sets of decision problems could be straightforward if the outputs are coded in binary, but this approach may overlook the complexities involved.
  • Another participant highlights the need for a complexity measure that would depend on the formalism used, indicating that defining equivalent classes could be a challenging task.

Areas of Agreement / Disagreement

Participants express differing views on the feasibility and utility of defining complexity classes as pure sets. There is no consensus on a single approach, and the discussion remains unresolved regarding the best way to conceptualize these classes within set theory.

Contextual Notes

Participants note that the definitions of decision problems and complexity measures are crucial and that variations in these definitions could lead to different interpretations of complexity classes. The discussion highlights the potential limitations of set-theoretic definitions in capturing the nuances of computational complexity.

Dragonfall
Messages
1,023
Reaction score
5
What are complexity classes (P, NP, etc) in terms of pure sets? ZFC, I mean.
 
Physics news on Phys.org
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.
 

Similar threads

Graduate Maybe it is not necessary to define set membership?
  • · Replies 13 ·
Replies
13
Views
2K
High School Is There an Alternative Approach to Learning Pure Math for Beginners?
  • · Replies 3 ·
Replies
3
Views
3K
Graduate An additional constraint to the ZFC axioms?
  • · Replies 40 ·
2
Replies
40
Views
5K
Graduate Looking for book on ZFC axiomatic set theory (I think)
  • · Replies 12 ·
Replies
12
Views
3K
Graduate Application of sets with higher cardinality
  • · Replies 7 ·
Replies
7
Views
3K
Graduate Is there a decidable set theory?
  • · Replies 5 ·
Replies
5
Views
2K
Check my P=NP proof for errors (based on incompleteness of ZFC)
  • · Replies 2 ·
Replies
2
Views
2K
High School Are proofs needed for definitions? Conditional probabilities
  • · Replies 4 ·
Replies
4
Views
2K
MHB What are the key differences between a set and a class?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Defining the membership relation in set theory?
  • · Replies 14 ·
Replies
14
Views
6K