Могу ли я ограничить мощность набора, если известно, что тестирование на членство в нем является NP-полным?

Я хотел бы ограничить мощность множества графов единичных дисков с $N$ Вершины. Известно, что проверка того, является ли граф членом этого набора, является NP-сложной задачей. Приводит ли это к какой-либо нижней границе мощности, предполагая, что P $\neq$ NP?

Например, предположим, что есть порядок на всех графах с $N$ Вершины. Если бы NP-твердость означала, что количество элементов превышает $2^N$ иначе вы могли бы проверить на членство за полиномиальное время, выполнив бинарный поиск по множеству? Я думаю, это предполагает, что вы как-то сохранили набор в памяти ... Это разрешено?

Определение: граф является графом единичного диска, если каждая вершина может быть связана с единичным диском на плоскости, так что вершины соединяются всякий раз, когда их диски пересекаются.

Вот ссылка на NP-сложность тестирования членства для графов единичных дисков: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

cc.complexity-theory graph-theory Дэвид Чой
источник

Мне интересно, есть ли пример, где этот метод обеспечивает наиболее известную нижнюю границу размера некоторого набора? Это было бы классным косвенным комбинаторным применением теории сложности.

Сашо Николов

Спасибо Вам за Вашу помощь. Оба ответа были полезны и проницательны; Я бы принял одно из них в отсутствие другого.

Дэвид Чой

Ответы:

Я не уверен, задаете ли вы этот вопрос для техники или для ответа, но есть недавняя статья Макдиармида и Мюллера, где они показывают количество (помеченных) графиков единичных дисков на $n$ вершины $2^{(2 + o(1))n}$ ; см. http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf .

Барт Янсен
источник

Теорема Махани утверждает, что разреженные NP-полные множества существуют тогда и только тогда, когда P = NP. Поэтому, предполагая, $P \neq NP$ подразумевает суперполиномиальную нижнюю границу количества экземпляров размера $n$ в $NP$ множества для бесконечно многих $n$ , То есть если $P \neq NP$ тогда любой $NP$ -полный набор должен иметь некоторые $\epsilon \gt 0$ такой, что для бесконечно многих целых $n\ge 0$ набор содержит хотя бы $2^{n^{\epsilon}}$ строки длины $n$ ,

Х. Берман и Дж. М. Хичкок доказали нижнюю границу ( $2^{n^{\epsilon}}$ ), если полиномиальная иерархия не разрушится.

[1] Х. Берман и Дж. М. Хичкок, NP-жесткие множества являются экспоненциально плотными, если только coNP ⊆ NP / poly, на конференции IEEE по вычислительной сложности, стр. 1–7, 2008

[2] Эрик Аллендер, Отчет о состоянии вопроса P против NP, Advances in Computers, том 77, 2009, страницы 117-147.

Мухаммед Аль-Туркистани
источник

[Mah82] SR Mahaney. Редкие полные наборы для NP: Решение гипотезы Бермана и Хартманиса , Journal of Computer and System Sciences 25: 130-143, 1982 г.

Марцио Де Биаси

Каждый NP-комплект имеет бесконечно большую бесконечность. Вы, вероятно, имели в виду, что P ≠ NP подразумевает суперполиномиальную нижнюю границу для числа экземпляров размера

n

$n$ , для бесконечно многих

n

$n$ , Обратите внимание, что

2^{(\log n)^{2}}

$2^{(\log n)^2}$ является супер-полиномом, но не имеет той формы, которую вы даете.

Андрас Саламон

Спасибо András, ваш комментарий включен в ответ.

Мухаммед Аль-Туркистани

@ Мохаммед: сделайте нижнюю границу

2^{ω (\log n)}

$2^{\omega(\log n)}$ , или

n^{ω (1)}

$n^{\omega(1)}$ это то, что означает суперполином.

Сашо Николов

@Sasho, H. Buhrman и JM Hitchcock доказали нижнюю оценку (

2^{n^{ϵ}}

$2^{n^{\epsilon}}$ ) Я упомянул в своем ответе, если полиномиальная иерархия не рухнет. Х. Берман и Дж. М. Хичкок, NP-сложные наборы экспоненциально плотны, если только coNP ⊆ NP / poly, на конференции IEEE по вычислительной сложности, стр. 1–7, 2008

Мохаммед Аль-Туркистани,