Поли-временной надмножество NP-законченного языка с бесконечным числом исключенных из него строк

Для любого произвольного NP-полного языка всегда ли найдется надмножество множителей, дополнение которого также бесконечно?

На /cs//q/50123/42961 была запрошена тривиальная версия, в которой суперсет не должен иметь бесконечного дополнения.

Для целей этого вопроса можно предположить, что . Как объяснил Вор, если то ответ «Нет». (Если , то является NP-полным. Очевидно, что не существует надмножества которое является бесконечным и имеет бесконечное число дополнение, так как дополнение имеет только один элемент.) Таким образом, мы можем сосредоточиться на случае . $P \ne NP$ $P = NP$ $P = NP$ $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ $X$ $X$ $P \ne NP$

cc.complexity-theory np-complete structural-complexity ARi
источник

Если то является NP-полным. Ясно, что не существует надмножества которое является бесконечным и имеет бесконечное дополнение (обратите внимание, что ). Так что вы можете «сосредоточиться» на том, что произойдет, если .

P = N P

$P = NP$

X = {x ∣ x \in N^{+} \land x > 1}

$X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$

X

$X$

\bar{X} = {1}

$\bar{X} = \{1\}$

P \neq N P

$P \neq NP$

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

Как насчет релятивизированной версии: существует ли оракул й, все со-NP множества являются P -иммунными.

A

$A$

^{A}

$^A$

^{A}

$^A$

Ланс Фортноу

@LanceFortnow ... или для любого полного языка в конкретном. Класс сложности, всегда есть нетривиальный надмножество меньшей сложности.

ARi

Ответы:

Каждое -полное множество содержит бесконечное подмножество в предполагая, что $\mathsf{coNP}$ $\mathsf{P}$

существуют псевдослучайные генераторы и
существуют безопасные односторонние перестановки.

Другими словами, исходя из допущения , что эти две гипотезы верны, не -полных набор не является P- иммунной . Как указано в комментариях Ланса, это вытекает из теоремы 4.4 $\mathsf{coNP}$

Глассер, Паван, Сельман и Сенгупта, " Свойства NP-полных наборов ", SIAM J. Comput. 36 (2), 516–542.

(Каве уже показал, что ваш вопрос эквивалентен тому, содержит ли каждое -полное множество бесконечное подмножество. На другом языке это говорит о том, что ни один -полный набор не является " -иммунным". Это это язык, используемый в упомянутой выше теореме.) $\mathsf{coNP}$ $\mathsf{P}$ $\mathsf{coNP}$ $\mathsf{P}$

Джошуа Грохов
источник

Проект ECCC

Kaveh

Благодаря сильным жестким функциям (и итерации ) односторонние перестановки подразумевают псевдослучайные генераторы.

@RickyDemer: см. Определения 4.1-4.3 в цитируемой статье. Если я правильно понимаю, OWP подразумевают то, что они называют «крипто-PRG», но не обязательно то, что они называют «PRG» в газете Glasser-Pavan-Selman-Sengupta. Для их результата им (кажется) нужны как OWP, так и то, что они называют PRG.

Джошуа Грохов

Каве только показал, что эквивалентность ко-NP-полным множествам P-иммунна, но заключение теоремы 4.4 в Glasser и др. О том, что все NP-полные наборы должны иметь уменьшение длины, также подразумевает, что со-NP-полных наборов нет. полные P-иммунные наборы.

Ланс Фортноу

@JoshuaGrochow Спасибо ... но есть ли предположения, которые мы можем сделать, которые, в свою очередь, подразумевают отсутствие такого языка. Меня больше интересовали сценарии, в которых не существует надмножества поли-времени

ARi

Интересный вопрос. Заявление

для каждого NP-полного существует в P, такое что и бесконечно. $L$ $U$ $L \subseteq U$ $U^c$

эквивалентно:

для каждого NP-полного дополнение содержит бесконечное множество P. $L$ $L$

что в свою очередь эквивалентно

каждый coNP-полный набор содержит бесконечное P-множество.

~~который по симметрии такой же, как~~

~~каждый NP-полный набор содержит бесконечное P-множество.~~

Я не думаю, что ответ известен. Я думаю, что натуральные NP-комплекты легко удовлетворяют этому условию. Я не думаю, что у нас есть инструменты для создания искусственного набора, который не соответствует заявлению. (см. комментарий Ланса ниже)

Кава
источник

Ваше первоначальное утверждение тривиально верно. (Пусть U будет полный язык.)

Это интересная цепочка выводов ... Не могли бы вы привести пример естественного NP законченного языка в этом отношении

ARi

Симметрия не имеет смысла. Например, каждый набор ce имеет бесконечное вычислимое подмножество, но есть наборы ce, которые этого не делают.

Ланс Фортноу