- #1

- 1,030

- 4

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- 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

- 494

- 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

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

- 494

- 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,824

- 0

- #7

- 1,030

- 4

Share: