Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from cstheory.stackexchange.com Jan 1 '13 at 2:19

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

    
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

3 Answers 3

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.

share|improve this answer
    
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
1  
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
1  
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. –  Yuval Filmus Feb 8 at 4:41
1  
@ernab A subset of a countable subset is either finite or countable. –  Yuval Filmus Apr 9 at 2:21

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.

share|improve this answer
2  
Cantor came up with a way of comparing the magnitudes of infinite sets already in the 19th century. –  Yuval Filmus Apr 9 at 2:22
    
So, is the cardinality of Natural numbers larger than the cardinality of even natural numbers? –  emab Apr 9 at 2:39
    
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$. –  Yuval Filmus Apr 9 at 2:44
    
P and NP are countable, so every element have been maped to a natural number, is this right? –  emab Apr 9 at 2:48
    
Right, P and NP have the same cardinality as the set of natural numbers. –  Yuval Filmus Apr 9 at 2:48

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.

share|improve this answer
7  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.