Означает ли

20

Возможно ли, что и мощность совпадает с мощностью ? Или означает, что и должны иметь разные мощности?PNPPNPPNPPNP

Джейсон Бейкер
источник
очевидно, в каком-то смысле более сложные языки более многочисленны, чем менее сложные, но, похоже, они мало изучены. вместо этого есть, например, теоремы иерархии пространства и времени ....
vzn

Ответы:

70

Известно, что P NP R, где R - множество рекурсивных языков. Поскольку R счетно, а P бесконечно (например, языки { n } для n N находятся в P), мы получаем, что P и NP оба счетны.{n}nN

Юваль Фильмус
источник
Как определяется R?
saadtaame
Это набор всех языков, принимаемых программами на Си.
Юваль Фильмус
7
Позвольте мне сначала исправить определение: - это набор всех языков, принятых C-программами, которые всегда останавливаются . Нам не нужно более формальное определение, так как программы на C - это строки над конечным алфавитом, и их только счетное количество. Теория рекурсии основана на этом понимании, что программы могут быть определены конечным образом (в виде чисел) и, следовательно, могут быть использованы в качестве входных данных для других программ. R
Юваль Фильмус
1
Счетное произведение счетных множеств является счетным только в том случае, если все, кроме конечного числа из них, являются синглетонами или хотя бы один из них пуст. Я предлагаю вам задать дополнительные вопросы о количестве элементов на math.stackexchange, где они находятся.
Юваль Фильмус
1
@ernab Подмножество счетного подмножества является либо конечным, либо счетным.
Юваль Фильмус
1

Если вас беспокоит размер двух наборов P и NP, размер обоих этих наборов бесконечен и равен.

Если эти два набора равны, то их размер также равен. Если они не равны, так как они счетны, то их мощность равна количеству натуральных чисел и равна.

Так что, в любом случае, их мощность равна.

orezvani
источник
3
Кантор придумал способ сравнения величин бесконечных множеств еще в 19 веке.
Юваль Фильмус
Итак, больше ли количество натуральных чисел, чем количество натуральных чисел?
орезвани
1
Нет, они имеют одинаковую мощность. Вы можете проверить любую книгу по теории множеств (или Wikipedia) для необходимых определений. Говорят, что два набора имеют одинаковую мощность, если между ними существует биекция. Набор , как говорят, в большинстве мощность B , если существует инъекция от A до B . Предполагая аксиому выбора, для каждых двух множеств A и B либо A имеет максимальную мощность B, либо наоборот. Мы говорим, что A имеет мощность меньше, чем B, если она имеет мощность не более BABABABABABBно не такой же , как мощность . B
Юваль Фильмус
P и NP являются счетными, поэтому каждый элемент сопоставлен с натуральным числом, верно?
орезвани
Правильно, P и NP имеют ту же мощность, что и набор натуральных чисел.
Юваль Фильмус
0

Я работаю в основном по математике и немного знаком с этой проблемой. Тем не менее, теория множеств является одной из моих любимых областей исследования, и это, кажется, вопрос теории множеств.

Итак, для начала, как P, так и NP бесконечно бесконечны, как уже указывали другие. Таким образом, нет смысла обсуждать мощность P и NP дальше.

Однако в целом:

Неравенство множества не информирует о размере множества. Например, и B = { 4 , 5 , 6 } . A B , но | A | = | Б | , Рассмотрим также, C = { 1 , 2 , 3 } и D = { 4 , 5 } . C A={1,2,3}B={4,5,6}AB|A|=|B|C={1,2,3}D={4,5} и | C | | D | ,CD|C||D|

Однако, по определению, равенство множеств информирует нас о количестве элементов. Если , то | A | = | Б | , Рассмотрим случай A = { 1 , 2 , 3 } и B = { 1 , 2 , 3 } . A = B и | A | = | Б | ,A=B|A|=|B|A={1,2,3}B={1,2,3}A=B|A|=|B|

Если два набора счетно бесконечны, то они имеют одинаковую мощность. P и NP оба счетно бесконечны, так что в значительной степени это подводит итог.

Юваль Фильмус
источник
7
«Как P, так и NP бесконечно бесконечны, как уже указывали другие. Поэтому имеет смысл обсуждать количество элементов P и NP». Я не согласен. Поскольку они оба бесконечно бесконечны, больше нечего сказать об их мощности.
@DavidEppstein, подумав, ты прав. Я отредактирую свой ответ, чтобы исправить это. Тем не менее, я оставлю некоторую дискуссию о кардинальности в целом (упоминая кардинальность счетно бесконечных множеств).
Соответствующая деталь вы здесь отсутствует, с точки зрения , например , с и B , что P N P . ABPNP
Jmite