Насколько распространен фазовый переход в NP-полных задачах?

17

Хорошо известно, что во многих NP-полных задачах наблюдается фазовый переход. Я заинтересован в фазовом переходе в отношении локализации на языке, а не в сложности ввода относительно алгоритма.

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

  1. Существует параметр порядка р(Икс) , который является вычисляемой за полиномиальное время действительной функцией экземпляра.

  2. Есть порог T . Это либо реальная константа, либо она может зависеть от Nзнак равно|Икс|то есть Tзнак равноT(N) .

  3. Для почти каждого Икс с р(Икс)<T , мы имеем ИксL . (Здесь почти все означает: все, кроме исчезающего множества, то есть пропорция приближается к 1 при N ).

  4. Для почти каждого Икс с р(Икс)>T , мы имеем ИксL .

  5. Почти для каждого Икс справедливо, что р(Икс)T . (То есть переходная область является «узкой».)

В этом смысле многие естественные NP-полные задачи демонстрируют фазовый переход. Примерами являются многочисленные варианты SAT, все свойства монотонного графа, различные проблемы удовлетворения ограничений и, возможно, многие другие.

Вопрос: Какие есть «хорошие» исключения? Существует ли естественная NP-полная проблема, которая (вероятно) не имеет фазового перехода в указанном выше смысле?

Андрас Фараго
источник
1
Tр(Икс)Икср±1Tзнак равно0рр
Йонатан N
Таким образом, если вы определяете фазовый переход, как описано выше, то существуют сложные случаи с высокой вероятностью - в случае неполных проблем NP проблема состоит в том, чтобы изучить, может быть, какое-то свойство (доказательство) проблемы, так что вероятнее всего существуют сложные случаи. Наоборот, если бы было доказательство, есть легкие случаи, с высокой вероятностью. Например, случайный граф может иметь граничную плотность вблизи фазового перехода, что может повлиять на легкость решения проблемы.
user3483902

Ответы:

4

Эксперты-исследователи в этой области в основном утверждают, что фазовые переходы являются универсальной особенностью комплексных задач NP, хотя это еще предстоит сформулировать / доказать строго, и это еще не широко рассматривается / не распространяется в более широкой области (это больше вытекает из эмпирически ориентированных филиал исследования). это почти открытая гипотеза. Есть веские доказательства. нет никаких вероятных кандидатов на полные задачи NP без фазового перехода. Вот две ссылки, которые поддерживают этот POV:

Вот примерный набросок истинности утверждения. это имеет отношение к P, содержащемуся в NP complete. NP-полная проблема / язык должна иметь экземпляры, которые разрешимы за время P, а другие - разрешимы за экспоненциальное (или, по крайней мере, суперполиномиальное) время, если P ≠ NP. но всегда должен быть какой-то способ «сгруппировать» P-экземпляры из «не-P» экземпляров. поэтому всегда должны быть некоторые «критерии перехода» между экземплярами P и non-P. короче, может быть, это явление неразрывно связано с P ≠ NP!

Еще один грубый аргумент: все проблемы с NP полностью взаимозаменяемы через сокращения. если фазовый переход обнаружен в одном, он должен быть найден во всех из них.

более косвенные доказательства этого, совсем недавно (~ 2010 г.) было показано, что фазовый переход обнаруживается для нижних границ на монотонных схемах для обнаружения клики на случайных графиках.

полное раскрытие: Моше Варди изучил фазовые переходы, особенно в SAT, и в этом выступлении / видео контрастное, более скептическое мнение.

ВЗН
источник
2
Хорошая ссылка на Моше Варди поговорим, спасибо! Просто чтобы понять суть, фазовый переход ансамбля NP-Complete не подразумевает трудности в сложности экземпляра. М. Варди не упоминает об этом, но распространение опроса решает случаи с миллионами переменных / предложений вблизи критического порога (на положительном конце) для 3SAT, и это было известно в течение некоторого времени, когда на Эрдосе почти наверняка есть алгоритмы полиномиального времени для цикла HAM -Ренький случайный граф.
user834
0

граммN,мNм(N2)мграммN,м

user3483902
источник
2
Бумаги связаны показывают прямо противоположные, что фазовый переход гамильтоновых циклов в Эрдоше-Рении случайных графы показывают фазовый переход (по вероятности гамильтонов цикл появляется) , но показывает не значительного пикапа в вычислительной сложности. Хорошо известно, что есть почти наверняка вероятностные алгоритмы полиномиального времени для случайных графов Эрдоша-Реньи, повсюду в фазовом переходе, даже на критическом пороге. Извините, но я должен дать отрицательный ответ за этот ответ.
user834
-1

C раскраска D регулярных графов имеет ряд дискретных переходов, не особенно поэтапных, если вы не растягиваетесь.

Вот таблица результатов раскраски, которую я буду отправлять на SAT17. Обратите внимание, что 3 раскраски 6 регулярных графов невозможны, за исключением нескольких примеров. Аналогично 4 раскраски графов десятой степени ... Графики C3D5N180 слегка сложны. Золотая точка C4D9 находится только ориентировочно на C4D9N180; Графики C4D9 являются самыми тяжелыми 4cnfs по размеру, с которыми я сталкивался, поэтому C4D9 квалифицируется как «Жесткая точка». Предполагается, что Золотая точка C5D16 существует, но будет находиться в области жестких точек от 5 до 6 цветов.

          Universal Constants of Regular Graph Coloring

У формул раскраски есть переменные lgC на вершину, в общей сложности переменные lgC * N; ребра имеют C раскраски, всего C * M. Есть несколько дополнительных предложений для каждой вершины, чтобы исключить дополнительные цвета. Золотые точки являются наименьшим N таким, что: окрашиваемость C на графах степени D с N вершинами почти всегда выполнима с вероятностью, близкой к 1. Для высокой вероятности N случайных экземпляров были выполнимыми. Для очень высокого, N * N были удовлетворительными. Для Super High N * N * N случайные случаи были удовлетворительными.

Золотые точки расцветки с высокой вероятностью (1 - 1 / N):

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Точки золотой окраски с очень высокой вероятностью (1 - 1 / (N * N)):

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Сверхвысокие вероятности (1 - 1 / (N * N * N)) золотых окрасок:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

Все случайные случаи в исследовании были удовлетворительными. Точки линейной вероятности проверены сотнями выполнимых формул. Квадратичные точки вероятности проверены десятками тысяч выполнимых формул. Кубические вероятностные точки проверены сотнями тысяч выполнимых формул. Очки C4D9 и C5D13 сложны. Предполагается, что точка C5D16 существует. Один случайный случай из пяти красок шестнадцатой степени подтвердит эту гипотезу.

Даниэль Пехоушек
источник