- #1

- 1,030

- 4

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

- Thread starter Dragonfall
- Start date

- #1

- 1,030

- 4

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

- #2

- 492

- 0

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

- #4

- 1,030

- 4

"problem q" would also have to be a set.I thought they were just sets. Like

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

etc.

- #5

- 492

- 0

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

- #7

- 1,030

- 4

- Last Post

- Replies
- 5

- Views
- 3K

- Replies
- 18

- Views
- 3K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 33

- Views
- 20K

- Last Post

- Replies
- 7

- Views
- 3K

- Replies
- 47

- Views
- 21K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 946

- Last Post

- Replies
- 9

- Views
- 3K

- Last Post

- Replies
- 9

- Views
- 3K