Complexity Classes as Pure Sets

  • Thread starter Dragonfall
  • Start date
  • #1
1,030
4

Main Question or Discussion Point

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

Answers and Replies

  • #2
492
0
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.
 
  • #3
52
0
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.
 
  • #4
1,030
4
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.
 
  • #5
492
0
... 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.
 
  • #6
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 
  • #7
1,030
4
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.
 

Related Threads for: Complexity Classes as Pure Sets

Replies
9
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
2
Replies
33
Views
19K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
4
Views
2K
  • Poll
  • Last Post
2
Replies
47
Views
21K
Top