«Почти легкие» NP-полные задачи

20

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

Другими словами, существует P , такое, что обращается в нуль, что означает Это также означает, что на равномерном случайном входе алгоритм Polytime для A даст правильный ответ для L с вероятностью, приближающейся к 1. Следовательно, имеет смысл просматривать L почти легко.A LΔA

limn|(LΔA){0,1}n|2n=0.
ALL

Обратите внимание, что LΔA не должно быть разреженным. Например, если он имеет 2n/2 n битных строк, то он все еще исчезает (с экспоненциальной скоростью), поскольку 2n/2/2n=2n/2 .

В соответствии с приведенным выше определением несложно (искусственно) построить NP- полные задачи, которые являются P- плотно-близкими. Например, пусть L будет любым NP- полным языком и определим L2={xx|xL} . Тогда L2 сохраняет NP- полноту, но имеет не более 2n/2 n битных да-экземпляров. Следовательно, тривиальный алгоритм, который отвечает «нет» на каждый вход, будет правильно определять L2 почти на всех входах; он будет ошибаться только в 12n/2 части n битных входов.

С другой стороны, было бы очень удивительно, если бы все NP- полные проблемы были P- плотно-близкими. Это означало бы, что в некотором смысле все NP- неполные проблемы почти легки. Это мотивирует вопрос:

Предполагая P NP , какие естественные NP- полные проблемы не являются P- плотно-близкими?

Андрас Фараго
источник
3
Поскольку Heuristica не исключается, нет даже не-обязательно-естественная задача , для которых P ≠ NP , как известно, означает , что эта проблема не является почти в Р.
1
Я считаю, что проблемы с почтовой корреспонденцией - это хорошая проблема кандидата. Это трудно даже для равномерно случайных случаев и, следовательно, это трудно в среднем случае.
Мухаммед Аль-Туркистани
8
К вашему сведению: ваш выбор номенклатуры, хотя и естественный, противоречит некоторой существующей номенклатуре: класс Почти-P состоит из таких языков L, что имеет меру 1. Вас также может заинтересовать Знайте, что разреженная версия вашего определения уже использовалась и связана с несколькими другими идеями, см. P-close . Учитывая определение P-close, возможно, хорошее название для вашей концепции - P-density-close или P-close-достаточно :). {A:LPA}
Джошуа Грохов
1
С другой стороны, проблема решения « Окрашивание графика », предположительно, является кандидатом на решение этой проблемы.
4
Я не уверен, что это правильное определение. Если плотность обращается в нуль, то это «почти легко» с помощью любого тривиального языка , независимо от того, насколько это трудно на самом деле. Тем не менее, трудно демонстрировать естественные жесткие языки над алфавитом с плотностью, которая не исчезает, просто из-за кодировки. Разве пересечение не должно быть с допустимыми входными данными размера (так что это проблема обещания), а не со всеми строками? В противном случае это главным образом требует ответа на вопрос: существует ли булево кодирование некоторого NP-жесткого языка с плотностью, которая не исчезает? LA{0,1}n
Андрас Саламон

Ответы:

5

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

=

С другой стороны, я нашел одну, немного менее стандартную гипотезу, которая подразумевает существование искомой NP- полной проблемы, хотя и не естественной. В теории меры, ограниченной по ресурсам, основная гипотеза состоит в том, что NP не имеет меры ноль, обозначаемый NP . Неформально это означает, что NP- языки в E не образуют ничтожного подмножества. Подробнее см. Опрос здесь . В этой теории они доказывают, среди прочего, что NP подразумевает существование Ppμp()0μp()0-бииммунный язык в НП . Язык является P -би-Иммунная если ни , ни его дополнение имеет бесконечное подмножество в P . Такой язык сильно отвечает нашим требованиям.LL

Однако до сих пор остается неясным, существует ли пример, представляющий естественную проблему.

Андрас Фараго
источник
2
Би-иммунитет также намного сильнее вашего состояния и связан с более распространенным использованием «почти всех» в теории структурной сложности, а именно «для всех, кроме конечного числа» ...
Джошуа Грохов
1
@JoshuaGrochow Я согласен, но, похоже, в некотором смысле, P-би-иммунитет означает слишком сильную невосприимчивость . Это, кажется, не происходит среди естественных NP-полных проблем. Меня удивляет, что, по-видимому, нет результата, который обеспечивает условия только для существования «слабо почти повсеместного» неразрешимого NP-полного языка. Под «почти повсеместно» я подразумеваю, что условие «все, кроме конечного числа» заменяется словом «почти все, кроме исчезающего». Это может быть лучше связано с тем, что действительно встречается на практике.
Андрас Фараго
Известно ли, что NP является p-измеримым?
@RickyDemer Насколько я знаю, неизвестно, является ли NP-измеримым.
Андрас Фараго