principleCritical
Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$?
Viewed 0 times
implymathsfthatdoes
Problem
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?
Solution
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.
Context
StackExchange Computer Science Q#7665, answer score: 78
Revisions (0)
No revisions yet.