Теория вычисления сложности (наука о том, сколько ресурсов необходимо для решения различных вычислимых задач), область исследований Скотта Ааронсона, — на первый взгляд сугубо прикладная дисциплина, никак не затрагивающая извечные философские вопросы. Но автор предлагает использовать иной подход. Достижения последних десятилетий в теории вычислительной сложности позволяют по-новому взглянуть на фундаментальные проблемы математики и квантовой физики, проблему индукции, искусственного интеллекта, рациональности, свободы воли, антропный принцип и многие другие извечные вопросы. В книге «Квантовые вычисления со времён Демокрита» Скотт Ааронсон показывает, как взаимовыгодно сотрудничают философия и теория вычислительной сложности.
Одним из ключевых вопросов, затрагивающим многие поднимаемые в книге темы, является вопрос о равенстве классов сложности P и NP — одна из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США. Равен ли класс P классу NP? Задачи класса P решаются за время, определяемое полиномом от размера входных данных. Для решения задач класса NP необходимо затратить «экспоненциальное время», однако для проверки решения задач такого класса можно обойтись «полиномиальным временем». Например, в 2002 году было показано, что проверка чисел на простоту входит в класс P. Справедливо ли это также для проблемы фолдинга (сворачивания) белка? Если да, то тогда будет достигнут, в частности, существенный прогресс в борьбе с онкологическими заболеваниями. Проверка решения некоторых задач также требует «экспоненциального времени», какие-то можно решить с заданной долей вероятности, а какие-то можно решить за «полиномиальное время», используя квантовый компьютер. И этим классы сложности отнюдь не исчерпываются. Скотт Ааронсон постепенно познакомит вас с «зоопарком сложности», попутно разъяснив различные идеи Тьюринга, Гёделя и других авторитетных господ, и даже познакомит с некоторыми нелокальными теориями скрытых параметров. Впрочем, в предисловии автор в подробностях описывает, какие темы будут рассмотрены в книге, поэтому здесь сознательно не приводится детальное описание её содержания.
В целом в книге «Квантовые вычисления со времён Демокрита» рассматривается множество интересных и фундаментальных вопросов в контексте темы P vs NP, но и само возможное разрешение вопроса о равенстве или неравенстве классов сложности P и NP будет иметь глубокие последствия. Словами Скотта Ааронсона:
Если P = NP, то мир был бы совсем не таким, каким мы обычно его себе представляем. «Творческие прорывы» не имели бы особого значения, поскольку не было бы фундаментальной разницы между поиском решения и его проверкой. Каждый, кто способен оценить симфонию, был бы Моцартом. Каждый, кто понимает пошаговые рассуждения, был бы Гауссом. Каждый, кто может распознать хорошую инвестиционную стратегию, был бы Уорреном Баффетом. Эту проблему можно сформулировать и в дарвиновских терминах: если мы живём в такого рода вселенной, то почему, учитывая нашу эволюционную историю, мы всё ещё не можем использовать это преимущество?
С разрешения издательства «Альпина нон-фикшн» приводим в качестве ознакомительной главу «Пенроуз», посвящённую следующим вопросам: возможно ли создать искусственный интеллект; имеют ли отношение принципы работы квантовых компьютеров к функционированию мозга человека; может ли наш интеллект быть алгоритмическим; возможно ли в принципе свести сознание к вычислительным процессам.
<...>
