Max Home IndustryСтатья, принятая для Physical Review Letters, в настоящее время приписывается утверждению, что «Физика — это сложно». Однако все зависит от того, что вы подразумеваете под «физикой».
Трудные задачи NP представляют собой странный набор, потому что они, по крайней мере, так же сложны, как и полные задачи NP, но они могут быть сложнее. Простой способ думать об этом заключается в том, что они обычно соответствуют задачам, решение которых заняло бы слишком много времени для любой реальной версии проблемы, выполняемой на реальном компьютере. Обычно они включают в себя своего рода комбинаторный поиск решения, которое растет экспоненциально или быстрее по мере роста количества задействованных элементов.
То, что, по утверждениям публикуемой статьи, доказано, указано в ее названии: «Извлечение динамических уравнений из экспериментальных данных — сложная задача», и в аннотации говорится:
Поведение любой физической системы определяется лежащими в ее основе динамическими уравнениями. Большая часть физики озабочена открытием этих динамических уравнений и пониманием их последствий. В этой работе мы показываем, что, что примечательно, идентификация лежащего в основе динамического уравнения из любого количества экспериментальных данных, какими бы точными они ни были, является доказуемой вычислительно сложной задачей (она NP-трудна) как для классических, так и для квантово-механических систем
Таким образом, NP-трудная процедура состоит в том, что вы можете наблюдать мир с любыми деталями, а затем пытаться вывести уравнения, управляющие динамикой. То, что это сложный NP, не должно вызывать большого удивления.
Хотя статья еще не опубликована в Physical Review Letters, препринт есть в: arXiv: 1005.0005v1.
Здесь объясняется основная идея. Возьмите общее выражение для возможной динамики и выведите параметры из снимков системы в разное время. У вас есть проблема, когда вам дается начальное состояние s (0) и столько снимков s (t), сколько вам нужно. Из этих данных вы должны вывести параметры главного уравнения, что является проблемой поиска. Более простая форма вопроса показывает, почему это так сложно. Учитывая только один моментальный снимок, выясните, мог ли он быть сгенерирован действительной динамикой из исходного состояния. Обратите внимание: этот вопрос просто требует, чтобы вы нашли одно уравнение, которое могло бы сгенерировать развитие времени — учитывая, что у нас есть только один снимок, их может быть много. Проблема становится NP-трудной, потому что прямое вычисление от уравнения к развитию включает ex, но обратный путь в обратном направлении, то есть от разработки к уравнению включает log x, который в комплексной области является многозначным. Вы должны искать правильный набор значений, которые дают вам результат.
Оказывается, этот поиск эквивалентен задаче 3SAT, которая включает присвоение набора значений трем переменным в логическом выражении, чтобы сделать его истинным. Задача 3SAT является NP-полной, и поэтому задача поиска динамики из снимков является NP-сложной, поскольку 3SAT может быть сведен к ней за полиномиальное время, но не обязательно в NP.
Аргумент справедлив как для классических, так и для квантовых систем, поэтому вывести уравнения из полных данных о системе NP-сложно.
Неужели это так удивительно?
Возможно нет. В конце концов, мы давно привыкли к мысли, что хаос естественен для динамических систем. Так почему же следует ожидать, что данные будут предоставлять уравнения простым способом? С другой стороны, системы с высокой степенью симметрии, вероятно, допускают простой алгоритм, когда дело доходит до вывода их динамики.
Приятно видеть, что информатика и теория сложности, в частности, могут что-то сказать о физике.