Est implique que?

20

Est-il possible que et la cardinalité de soit la même que la cardinalité de ? Ou signifie-t-il que et doivent avoir des cardinalités différentes?P≠NPPNPP≠NPPNP

complexity-classes p-vs-np Jason Baker
la source
il y a apparemment un sens dans lequel les langues plus complexes sont plus nombreuses que les langues moins complexes, mais il semble peu étudié. à la place, il y a par exemple les théorèmes de la hiérarchie de l'espace et du temps ....
vzn

Réponses:

70

On sait que P NP R, où R est l'ensemble des langages récursifs. Puisque R est dénombrable et P est infini (par exemple, les langues pour sont en P), nous obtenons que P et NP sont tous deux dénombrables.⊂ { n } n ∈ N⊆⊂{n}n∈N

Yuval Filmus
la source
Comment est défini R?
saadtaame
C'est l'ensemble de toutes les langues acceptées par les programmes C.
Yuval Filmus
7
Permettez-moi d'abord de corriger la définition: est l'ensemble de tous les langages acceptés par les programmes C qui s'arrêtent toujours . Nous n'avons pas besoin d'une définition plus formelle puisque les programmes C sont des chaînes sur un alphabet fini, et il n'y en a que beaucoup. La théorie de la récursivité est basée sur cette idée, que les programmes peuvent être spécifiés de manière finie (sous forme de nombres) et peuvent donc être introduits en entrée dans d'autres programmes. R
Yuval Filmus
1
Un produit dénombrable d'ensembles dénombrables n'est dénombrable que si tous, mais un nombre infini d'entre eux sont des singletons, ou si au moins l'un d'entre eux est vide. Je vous suggère de poser d'autres questions concernant la cardinalité sur math.stackexchange, où ils appartiennent.
Yuval Filmus
1
@ernab Un sous-ensemble d'un sous-ensemble dénombrable est fini ou dénombrable.
Yuval Filmus
1

Si vous êtes préoccupé par la taille de deux ensembles P et NP, la taille de ces deux ensembles est infinie et égale.

Si ces deux ensembles sont égaux, leur taille est également égale. S'ils ne sont pas égaux, puisqu'ils sont dénombrables, leur cardinalité est égale à la cardinalité des nombres naturels et égale.

Donc, dans les deux cas, leur cardinalité est égale.

orezvani
la source
3
Cantor a trouvé un moyen de comparer les magnitudes des ensembles infinis déjà au 19ème siècle.
Yuval Filmus
Alors, la cardinalité des nombres naturels est-elle plus grande que la cardinalité des nombres naturels pairs?
orezvani
1
Non, ils ont la même cardinalité. Vous pouvez consulter n'importe quel livre sur la théorie des ensembles (ou Wikipedia) pour les définitions requises. On dit que deux ensembles ont la même cardinalité s'il y a une bijection entre eux. Une série est dit avoir tout au plus la cardinalité de B en cas d'injection de A à B . En supposant l'axiome de choix, pour tous les deux ensembles A et B , A a au plus la cardinalité de B ou vice versa. On dit que A a une cardinalité plus petite que B si elle a au plus la cardinalité de BABABABABABBmais pas le même que cardinalité . B
Yuval Filmus
P et NP sont dénombrables, donc chaque élément a été mappé à un nombre naturel, n'est-ce pas?
orezvani
À droite, P et NP ont la même cardinalité que l'ensemble des nombres naturels.
Yuval Filmus
0

Je travaille principalement en mathématiques et je ne connais que peu ce type de problème. Cependant, la théorie des ensembles est l'un de mes domaines d'étude préférés, et cela semble être une question de théorie des ensembles.

Ainsi, pour commencer, P et NP sont infiniment infinis comme d'autres l'ont déjà souligné. Il n'est donc pas logique de discuter plus avant de la cardinalité de P et NP.

Cependant, en général:

L'inégalité des ensembles ne renseigne pas sur la taille d'un ensemble. Prenons par exemple et B = { 4 , 5 , 6 } . A ≠ B , mais | A | = | B | . Considérez également, C = { 1 , 2 , 3 } et D = { 4 , 5 } . C ≠A={1,2,3}B={4,5,6}A≠B|A|=|B|C={1,2,3}D={4,5} et | C | ≠ | D | .C≠D|C|≠|D|

Cependant, par définition, l'égalité des ensembles nous renseigne sur la cardinalité. Si , alors | A | = | B | . Considérons le cas de A = { 1 , 2 , 3 } et B = { 1 , 2 , 3 } . A = B et | A | = | B | .A=B|A|=|B|A={1,2,3}B={1,2,3}A=B|A|=|B|

Si deux ensembles sont infiniment dénombrables, alors ils partagent la même cardinalité. P et NP sont tous deux infiniment infinis, ce qui résume à peu près cela.

Yuval Filmus
la source
7
Re "P et NP sont infiniment infinis comme d'autres l'ont déjà souligné. Donc, il est logique de discuter de la cardinalité de P et NP.": Je ne suis pas d'accord. Parce qu'ils sont tous les deux infiniment dénombrables, il n'y a plus rien à dire sur leur cardinalité.
@DavidEppstein, en réfléchissant, vous avez raison. Je vais modifier ma réponse pour résoudre ce problème. Cependant, je laisserai une discussion sur la cardinalité en général (en mentionnant la cardinalité des ensembles infiniment dénombrables).
Les détails pertinents vous manque ici, en termes de l'exemple avec et B est que P ⊆ N P . ABP⊆NP
jmite