Cardinality of P
the.theorist
what about the cardinality of NP?
Are P (or NP) even considered sets in ZFC or 1st order Peano
Arithmetic?
If anyone out there has links (or names) to papers (or people) that
have worked on these questions it would be very helpful.
Kalle07
> Does anybody know what the cardinality of the set P is?
> what about the cardinality of NP?
am wrong.
P is the set of all languages that can be decided by a Turing machine
in polynomial time. The cardinality of that set is countable infinite,
or aleph 0, if you will. It is infinitely large, as the languages L_1
= {1}, L_2 = {2}, ... (i.e., the languages that consists of a single
number) are in P. It is countable infinite, as each of the languages
in P can be assigned a natural number (e.g., the smallest Goedel
number of a Turing machine that decides the language). The same holds
for NP, and any other complexity class that is defined by a runtime
complexity bound on Turing machines.
tc...@lsa.umich.edu
the.theorist <the.th...@gmail.com> wrote:
>Does anybody know what the cardinality of the set P is?
>what about the cardinality of NP?
As someone else explained, all the usual complexity classes are countable.
>Are P (or NP) even considered sets in ZFC or 1st order Peano
>Arithmetic?
P and NP are certainly considered sets in ZFC. In ZFC, strictly speaking,
all you can talk about are sets, so *everything* is a set.
As for first-order Peano arithmetic, it's worth pointing out that the term
"first-order Peano arithmetic" is not just a proper name for a particular
system---the word "first-order" actually means something. It means that
you can only talk directly about the natural numbers. In particular, you
can't talk about sets directly. Finite sets can be "faked" by identifying
them with natural numbers, but there is no general method for talking about
infinite sets.
On the other hand, it is possible to take a statement like "P = NP" which
ostensibly says that two infinite sets are equal and translate it into a
statement about finite sets, which can then be expressed in first-order
Peano arithmetic.
>If anyone out there has links (or names) to papers (or people) that
>have worked on these questions it would be very helpful.
The above facts are so basic that there are no names or papers associated
with them. You're best off learning some basic logic and set theory from a
class or from an introductory textbook. Then you'll be able to answer
questions like this yourself.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences