Хаос и

18

Я заинтересован в изучении связей между «хаосом» или, в более широком смысле, динамическими системами и вопросом . Вот пример типа литературы, которую я ищу:пзнак равноNп

Эрчи-Раваш, Мария и Золтан Торошкай. «Твердость оптимизации как переходный хаос в аналоговом подходе к удовлетворению ограничений». Физика природы 7, нет. 12 (2011): 966-970. ( Журнал ссылка .)

Кто-нибудь написал опрос или составил библиографический сборник?

Джозеф О'Рурк
источник
2
это был очень новый / новый / беспрецедентный взгляд на проблему в то время. может быть, вам стоит посмотреть цитаты. Вас заинтересовали бы полные задачи NP в динамических системах? там, вероятно, есть некоторые ...
vzn
1
@vzn: "в то время" не так давно! Да, я был бы заинтересован проблемами NPC в динамических системах. Но то , что я на самом деле после того, как это динамические системы вопросов , которые могли бы пролить свет на вопроса. пзнак равноNп
Джозеф О'Рурк
2
Динамические системы имеют дело с действительными числами, что затрудняет связь их с P против NP. Есть некоторые работы по сложности динамических систем и дифференциальных уравнений, например, проверка диссертации Марка Бравермана.
Каве
2
Клеточные автоматы - это динамические системы, которые обычно используют единицы и нули. Если вы можете показать, что CA не является обратимым, то по определению это односторонняя функция, которая является более сильным утверждением, чем P! = NP.
Уильям Хёрд
2
@vzn: На самом деле, vzn, у вас есть полезный список ссылок в вашем блоге здесь , о фракталах и вычислениях. Например, «Фрактальная размерность в сравнении с вычислительной сложностью».
Джозеф О'Рурк,

Ответы:

6

статья, которую вы цитируете, Эрчи-Раваш, Торочкайочень сквозной; он вписывается в / затрагивает несколько направлений исследования проблем / сложности / твердости 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]

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

[1] Аспекты статистической физики в вычислительной сложности / Gogioso

[2] Скованность лезвия ножа / Тоби Уолш

[3] Монотонная сложность k-клики на случайных графах / Россман

[4] Фазовые переходы и вычислительная сложность / Моше Варди

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

[6] Фазовый переход / Уолш

[7] Определение динамических уравнений сложно / Cubitt, Eisert, Wolf

[8] Задача стационарной системы NP-трудна даже для монотонных квадратичных булевых динамических систем / Just

[9] Проблемы существования предшественников и перестановок для последовательных динамических систем / Баррет, Хант III, Марате, Рави, Розенкранц, Стернс. (также анализируются проблемы анализа для графических динамических систем: унифицированный подход через предикаты графов )

[10] Динамический системный подход к сопоставлению взвешенных графов / Завланос, Паппас

[11] О хаотическом поведении некоторых np-полных задач / Perl

[12] Новый квантовый алгоритм изучения NP-полных задач / Охя, Волович

ВЗН
источник
1
Спасибо, @vzn, это более академично (и более полезно для меня), чем я мог надеяться! Я ценю усилия, которые потребовались для составления вашего подробного ответа.
Джозеф О'Рурк
1
К вашему сведению, новое исследование, проведенное некоторыми из тех же авторов, Ercsey-Ravasz, Toroczkai и др., Переход от порядка к хаосу в твердости случайных задач булевой выполнимости /
arxiv
6

Существует сравнительно недавняя исследовательская тенденция (около 15 лет) смешивания статистической физики неупорядоченных систем и дискретных комбинаторных задач оптимизации. Связь через вероятности Больцмана, а вычислительная жесткость связана с умножением метастабильных состояний физической системы. Модели спиновых стекол доказуемы изоморфны большинству задач дискретной оптимизации.

Я советую вам начать с этой кандидатской диссертации, там вы найдете больше ссылок

Ленка Здеборова. Статистическая физика сложных задач оптимизации на http://arxiv.org/abs/0806.4112

Одна классическая статья, которая, честно говоря, я не очень хорошо понимаю:

Дэвид Л. Донохо, Джаред Таннер. Наблюдаемая универсальность фазовых переходов в многомерной геометрии, с последствиями для современного анализа данных и обработки сигналов на http://arxiv.org/abs/0906.2530

Также, на спиновых очках, введение

Томмазо Кастеллани, Андреа Каванья. Теория спинового стекла для пешеходов

Armando
источник
4

К сожалению, он находится за платным доступом, поэтому я не могу просмотреть эту статью, но после прочтения тезисов она имеет по крайней мере поверхностное сходство с некоторыми «карикатурами», которые я видел при распространении результатов опроса, и она используется для решения 3-SAT. Вот «мультипликационная картина» из книги Манева, Мосселя и Уэйнрайта «Новый взгляд на распространение исследования и его обобщения»

введите описание изображения здесь

αdαс4,2

Было бы интересно посмотреть, соответствуют ли местоположения различных фрактальных областей, о которых сообщают Эрчи-Раваш и Торочкай, различным критическим порогам, отмеченным при распространении съемки (или я совершенно не прав, и сходство действительно поверхностно).

user834
источник
2
Вы можете найти это на arxiv.org/abs/cs/0409012 и arxiv.org/abs/1208.0526, если это поможет
Phylliida
1

В этой статье «Решение простых задач факторизации и NP-полного решения за полиномиальное время с цифровыми машинами memcomputing» заявлен эффективный алгоритм для NP-полного решения задач. Цифровые мемкомпьютерные машины - это нелинейные динамические системы, спроектированные так, что их точки равновесия соответствуют решениям булевой задачи удовлетворения. Наиболее важный вывод заключается в том, что может существовать динамическая система, которая эффективно решает NP-полные задачи. Они пришли к выводу, что их результат все же решает проблему P против NP. P = NP будет следовать из формального доказательства, что если существуют равновесия, глобальный аттрактор не поддерживает периодические орбиты и / или странные аттракторы.

Ссылка:

1- Траверса и Ди Вентра. Полиномиальное решение первичных факторизационных и NP-полных задач с цифровыми станками памяти. Хаос: междисциплинарный журнал нелинейных наук, том 27, выпуск 2, 2017 г.

2- Траверса, Рамелла, Бонани и Ди Вентра, Memcomputing NP-полных задач за полиномиальное время с использованием полиномиальных ресурсов и коллективных состояний , Science Advances, Volume 1, Issue 6, 2015.

Мухаммед Аль-Туркистани
источник