Может ли быть чрезвычайно большое скрытое подмножество полиномиально разрешимых задач в задачах NP-Complete?

Предположим, P! = NP.

Мы знаем, что можем в любое время легко создавать 3-SAT. Мы также можем генерировать то, что мы считаем трудными примерами (потому что наши алгоритмы не могут их быстро решить). Что-нибудь мешает множеству жестких экземпляров быть сколь угодно малыми, при условии, что для любого данного размера экземпляра (n) существуют только экземпляры Poly (n) (или даже постоянные) размера Poly (n) или меньше?

Для любого жесткого экземпляра 3-SAT нам нужно было бы добавить набор всех экземпляров 3-SAT, к которому он сводится, с помощью циклического цикла сокращения NP-полноты, но я не предвижу это добавление к числу сложных экземпляров очень сильно ,

В этом мире мы могли бы построить алгоритм, который полиномиально решает все NP-полные задачи, кроме исключительных.

Редактировать: более мягкий вариант вопроса: даже если мы покажем P! = NP, как мы можем узнать, действительно ли данный метод для генерирования задач размером 3-SAT генерирует сложный с некоторой необходимой вероятностью? Если нет способа узнать только из P! = NP, что требуется, чтобы показать, что мы можем создать сложную NP-полную проблему?

1) В зависимости от того, что именно подразумевалось, заключение в наблюдении Каве может быть усилено из $\mathsf{NP} \subseteq \mathsf{P/poly}$ в $\mathsf{P} = \mathsf{NP}$, по существу, используя теорему Махани. То есть, если есть алгоритм, который решает SAT и работает во времени$\leq p(n)$ на все случаи длины $n$ за исключением возможно $q(n)$ такие случаи, когда $p$ а также $q$ оба полиномы, то на самом деле $\mathsf{P} = \mathsf{NP}$, См., Например, Мейер и Патерсон и ссылки в них, или монографию Шонинга «Сложность и структура» . Так что, если это отражает ваше представление о «трудных случаях», то должно быть больше, чем$poly(n)$ много сложных случаев для каждого $n$предполагая $\mathsf{P} \neq \mathsf{NP}$,

К вашему сведению, такие алгоритмы иногда называют алгоритмами «apt» или «APT» для «почти полиномиального времени» (не путать с более современным классом сложности $\mathsf{almostP}$что бывает равным $\mathsf{BPP}$).

2) Вышесказанное может быть еще более усилено, как изложено ниже. Предполагать$\mathsf{P} \neq \mathsf{NP}$, Тогда выше сказанное говорит о том, что для любого алгоритма решения SAT и любого полинома$p$существует множество экземпляров суперполиномиального размера, для которых алгоритм занимает больше $p(n)$время. Но набор может зависеть от алгоритма.

Более сильный результат переключает квантификаторы и делает вывод: существует супер-полиномиальный набор размеров H (для «жесткого»), такой, что для любого алгоритма A, решающего SAT, и любого полинома p, A требуется больше, чем $p(n)$время на всех, кроме конечного числа элементов H. Такое H называется ядром сложности (предположение о размере не является частью определения ядра сложности). Определение и существование ядер сложности было дано Линчем . Результат, который я только что процитировал, подтверждается Орпоненом и Шонингом .

Никто не упомянул знаменитую газету Impagliazzo «Пять миров».

http://www.cs.ucsd.edu/users/russell/average.ps

другой угол в этом вопросе (вне ссылки на теорему Махани). «Точка перехода» в SAT - это исследование этого явления, связанного с распределением простых и жестких экземпляров, особенно в «критической точке», где вероятность тяжелых экземпляров максимальна. литература по этому вопросу длинная и сложная. у него есть как эмпирический, так и аналитический подходы. это имеет глубокие связи с физикой / термодинамикой. [3] к сожалению, в настоящее время нет статьи в Википедии по этой очень важной и фундаментальной теме теории сложности. кроме того, кажется, что нет много общих или «стандартных» опросов по этому вопросу. Вот один недавний упоминание о начале фазовых переходов SAT [1] и TCS в целом. [4] Ваш вопрос также попадает в категорию «действительно хороший ответ будет в основном почти P$\stackrel{?}{=}$НП доказательство. "

Что-нибудь мешает множеству жестких экземпляров быть сколь угодно малыми, при условии, что для любого данного размера экземпляра (n) существуют только экземпляры Poly (n) (или даже постоянные) размера Poly (n) или меньше?

снова теорема Махани (сформулированная немного по-другому) прямо отвечает на это. Другой способ взглянуть на это состоит в том, что попытки сузить распределение экземпляров некоторым ключевым / характерным способом приводят к NP-завершенным функциям. Примером этого является сложность монотонной схемы: «Функции среза». [2]

[1] Прогнозирование удовлетворенности при фазовом переходе Лин Сюй, Хольгер Х. Хос, Кевин Лейтон-Браун

[2] Пол Э.С. Данн: Сложность центральных функций среза. Теор. Вычи. Sci. 44: 247-257 (1986)

[3] Аналитическое и алгоритмическое решение случайных задач удовлетворенности М. Мезард, Г. Паризи, Р. Зекчина

[4] Фазовые переходы в NP-полных задачах: вызов вероятности, комбинаторика и информатика. Автор - Мур