# Does P != NP imply that | NP | > | P |?

Is it possible that P != NP and the cardinality of P is the same as the cardinality of NP? Or does P != NP mean that P and NP must have different cardinalities?

-
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.... –  vzn Oct 24 '13 at 17:07

## migrated from cstheory.stackexchange.comJan 1 '13 at 2:19

This question came from our site for theoretical computer scientists and researchers in related fields.

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.

-
How is R defined? –  saadtaame Feb 7 at 15:14
It is the set of all languages accepted by C programs. –  Yuval Filmus Feb 7 at 15:30
How do you show that it's countable? A more formal definition is needed I guess. –  saadtaame Feb 7 at 20:30
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. –  Yuval Filmus Feb 7 at 21:27
Is this a theorem that says: a countable product of countable (finite in this case) sets is countable? –  saadtaame Feb 8 at 0:31
show 1 more comment

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.

-
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. –  David Eppstein Dec 31 '12 at 20:59
@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). –  Travis Fields Dec 31 '12 at 22:10
The relevant detail you're missing here, in terms of the example with $A$ and $B$ is that $P \subseteq NP$. –  jmite Mar 21 '13 at 5:02