Плотный NP полный язык подразумевает P = NP

16

Мы говорим, что язык является плотным, если существует такой многочлен , что для всехДругими словами, для любой заданной длины существует только многочлен много слов длины , которых нет вJΣ*| J cΣ n | р ( п ) п N . п п J .п

|JсΣN|п(N)
NN,NNJ,

Проблема, которую я сейчас изучаю, требует показать следующее

Если существует плотный полный язык, тоП = Н ПNппзнак равноNп

Что текст указывают на то , чтобы рассмотреть полиномиальное сведение к - , а затем построить алгоритм , который пытается удовлетворить данную формулу , а также порождающих элементов вS A T C N F J c .3SATСNFJс,

Что мне интересно, так это

Есть ли более прямое доказательство? Известно ли это понятие в более общем контексте?

Jernej
источник
1
Существует родственное понятие разреженных языков, в котором условие является прямо противоположным: |JΣN|п(N) .
Юваль Фильмус
2
Проверьте теорему Махани .
Пол GD
2
@ PålGD Превратиться в ответ? (при условии, что аргумент переносится на плотные языки)
Yuval Filmus

Ответы:

6

Это хорошая домашняя задача о теореме Махани.

Обратите внимание, что дополнение к «плотному» языку является разреженным языком. Более того, если язык является -полным, его дополнение является .c O N PNпсоNп

Если существует "плотный" -полный язык, существует разреженный язык.c O N PNп coNP

Теорема Махани говорит нам, что нет редкого -комплектного языка, если только .П = Н ПNPP=NP

Мы можем принять доказательство, чтобы показать, что нет редкого языка, если только который эквивалентен (так как замкнуто относительно дополнений).coNPP=coNPP=NPP

Таким образом, ответ будет отрицательным, если только . Обратите внимание, что если то каждый нетривиальный язык является -полным.P=NPP=NPNP

ps: Вы можете попробовать следующее, а затем использовать теорему Махани: существует разреженный -комплектный набор, если существует разреженный набор. Однако я сомневаюсь, что доказательство этого утверждения будет намного проще, чем доказательство теоремы Махани.NPcoNP

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

NPHardP=NP

Упомянутый проект содержит полное доказательство.

Реза
источник
1
Это не дает больше, чем комментарий (который даже не ваш). Пожалуйста, уточните, чтобы сделать правильный ответ из этого поста.
Рафаэль
@ Рафаэль: Это правильный ответ. Вы проверили ссылку?
Цуёси Ито
5
@TsuyoshiIto: ответы, состоящие только из ссылки, обычно считаются плохими на SE; см здесь .
Рафаэль
@ Рафаэль: Ответ на вопрос был решен ранее в литературе. Ссылка содержит полное доказательство (а это 6 страниц). Я думаю, если бы у него было больше вопросов, мы могли бы продолжить обсуждение.
Реза
@ Рафаэль: Глупо. Ссылка лучше, чем ничего. Если хотите, разработайте ответ самостоятельно, а не обвиняйте пользователя в размещении полезной ссылки.
Цуёси Ито