Max Home IndustryВ ознаменование 50-летия открытия Стивеном Куком NP-полных проблем Институт Филдса организовал симпозиум. Скотт Ааронсон выступил с докладом о роли физики в решении сложных задач NP, и это очень интересный отчет.
Вначале тема — это то, что не является темой, что вполне уместно на логическом уровне. О чем идет речь, и я говорю вам в надежде, что вам даже не придется тратить 5 минут вашего времени на просмотр видео, это:
«есть ли какие-либо физические средства для решения произвольной задачи NP за полиномиальное время».
Вы также можете сформулировать это так, как есть аналоговые компьютеры, которые решают задачи NP за полиномиальное время.
Это тема, дорогая моему сердцу с тех пор, как я описал способ найти максимум списка чисел в O (1), то есть постоянное время — возьмите пачку спагетти, разрежьте каждый кусок до длины одного из чисел представляющий интерес, а затем, держа в кулаке крапачок для спагетти вниз по столу, вытащите самый длинный кусок, который будет хорошо виден. С тех пор мне дали название «спагетти-монстр». Еще меня привлекли к ответственности за то, что я не потратил время на подготовку длинных спагетти — смотрите, это был всего лишь пример!
В этом видео рассматриваются аналогичные идеи, но на более продвинутом уровне. Это не чисто теоретический вопрос, потому что квантовые компьютеры — это физические системы, которые могут просто решать задачи NP за полиномиальное время. Они могут? Есть ли какой-то закон Вселенной, который означает, что они не могут? Изучение физических систем, которые могут или кажутся способными решать проблемы NP, должно дать нам представление о том, как действовать в квантовом случае.
Итак, если вам все еще интересно, посмотрите видео:
Означает ли это P = NP?
Ответ заключается скорее в том, что физик думает о NP-сложной проблеме отличается от того, что думает о ней компьютерный ученый. Похоже, что ученый думает, что решение достаточно большого набора примеров задач, содержащихся в NP, является физическим доказательством того, что NP = P. Ученый-компьютерщик отмечает, что не все примеры проблем NP действительно сложны. Существуют более простые проблемы даже в типе, доказуемом в NP, и если вы не можете показать, что ваш физический класс достаточно велик, чтобы включать все проблемы NP этого типа, вы не получили значительного результата.
Мой компьютер для спагетти, например, может решить все задачи сортировки за одно и то же время, но, конечно, сортировка не в NP.
На симпозиуме есть много других интересных докладов, и видео стоит посмотреть. Как выразился Скот Арронсон:
ознакомьтесь также с другими выступлениями — они принадлежат целому ряду случайных никому, таких как Ричард Карп, Ави Вигдерсон, Лесли Валиант, Майкл Сипсер, Александр Разборов, Синтия Дворк и Джек Эдмондс.