Я заинтересован в изучении связей между «хаосом» или, в более широком смысле, динамическими системами и вопросом . Вот пример типа литературы, которую я ищу:
Эрчи-Раваш, Мария и Золтан Торошкай. «Твердость оптимизации как переходный хаос в аналоговом подходе к удовлетворению ограничений». Физика природы 7, нет. 12 (2011): 966-970. ( Журнал ссылка .)
Кто-нибудь написал опрос или составил библиографический сборник?
cc.complexity-theory
p-vs-np
Джозеф О'Рурк
источник
источник
Ответы:
статья, которую вы цитируете, Эрчи-Раваш, Торочкайочень сквозной; он вписывается в / затрагивает несколько направлений исследования проблем / сложности / твердости NP. связь со статистической физикой и спиновыми стеклами была обнаружена в основном посредством «фазовых переходов» в середине 1990-х годов, и это привело к большой работе, см. Gogioso [1] для опроса 56p. фазовый переход совпадает с так называемым «острием ножа ограничения» в [2]. Точно такая же точка перехода действительно появляется в очень теоретическом анализе вычислительной сложности / твердости, например, [3], который также относится к ранним исследованиям поведения точки перехода в задачах клики Эрдосом. [4] - это обзорная / видео-лекция Моше Варди о фазовых переходах и сложности вычислений. [5] [6] - обзоры поведения фазовых переходов в NP полных задачах. Автор Moore, Walsh.
затем разрозненное, но, возможно, все большее изучение разнообразных связей динамических систем с вычислительной сложностью и сложностью в различных контекстах. в [7] обнаружена общая связь, которая, возможно, объясняет некоторые основные причины частого «перекрытия». ссылки [8] [9] [10] [11] разнообразны, но показывают повторяющуюся тему / сквозной вид между полными задачами NP и различными динамическими системами. в этих работах есть некоторая концепция / примеры гибридной связи между дискретными и непрерывными системами.
хаотическое поведение в NP полных системах проанализировано в [11].
Несколько похожая ссылка на Ercsey-Ravasz / Toroczkai в области квантовых алгоритмов в том, что динамическая система работает «по-видимому» в P-времени [12]
[1] Аспекты статистической физики в вычислительной сложности / Gogioso
[2] Скованность лезвия ножа / Тоби Уолш
[3] Монотонная сложность k-клики на случайных графах / Россман
[4] Фазовые переходы и вычислительная сложность / Моше Варди
[5] Фазовые переходы в NP-полных задачах: вызов вероятности, комбинаторика и информатика / Мур
[6] Фазовый переход / Уолш
[7] Определение динамических уравнений сложно / Cubitt, Eisert, Wolf
[8] Задача стационарной системы NP-трудна даже для монотонных квадратичных булевых динамических систем / Just
[9] Проблемы существования предшественников и перестановок для последовательных динамических систем / Баррет, Хант III, Марате, Рави, Розенкранц, Стернс. (также анализируются проблемы анализа для графических динамических систем: унифицированный подход через предикаты графов )
[10] Динамический системный подход к сопоставлению взвешенных графов / Завланос, Паппас
[11] О хаотическом поведении некоторых np-полных задач / Perl
[12] Новый квантовый алгоритм изучения NP-полных задач / Охя, Волович
источник
Существует сравнительно недавняя исследовательская тенденция (около 15 лет) смешивания статистической физики неупорядоченных систем и дискретных комбинаторных задач оптимизации. Связь через вероятности Больцмана, а вычислительная жесткость связана с умножением метастабильных состояний физической системы. Модели спиновых стекол доказуемы изоморфны большинству задач дискретной оптимизации.
Я советую вам начать с этой кандидатской диссертации, там вы найдете больше ссылок
Ленка Здеборова. Статистическая физика сложных задач оптимизации на http://arxiv.org/abs/0806.4112
Одна классическая статья, которая, честно говоря, я не очень хорошо понимаю:
Дэвид Л. Донохо, Джаред Таннер. Наблюдаемая универсальность фазовых переходов в многомерной геометрии, с последствиями для современного анализа данных и обработки сигналов на http://arxiv.org/abs/0906.2530
Также, на спиновых очках, введение
Томмазо Кастеллани, Андреа Каванья. Теория спинового стекла для пешеходов
источник
К сожалению, он находится за платным доступом, поэтому я не могу просмотреть эту статью, но после прочтения тезисов она имеет по крайней мере поверхностное сходство с некоторыми «карикатурами», которые я видел при распространении результатов опроса, и она используется для решения 3-SAT. Вот «мультипликационная картина» из книги Манева, Мосселя и Уэйнрайта «Новый взгляд на распространение исследования и его обобщения»
Было бы интересно посмотреть, соответствуют ли местоположения различных фрактальных областей, о которых сообщают Эрчи-Раваш и Торочкай, различным критическим порогам, отмеченным при распространении съемки (или я совершенно не прав, и сходство действительно поверхностно).
источник
В этой статье «Решение простых задач факторизации и NP-полного решения за полиномиальное время с цифровыми машинами memcomputing» заявлен эффективный алгоритм для NP-полного решения задач. Цифровые мемкомпьютерные машины - это нелинейные динамические системы, спроектированные так, что их точки равновесия соответствуют решениям булевой задачи удовлетворения. Наиболее важный вывод заключается в том, что может существовать динамическая система, которая эффективно решает NP-полные задачи. Они пришли к выводу, что их результат все же решает проблему P против NP. P = NP будет следовать из формального доказательства, что если существуют равновесия, глобальный аттрактор не поддерживает периодические орбиты и / или странные аттракторы.
Ссылка:
1- Траверса и Ди Вентра. Полиномиальное решение первичных факторизационных и NP-полных задач с цифровыми станками памяти. Хаос: междисциплинарный журнал нелинейных наук, том 27, выпуск 2, 2017 г.
2- Траверса, Рамелла, Бонани и Ди Вентра, Memcomputing NP-полных задач за полиномиальное время с использованием полиномиальных ресурсов и коллективных состояний , Science Advances, Volume 1, Issue 6, 2015.
источник