Is it possible that $\mathsf{P} \not = \mathsf{NP}$ and the cardinality of $\mathsf{P}$ is the same as the cardinality of $\mathsf{NP}$? Or does $\mathsf{P} \not = \mathsf{NP}$ mean that $\mathsf{P}$ and $\mathsf{NP}$ must have different cardinalities?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ there is apparently sense in which more complex languages are more numerous than less complex ones but it seems not to be studied much. instead, there is eg the space and time hierarchy theorems.... $\endgroup$– vznCommented Oct 24, 2013 at 17:07
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
9
It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P and NP are both countable.
answered Dec 31, 2012 at 17:58
-
-
$\begingroup$ It is the set of all languages accepted by C programs. $\endgroup$ Commented Feb 7, 2014 at 15:30
-
9$\begingroup$ Let me first correct the definition: $R$ is the set of all languages accepted by C programs that always halt. We don't need a more formal definition since C programs are strings over a finite alphabet, and there are only countably many of these. Recursion theory is based on this insight, that programs can be specified finitely (as numbers) and so can be fed as input to other programs. $\endgroup$ Commented Feb 7, 2014 at 21:27
-
1$\begingroup$ A countable product of countable sets is only countable if all but finitely many of them are singletons, or if at least one of them is empty. I suggest you ask further questions regarding cardinality on math.stackexchange, where they belong. $\endgroup$ Commented Feb 8, 2014 at 4:41
-
2$\begingroup$ @ernab A subset of a countable subset is either finite or countable. $\endgroup$ Commented Apr 9, 2014 at 2:21
$\begingroup$
$\endgroup$
7
If you are concerned about the size of two sets P and NP, the size of both these sets is infinite and equal.
If these two sets are equal, then their size is equal as well. If they are not equal, since they are countable then their cardinality is equal to the cardinality of natural numbers and equal.
So, in either case, their cardinality is equal.
-
3$\begingroup$ Cantor came up with a way of comparing the magnitudes of infinite sets already in the 19th century. $\endgroup$ Commented Apr 9, 2014 at 2:22
-
$\begingroup$ So, is the cardinality of Natural numbers larger than the cardinality of even natural numbers? $\endgroup$– orezvaniCommented Apr 9, 2014 at 2:39
-
1$\begingroup$ No, they have the same cardinality. You can check any book on set theory (or Wikipedia) for the required definitions. Two sets are said to have the same cardinality if there is a bijection between them. A set $A$ is said to have at most the cardinality of $B$ if there is an injection from $A$ to $B$. Assuming the axiom of choice, for every two sets $A$ and $B$, either $A$ has at most the cardinality of $B$ or vice versa. We say that $A$ has cardinality smaller than $B$ if it has at most the cardinality of $B$ but not the same cardinality as $B$. $\endgroup$ Commented Apr 9, 2014 at 2:44
-
$\begingroup$ P and NP are countable, so every element have been maped to a natural number, is this right? $\endgroup$– orezvaniCommented Apr 9, 2014 at 2:48
-
$\begingroup$ Right, P and NP have the same cardinality as the set of natural numbers. $\endgroup$ Commented Apr 9, 2014 at 2:48
$\begingroup$
$\endgroup$
3
I work in mathematics mainly and have only a bit of familiarity with this type of problem. However, set theory is one of my favorite areas of study, and this seems to be a set theory question.
So, to begin with, both P and NP are countably infinite as others have pointed out before. So, it does not make sense to discuss the cardinality of P and NP any further.
However, in general:
Set inequality does not inform one about the size of a set. Take for instance, $A=\{1,2,3\}$ and $B=\{4,5,6\}$. $A\neq B$, but $|A|=|B|$. Consider also, $C=\{1,2,3\}$ and $D=\{4,5\}$. $C\neq D$, and $|C|\neq|D|$.
However, by definition, set equality does inform us about cardinality. If $A=B$, then $|A|=|B|$. Consider the case of $A=\{1,2,3\}$ and $B=\{1,2,3\}$. $A=B$, and $|A|=|B|$.
If two sets are countably infinite, then they share the same cardinality. P and NP are both countably infinite, so that pretty much sums that up.
-
7$\begingroup$ Re "both P and NP are countably infinite as others have pointed out before. So, it does make sense to discuss the cardinality of P and NP.": I disagree. Because they are both countably infinite, there is nothing more to say about their cardinality. $\endgroup$– David EppsteinCommented Dec 31, 2012 at 20:59
-
$\begingroup$ @DavidEppstein, upon thinking, you are correct. I will edit my answer to fix that. However, I will leave some discussion on cardinality in general (mentioning the cardinality of countably infinite sets). $\endgroup$– Travis FieldsCommented Dec 31, 2012 at 22:10
-
$\begingroup$ The relevant detail you're missing here, in terms of the example with $A$ and $B$ is that $P \subseteq NP$. $\endgroup$ Commented Mar 21, 2013 at 5:02