Есть ли какие-нибудь неполные эвристические проблемы с NP?

18

Существуют ли какие-либо NP-полные проблемы с бесконечным подмножеством экземпляров такие, что принадлежность к может быть решена за полиномиальное время, и для всех , может быть решена за полиномиальное время? (Предполагая )Φx Φ x P N PΦxΦxPNP

Phylliida
источник
Посмотрите на эту удивительную гипотезу , которая значительно более правдоподобна, чем звучит ее утверждение, по причинам, изложенным в статье.

Ответы:

16

См. Ответ Джоша Грохова на надмножество времен Poly полного языка NP с бесконечным числом исключенных из него строк . Согласно этому ответу, согласно некоторым естественным криптографическим предположениям, для каждой задачи, полной со-NP, существует бесконечное подмножество случаев, такое что членство в является полиномиальным временем, а задача решения, ограниченная , тривиальна (ответ всегда нет).Φ ΦΦΦΦ

Это можно формализовать, заявив, что ни один со-NP-полный набор не является P-иммунным. Также известно (опять же при криптографических предположениях), что ни один NP-полный набор не является P-иммунным. Таким образом, существует еще одно бесконечное подмножество такое, что членство в проверяется за полиномиальное время, и проблема решения, ограниченная всегда имеет ответ yes. См., Например, Glasser et al., «Свойства NP-полных наборов», SICOMP 2006, doi: 10.1137 / S009753970444421X .Φ Φ ΦΦΦ

Дэвид Эппштейн
источник
Это действительно круто, спасибо :). Для полноты, эти предположения таковы: существуют псевдослучайные генераторы и существуют безопасные односторонние перестановки
Phylliida
@Phylliida: Обратите внимание, что те используют некоторое теоретико-сложное определение для «генератора псевдослучайных данных», а не обычное криптографическое определение.
0

Первое наблюдение состоит в том, что наличие именно того, что вы спрашиваете, будет доказательством того, что поскольку это будет означать, что множество всех экземпляров не может быть решено за полиномиальное время.PNP

Однако, и я думаю, что именно это вы и имели в виду, мы можем немного поиграть с тем, что мы подразумеваем под словом «решено за полиномиальное время». Если мы имеем в виду под этим все бесконечные подмножества экземпляров, принадлежность которых к P, являются N P -полными, то по теореме Махани нет ответа ( http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute -to-mahaney.html ). Эта теорема утверждает , что нет NP-полной задачи не может быть разреженной , если P = N P . Теперь, взяв подмножество экземпляров { 0 ii N } , мы имеем бесконечное разреженное подмножество экземпляров, для которых проверочное членство находится вϕPNPP=NP{0iiN} который не может быть N P -завершенным, если P = N P по теореме Махани.PNPP=NP

holf
источник
Извините, я имел в виду, что они не могут быть решены за полиномиальное время при условии, что , вы правы, что это очень важноPNP
Phylliida