Мы говорим, что язык является плотным, если существует такой многочлен , что для всехДругими словами, для любой заданной длины существует только многочлен много слов длины , которых нет в| J c ∩ Σ n | ≤ р ( п ) п ∈ N . п п J .
Проблема, которую я сейчас изучаю, требует показать следующее
Если существует плотный полный язык, тоП = Н П
Что текст указывают на то , чтобы рассмотреть полиномиальное сведение к - , а затем построить алгоритм , который пытается удовлетворить данную формулу , а также порождающих элементов вS A T C N F J c .
Что мне интересно, так это
Есть ли более прямое доказательство? Известно ли это понятие в более общем контексте?
Ответы:
Это хорошая домашняя задача о теореме Махани.
Обратите внимание, что дополнение к «плотному» языку является разреженным языком. Более того, если язык является -полным, его дополнение является .c O N PН П c o N P
Если существует "плотный" -полный язык, существует разреженный язык.c O N PН П coNP
Теорема Махани говорит нам, что нет редкого -комплектного языка, если только .П = Н ПNP P=NP
Мы можем принять доказательство, чтобы показать, что нет редкого языка, если только который эквивалентен (так как замкнуто относительно дополнений).coNP P=coNP P=NP P
Таким образом, ответ будет отрицательным, если только . Обратите внимание, что если то каждый нетривиальный язык является -полным.P=NP P=NP NP
ps: Вы можете попробовать следующее, а затем использовать теорему Махани: существует разреженный -комплектный набор, если существует разреженный набор. Однако я сомневаюсь, что доказательство этого утверждения будет намного проще, чем доказательство теоремы Махани.NP coNP
источник
Упомянутый проект содержит полное доказательство.
источник