Re: Cardinality of P
On 20 Aug., 00:18, "the.theorist" <the.theor...@xxxxxxxxx> wrote:
Does anybody know what the cardinality of the set P is?
what about the cardinality of NP?
I'll try to give an answer, and hope that others will point out if I
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.
.
Relevant Pages
- Re: Election 2008 for computer programmers
... their languages are recognised by finite state automata. ... nothing "after" a Turing machine: in fact, the book took pains to show ... The point is we need to understand politics at a higher level ...
(comp.programming) - Re: Election 2008 for computer programmers
... their languages are recognised by finite state automata. ... nothing "after" a Turing machine: in fact, the book took pains to show ... based on your higher and more recent knowledge to post correct ... You need to qualify it with the fact that you made it up. ...
(comp.programming) - Re: Election 2008 for computer programmers
... associated with the most expressive grammars. ... their languages are recognised by finite state automata. ... nothing "after" a Turing machine: in fact, the book took pains to show ... As to getting around to implementing Spinoza, ...
(comp.programming) - Re: Epistemology 201: The Science of Science
... that there are details of infinity that it does not capture. ... just because there is the same Cantorian cardinality. ... > Consider two idealized C like computer languages. ... > The above two programs are both legal C10 programs. ...
(sci.math) - Re: Epistemology 201: The Science of Science
... that there are details of infinity that it does not capture. ... just because there is the same Cantorian cardinality. ... > Consider two idealized C like computer languages. ... > The above two programs are both legal C10 programs. ...
(sci.cognitive) |
|
