Напомню: эта книга основана на курсе лекций, прочитанном мной в 2006 г. В последний день занятий, следуя прекрасной традиции, заведенной еще Ричардом Фейнманом, я предложил студентам задавать мне любые вопросы. У Фейнмана, по правилам, можно было спрашивать о чем угодно, за исключением политики, религии и итогового экзамена. В моем случае никакого экзамена не предусматривалось, и я даже не стал исключать политику и религию. В этой главе собраны некоторые из вопросов, которые мне тогда задали, вместе с моими ответами.
Студент: Задумываетесь ли вы об использовании теоретической информатики в физике? Может быть, она могла бы ограничить что-то или натолкнуть нас на какие-то новые физические теории? Как вы считаете, не можем ли мы с ее помощью открывать физические теории, которые обеспечат нам более мощные модели, чем квантовые вычисления?
Скотт: Можно ли считать BQP концом пути или нас ждут новые открытия? Фантастический вопрос, и мне хотелось бы, чтобы об этом думало как можно больше людей. Я в этом вопросе поведу себя как политик и не стану отвечать прямо, поскольку очевидный ответ звучит очень просто: «Не знаю». Мне кажется, вся идея науки состоит в том, что если мы не знаем ответа, мы не пытаемся высосать его из пальца или еще как. Мы стараемся обосновывать свои ответы. Так что пока все, что нам известно, согласуется с гипотезой о том, что квантовые вычисления — действительно конец пути. Грег Куперберг привел аналогию, которая мне понравилась. Он сказал, что есть люди, которые говорят: вот, мы перешли от классической механики к квантовой, какие нас еще ждут сюрпризы? Но, может быть, здесь как с Землей. Сначала люди считали, что Земля плоская, а затем, открыв ее шарообразность, говорили, что, может быть, она обладает топологией бутылки Клейна. Да, в заданном направлении есть неожиданности, но когда вы в них разобрались и их приняли, дальше в этом направлении уже может не быть дальнейших неожиданностей.
Земля сегодня такая же круглая, какой была при Эратосфене. Мы с вами говорили о странном свойстве квантовой механики, о том, что она кажется очень хрупкой теорией. Даже в общей теории относительности можно представить какие-то изменения и нововведения, скажем торсионные поля или еще что-то. Но в квантовой механике очень трудно что-то варьировать, в ней сразу же возникают противоречия. Разумеется, это никак не доказывает, что за ней ничего нет. В XVIII веке, вероятно, тоже казалось, что невозможно играть с евклидовой геометрией, не порождая противоречий. С другой стороны, сам факт, что нечто можно себе представить, не означает, что на проработку этого нечто следует тратить время. Итак, существуют ли реальные мысли о том, что могло бы стоять за квантовой механикой?
Ну, по квантовой гравитации имеются такие идеи, в которых, похоже, нет даже унитарности — даже вероятности там в сумме не дают единицы. Оптимист здесь воскликнул бы: «Ага! Мы нашли что-то за пределами квантовой механики!» А пессимист сказал бы, что все эти теории (в их нынешнем виде) полная чепуха, и когда специалисты по квантовой гравитации разберутся наконец в том, чем занимаются, унитарность вернется. Еще есть явления, которые, кажется, немного меняют наши представления о квантовой механике. Среди них проблема исчезновения информации в черной дыре:
Вот вы падаете в черную дыру. Основная проблема в том, что вся информация о вас — если вы падаете в черную дыру — позже, как предполагается, выходит наружу в виде излучения Хокинга. Если физика за пределами горизонта событий унитарна, то эта информация просто обязана выйти. Но мы не знаем в точности, как именно выходит информация. Если провести полуклассическое вычисление, получится, что выходит только тепловой шум. Однако большинство физиков (и даже Хокинг) в настоящий момент считают, что если бы мы на самом деле понимали, что происходит, то увидели бы, что информация и правда выходит.
Проблема в том, что, оказавшись внутри черной дыры, вы даже не приближаетесь к горизонту событий. Вы направляетесь прямо в сингулярность. С другой стороны, если черная дыра должна постепенно выпускать из себя информацию, то представляется, что эта информация должна каким-то образом находиться на горизонте событий или совсем рядом с ним. Это особенно верно, поскольку мы знаем, что количество информации в черной дыре пропорционально площади ее поверхности. Но вы, с вашей точки зрения, находитесь где-то далеко внутри. Так что создается впечатление, что информация должна находиться в двух местах одновременно.
Во всяком случае, одно из предположений, которые выдвигают такие люди, как Герард т'Хоофт и Ленни Сасскинд, состоит в том, что да, информация действительно «дублируется». На первый взгляд, это нарушение унитарности, в первую очередь теоремы о запрете клонирования. Но, с другой стороны, как можно увидеть обе копии этой информации? Если вы внутри черной дыры, вы никогда не увидите внешнюю копию. Можно представить себе, что если кому-то отчаянно захочется выяснить, нарушается ли здесь теорема о запрете клонирования, — настолько отчаянно, что он готов будет пожертвовать ради этого своей жизнью, — то можно сначала измерить внешнюю копию, а затем прыгнуть в черную дыру и поискать там копию внутреннюю. Но вот что забавно: кое-кто уже успел посчитать, что произойдет, если попытаться так сделать; выяснилось, что придется очень долго ждать, пока информация выйдет наружу в виде излучения Хокинга, и к тому времени, когда одна копия выйдет наружу посредством излучения Хокинга, другая уже достигнет сингулярности. Такое впечатление, что какой-то цензор не позволяет вам увидеть обе копии этой информации одновременно. Так что с точки зрения любого наблюдателя унитарность сохраняется. Забавно, что есть какие-то мелочи, которые, кажется, могли бы вызвать конфликт с квантовой механикой или привести к более мощной модели вычисления, но стоит к ним как следует приглядеться, и так казаться перестает.
С тех пор, как я впервые написал эту главу в 2006 г., события на фронте черных дыр развивались активно и очень интересно. Помимо прочего, появились новые аргументы, согласно которым давно сложившиеся представления о том, что наблюдатель, падающий в черную дыру, при прохождении горизонта событий «не увидит ничего особенного» и заметит безумные квантово-гравитационные эффекты лишь за доли секунды до аннигиляции в сингулярности, может оказаться ошибочным. Напротив, теория квантовой гравитации вполне может понадобиться даже для предсказания того, что такой наблюдатель увидит непосредственно на горизонте событий!
Первое указание на это пришло из работы специалиста по теории струн Самира Матхура вместе с образом черной дыры, получившим прозвище «пушистого клубка»[189]. На такую гипотезу Матхура подвигло проистекающее из теории струн «соответствие AdS/CFT[190]», которое определяет некоторые квантовые теории гравитации для D пространственных измерений так: сначала строятся обычные квантовые теории поля для D — 1 пространственных измерений, а затем говорится, что D-мерная квантовая гравитация — это всего лишь «дуальное описание» квантовой теории поля для пространства меньшей размерности. Если соответствие AdS/CFT верно, то, по крайней мере в теории струн черные дыры должны описываться средствами совершенно обычной, унитарной, обратимой квантовой механики, из чего затем следует, что попадающие в черную дыру биты информации должны каким-то образом выходить оттуда в виде излучения Хокинга. Проблема в том, что этот абстрактный аргумент не поясняет, как именно эти биты выбираются наружу или хотя бы как это в принципе возможно, при том что полуклассический расчет Хокинга свидетельствует об обратном. Так что Матхур решил просчитать, что происходит в некоторых «модельных сценариях» теории струн, которые учитывают хотя бы некоторые аспекты физических черных дыр. Обнаружил он — или утверждает, что обнаружил, — что «область квантово-гравитационных странностей» не остается крохотной (планковского размера) штучкой в сингулярности, но вместо этого увеличивается в размерах до тех пор, пока не превратится в сложный «пушистый клубок», заполняющий всю область в пределах горизонта событий. Так что в этой картине причина, по которой биты информации могут выйти наружу в виде излучения Хокинга, по существу, та же, по которой биты, описывающие кусок угля, могут выйти наружу при сжигании этого угля, а именно потому, что эти биты имеются на поверхности!
Матхур, однако, не говорил явно, что большой наблюдатель, падающий в черную дыру, увидит на горизонте событий что-то особенное, более того, он предполагал, что существует «приблизительное дуальное описание», верное для реалистичных по размеру наблюдателей, согласно которому эти наблюдатели проследуют сквозь горизонт событий до самой сингулярности, в точности так, как предсказывает классическая общая теория относительности. Это описание будет верным, несмотря на тот факт, что в определенном смысле «настоящая физика» происходит на поверхности этого пушистого клубка, в месте, которое мы привыкли называть горизонтом событий.
Не так давно, однако, появились доводы[191] в пользу того, что наблюдатель все же встретит нечто особенное на горизонте событий: что на самом деле он просто наткнется там на «файервол» в первоначальном смысле слова, то есть на огненную стену, и сгорит задолго до того, как хотя бы приблизится к сингулярности! Или, по крайней мере, даже если ничего такого не случается в «молодых» черных дырах, то непременно случится в «старых», тех, которые уже излучили по крайней мере половину своих битов в виде хокинговского излучения. Я не смогу воспроизвести обоснование этого предсказания во всех подробностях, но основано оно на модифицированной версии парадокса Хокинга, связанного с исчезновением информации в черной дыре. В момент подготовки американского издания этой книги (январь 2013 г.) специалисты, кажется, находились в сомнениях по поводу «файервола», и даже некоторые эксперты меняли свое мнение чуть ли не каждый месяц.
Чем бы ни закончилось разбирательство, я лично, признаюсь, почувствовал облегчение от такого развития событий, поскольку они очень созвучны невнятному ощущению, возникшему у меня после знакомства с проблемой исчезновения информации в черной дыре, а именно что на горизонте событий должно происходить что-то «физически особенное», несмотря на то, что классическая общая теория относительности утверждает обратное.
Я имею в виду вот что. Рассмотрим ситуацию с точки зрения наблюдателя Алисы, находящейся вне черной дыры и наблюдающей за происходящим в то время, как ее полоумный приятель Боб прыгает в черную дыру. Хорошо известно, что, поскольку по мере приближения к горизонту событий свету требуется все больше и больше времени на уход от черной дыры, Алиса на самом деле никогда не увидит, как Боб исчезает за горизонтом событий. Вместо этого Алисе будет казаться, что Боб все ближе и ближе подлетает к горизонту, но так за него и не уходит. По современным представлениям, квантовая информация, соответствующая Бобу, на самом деле «размажется» тонким слоем по всему горизонту событий с невероятной скоростью. Затем Алиса, если подождет лет примерно 1070, увидит, как горизонт событий, по которому размазало ее приятеля, медленно испаряется туманом хокинговского излучения — туманом, информационное содержание которого пропорционально площади горизонта событий в планковских единицах. Опять же по современным представлениям, если Алиса достаточно тщательно соберет и сложит вместе все кусочки хокинговского излучения, то она сможет, в принципе, восстановить те самые «кубиты Боба», которые упали в дыру. Теперь, учитывая все это, я спрашиваю вас: правдоподобно ли описание горизонта событий как совершенно обычного места без всяких странных квантово-гравитационных эффектов и можно ли говорить, что вся новая физика должна быть сосредоточена в крохотной сингулярности? Я говорю: нет, и физики, кажется, все больше склоняются к тому же мнению!
Но даже если мы согласимся с этим, остается вопрос о том, возможна ли «комплементарная» точка зрения, а именно точка зрения Боба, согласно которой он проходит горизонт событий без происшествий и живет еще, может быть, несколько часов (в случае сверхмассивной черной дыры, подобной той, что находится в центре нашей Галактики), пока не погибнет страшной смертью в сингулярности. Может, такая точка зрения возможна, может, нет, а может, возможна только в приблизительном варианте. Забавно, но не очевидно даже, относится ли вопрос о том, что «испытывает» Боб после прохождения горизонта событий, к компетенции науки! Ведь что бы ни испытывал Боб, даже если ничего, он никак не сможет сообщить об этом тем, кто остался вне черной дыры. Правда, информация о нем со временем выйдет наружу в виде тонких корреляций между фотонами хокинговского излучения, но процесс, порождающий эти фотоны, нисколько не хуже можно было описать с «комплементарной» позиции Алисы, с ее точки зрения, согласно которой Боба просто размазало по горизонту событий, и он вообще его не прошел! При этом Алисе не придется даже упоминать о «переживаниях» Боба после прохождения горизонта событий. Так что в каком смысле последние часы субъективного осознания себя Бобом — часы между прохождением горизонта событий и попаданием в сингулярность — реально «существуют»? Один Боб знает!
Конечно, вы могли бы возразить, что ситуация здесь не слишком отличается от обычной, в какой находимся мы все и все время по отношению к чужим, не нашим сознаниям. Философски говоря, Алиса не может быть абсолютно уверена в том, что существует «нечто, испытываемое как» быть Бобом, даже если Боб сидит с ней за одним столом в кливлендской квартире, а не несется кувырком в сингулярность черной дыры. Я бы сказал, что здесь, как часто бывает, физика просто «проводит нас по кругу» и вынуждает посмотреть на древнюю философскую загадку с новой стороны, в данном случае — через возможность двух комплементарных описаний, по одному из которых Боба размазывает в блин толщиной порядка планковской длины, а по второму он проживает еще несколько часов.
Оставив в стороне субъективные переживания Боба, заметим, что все современные представления о черных дырах соглашаются, кажется, в одном: нет нужды хотя бы чуть-чуть менять квантовую механику. Да, черные дыры — чудесная и пугающая лаборатория принципов квантовой механики, но очень многое, судя по всему, свидетельствует о том, что в конечном итоге они, как и прочие физические объекты, не противоречат этим принципам. Но если так, если даже самые экстремальные объекты, самые модные источники гравитации во Вселенной не разрушают квантовую механику, то становится гораздо труднее вообразить, что могло бы ее разрушить. Что-то космологическое? Что-то из самого начала времен? Из связи между сознанием и мозгом? Конечно, все возможно, но очень может быть также, что нам придется примириться с возможностью того, что квантовая механика фундаментально верна.
И это наконец приводит меня к главному моменту этого долгого отступления и поводу его завершить. Фигурально выражаясь, физики к настоящему времени заглянули во многие уголки вселенной, но не обнаружили там никаких явлений, которые могли бы образовать класс сложности, превосходящий наши вычислительные возможности сильнее, чем BQP — класс задач, решаемых квантовым компьютером с ограниченной ошибкой за полиномиальное время. Это не значит, что ничего подобного никогда не произойдет, просто BQP оказался чрезвычайно серьезным противником.
Во всяком случае, ориентироваться на физику — «очевидный» способ разобраться с тем, что может быть за BQP. Второй способ — попытаться найти ответ на этот вопрос внутри теории вычислительной сложности. Иными словами, мы можем спросить с чисто математической позиции, какие разумные с виду классы сложности могут быть выше BQP; когда-нибудь, возможно, новая физическая теория сможет правдоподобно их обосновать.
Первое, что мы замечаем, задав этот вопрос, — это то, что вычислительные модели, дающие нам больше чем BQP, дают в большинстве своем намного больше: позволяют решать не только NP-полные задачи за полиномиальное время, но часто даже PP-полные и PSPACE-полные задачи. Именно так происходит, к примеру, при добавлении нелинейностей, поствыбранных измерений или замкнутых времениподобных траекторий. И конечно, хотя все эти модели логически возможны, мне они представляются не просто слишком фантастическими, но и слишком скучными! В прошлом Природа всегда оказывалась коварнее, чем мы ожидали; она всегда находила способ дать нам то, что мы хотели, но не целиком. Итак, предположим, что мы хотим точно знать, что существует нечто более мощное, чем квантовые вычисления, но при этом такое, что все же не может решать NP-полные задачи за полиномиальное время. Сколько у нас тогда «места» для такой модели? У нас действительно есть задачи, которые вроде бы проще NP-полных, но все же слишком сложны, чтобы эффективно решаться квантовым компьютером. Два примера таких задач — это изоморфизм графа и проблема кратчайшего вектора. Они очень «близки» к NP-полным, но, вероятно, все же не совсем; представляется, что эти задачи сводятся к инвертированию односторонних функций и различению функций случайных и псевдослучайных.
Много лет назад я предложил пример вычислительной модели (обсуждается в главе 12), в которой вы видите всю историю скрытой переменной в ходе квантового расчета. Я привел свидетельства того, что в этой модели вы действительно получаете больше, чем при обычных квантовых вычислениях, — к примеру, вы решаете задачи об изоморфизме графа и об аппроксимации кратчайшего вектора, — но по-прежнему не можете решать NP-полные задачи. С другой стороны, признаю, что моя модель была довольно искусственной. Так что, возможно, прежде чем дойти до NP-полных задач, нам все же придется сделать еще один драматический шаг, но я в этом не уверен.
Студент: Откуда вы знаете, что шаг этот один? Теоретически между двумя задачами всегда можно втиснуть еще одну.
Скотт: Разумеется, но вот какое дело: никто не интересовался квантовыми вычислениями, когда Бернштейн и Вазирани выяснили, что с их помощью можно решить задачу рекурсивной выборки Фурье. Интерес возник только тогда, когда обнаружилось, что таким способом можно решать задачи, которые и раньше считались важными, такие как разложение на простые множители. Так что если мы оценим нашу гипотетическую новую модель по тем же стандартам и спросим себя, какие задачи из тех, что мы считаем важными, она может решить, то, возможно, окажется, что между разложением на простые множители и NP-полной задачей их вмещается не так уж много. Опять же может существовать какая-то модель, которая позволит нам зайти чуть дальше BQP, скажем решить задачу об изоморфизме графа или задачу о скрытой подгруппе еще для нескольких неабелевых групп, но, по современным представлениям, «место» между BQP и NP-полными задачами ограничено.
Студент: Откуда вообще берутся оракулы?
Скотт: Их просто определяют. Пусть A — оракул…
Студент: Ничего себе!
Скотт: Ну да, ну да. Мне всегда странно, почему только компьютерщиков критикуют так остро за использование при поиске ответов на вопросы методик, которые имеются в их распоряжении. Вот физики говорят, что собираются провести какой-то расчет в рамках теории возмущений. «О! Конечно, что тут еще сделаешь? Это глубокая и сложная задача». Разумеется, нужно делать то, что работает. Специалисты по теоретической информатике говорят, что мы не можем пока доказать, что P ≠ NP, но мы попробуем исследовать этот вопрос в релятивизированном мире. «Это нечестно!» Представляется очевидным, что начинать всегда нужно с результатов, которые вы можете доказать, и оттуда уже двигаться дальше. Единственное возражение, которое прежде можно было выдвинуть против результатов применения оракулов, состояло в том, что некоторые из них были попросту тривиальны. Они, по существу, просто сводились к переформулированию вопроса. Но сегодня у нас появились кое-какие очень нетривиальные разделения с применением оракула. Я имею в виду, что можно очень конкретно сформулировать, для чего годятся результаты применения оракула. Приблизительно раз в месяц на сайте arxiv.org я встречаю новую статью, в которой NP-полные задачи решаются на квантовом компьютере за полиномиальное время. Должно быть, это самая простая задача в мире. Такие статьи обычно очень длинны и сложны. Но если вы знаете о результатах работы с оракулами, вам не обязательно читать эти статьи. Это очень полезное приложение. Вы можете сказать: если это доказательство верно, то оно верно и относительно оракулов, а этого не может быть, потому что нам известен оракул, для которого это неверно. Автора такой аргумент, вероятно, не убедит, но, по крайней мере, он может убедить вас.
В качестве еще одного примера я привел оракул, относительно которого класс SZK (статистический, с нулевым разглашением) не входит в BQP. Иными словами, поиск противоречий — трудная задача для квантового компьютера. Конечно, годы идут, и на глаза то и дело попадаются статьи, где авторы рассуждают о том, как находить противоречия при помощи постоянного числа запросов на квантовом компьютере. Я, не читая статью, могу сказать, что нет, так не получится, потому что не происходит ничего нерелятивизирующего. Так что оракулы существуют, чтобы подсказывать вам, какие подходы пробовать не стоит. Они направляют вас к нерелятивизирующим методикам, которые, как нам известно, в конце концов нам непременно потребуются.
Студент: К какому классу сложности принадлежите вы сами?
Скотт: Я не дотягиваю даже до полноценного P. Даже до LOGSPACE! Особенно если не выспался.
Студент: К какому классу сложности относится творчество?
Скотт: Прекрасный вопрос. Я сам только сегодня утром думал об этом. Кто-то спросил, есть ли у человека в голове оракул для NP. Может, у Гаусса или Уайлса был. Но для большинства из нас поиск доказательств — в значительной мере дело случая. Попал или промахнулся… Можно посмотреть и с другой стороны: после трех миллиардов лет естественного отбора и тысячелетий строительства цивилизации, после всех войн и остального, мы можем решить несколько примеров типа SAT — но стоит перейти к гипотезам Римана или Гольдбаха, и внезапно окажется, что это предел, что здесь мы ничего уже решить не можем.
Когда речь заходит о доказательстве теорем, нам приходится иметь дело с очень специальным случаем NP-полной задачи. Вы не просто берете какую-то произвольную формулу полиномиального по n размера, вы берете какой-то фиксированный вопрос фиксированного размера и задаетесь вопросом, имеет ли он доказательство размера n. Так что вы формируете эти примеры для доказательств той длины, что вам нужна. Но даже для таких задач нет убедительных свидетельств того, что у нас имеется какой-то общий алгоритм для их решения. Мало кто готов отказаться от общения и провести всю жизнь по-монашески, в размышлениях о математике. Наконец, таким людям удается решать кое-какие задачи и даже получать иногда за это Филдсовскую премию. Но задач, о которых все знают и которые никто не может решить, вокруг меньше не становится. Так что я бы сказал, что прежде чем вслед за Пенроузом пускаться в рассуждения о том, что математическая изобретательность человека превосходит возможности вычислений, нам следовало бы убедиться, что объективные данные подтверждают гипотезу о том, что человек хорошо умеет отыскивать доказательства. Я в этом, откровенно говоря, не убежден.
Ясно, что в определенных случаях у нас очень хорошо получается находить закономерности или брать задачи, которые кажутся трудными, и раскладывать их на более простые подзадачи. Во многих случаях это у нас получается лучше, чем у любого компьютера. Мы можем задать вопрос: «Почему так?» Это очень серьезный вопрос, но мне кажется, что ответ заключается отчасти в том, что у нас фора в миллиард лет. Миллиард лет естественного отбора снабдил нас отличным набором инструментов эвристики для решения поисковых задач определенного типа. Не всех и не всегда, но в некоторых случаях у нас действительно здорово получается. Как я уже говорил, я считаю, что NP-полные задачи не решаются эффективно в реальной Вселенной; поэтому я уверен, что не может быть машины, которая просто сможет эффективно доказать любую теорему. Тем не менее наверняка возможна машина, которая сможет пользоваться теми же творческими озарениями, какими пользуются математики-люди. Машинам не придется соперничать с Богом, только с Эндрю Уайлсом. Возможно, это проще, но это уже не относится к теории вычислительной сложности; это вопрос искусственного интеллекта.
Студент: Значит, даже если не существует способа решать NP-полные задачи за полиномиальное время, все равно можно считать, что математики-люди устаревают?
Скотт: Конечно. И после того, как компьютеры примут у нас эстафету, возможно, им тоже придется беспокоиться о том, что когда-нибудь появится NP-оракул и оставит их без работы.
Студент: Неравенства Белла, судя по всему, являются важным инструментом исследования ограничений квантовой механики. Мы знаем, что происходит в случае полностью нелокальных ящиков, но что происходит (скажем, с вычислительной сложностью), если мы допускаем уровень корреляций чуть выше, чем, скажем, дает квантовая запутанность?
Скотт: Хороший вопрос, и есть люди, которые над ним думают.
Чтобы немного показать контекст, скажу, что есть важное достижение, известное как неравенство Цирельсона[192], которое можно считать «квантовым вариантом неравенства Белла». Неравенство Белла утверждает, что Алиса и Боб могут выиграть в своеобразной игре под названием CHSH не более чем в 75 % случаев в классической вселенной, но в ~85 % случаев, если у них будут общие запутанные кубиты. А неравенство Цирельсона гласит, что даже при наличии запутанных кубитов все же есть предел возможностям Алисы и Боба: они не могут выигрывать в CHSH-игре более чем в ~85 % случаев, невзирая на тот факт, что даже 100-процентный выигрыш не позволил бы им посылать сигналы быстрее скорости света. Поэтому можно сказать, что ограничения, наложенные квантовой механикой, немного сильнее, чем им «необходимо быть», сильнее, в частности, чем ограничения, связанные с отсутствием обмена информацией.
Итак, примерно десять лет назад возникла тенденция изучения гипотетических «суперквантовых» теорий, в которых нарушалось бы неравенство Цирельсона, но все же не разрешалась бы сверхсветовая коммуникация. Простейший способ добиться этого — постулировать существование так называемых «нелокальных ящиков» — волшебных устройств, позволяющих Алисе и Бобу выигрывать CHSH-игру, скажем, в 95 % случаев вместо 85 %. Тогда можно исследовать, как эти нелокальности влияют на другие аспекты. К примеру, Брассар с соавторами[193] (опираясь на более ранний результат Вима ван Дама[194]) показали, что наличие достаточно хорошего нелокального устройства (если ошибка достаточно мала) делает сложность коммуникации тривиальной (к примеру, все проблемы коммуникации могут быть решены при помощи одного-единственного бита).
Фундаментальная проблема здесь в том, что нарушение предела Цирельсона действительно можно себе представить, то есть можно представить, что существуют нелокальные корреляции более сильные, чем позволяет квантовая механика, но констатация этого факта не дает нам модели вычисления. Я имею в виду, каковы у нас разрешенные операции? Какое пространство возможных состояний порождает возможность существования нелокальных устройств? Если бы у нас были ответы на эти вопросы, мы могли бы начать думать о вычислительной сложности в этих гипотетических мирах.
Студент: Как вам кажется, не проясняется ли слегка ситуация с классами сложности? А то появляются новые, их становится все больше…
Скотт: Для меня это как спросить у химика, не проясняется ли слегка ситуация с периодической таблицей. Может быть, азот объединится с гелием? В нашем случае даже немного лучше, чем у химиков, мы все же можем надеяться на слияние некоторых классов. Так, мы надеемся и рассчитываем, что P, RP, ZPP и BPP сольются в один класс. Мы надеемся и рассчитываем, что сольются NP, AM и MA, а IP и PSPACE уже слились. Так что да, слияния происходят, но мы также знаем наверняка, что существуют классы, которые не сольются ни при каких обстоятельствах. Так, P отличается от EXP, и из этого сразу следует, что либо P отличается от PSPACE, либо PSPACE отличается от EXP, либо то и другое одновременно. Так что не все может слиться, и это не должно никого удивлять.
Может быть, теория вычислительной сложности пошла не туда, когда стала давать всему названия в виде случайных на первый взгляд сочетаний заглавных букв. Я понимаю, что для непосвященных такие названия выглядят как шифрованные обозначения или юмор «для своих». На самом же деле мы просто говорим о разных концепциях вычислений. Время, объем памяти, рандомность, квантовость, присутствие доказателя. Число классов сложности соответствует числу разных вычислительных концепций. Так что разнообразие зоопарка сложности — всего лишь естественное отражение разнообразия мира вычислений.
Студент: Как вы считаете, BPP сольется с P?
Скотт: О да. Наверняка. У нас есть даже не одна, а несколько достаточно правдоподобных гипотез по поводу нижней оценки схем, о которых известно, что если они верны, то P = BPP. Ведь кое-кто уже в 1980-е гг. понимал, что P должен быть равен BPP. Еще тогда Яо указал, что если бы у нас были достаточно хорошие криптографические генераторы псевдослучайных чисел, то с их помощью можно было бы дерандомизировать любой вероятностный алгоритм; следовательно, P = BPP. В 1990-е гг. работа продолжилась, и тот же вывод делался из все более слабых допущений.
Помимо этого, есть и «эмпирический» вариант. Два из самых впечатляющих результатов последнего десятилетия в области теории сложности — это тест на простоту Аграваля — Кайала — Саксены (AKS), который показывает, что проверка на простоту относится к P, и теорема Рейнгольда о том, что просмотр ненаправленного графа относится к детерминистическому LOGSPACE. Так что идея взять конкретный рандомизированный алгоритм и дерандомизировать его, как мы видим, принесла значительный успех. Она как бы внушает уверенность в том, что если бы мы были достаточно умны или достаточно знали, то справились бы таким же образом и с остальными BPP-задачами. Кроме того, можно взглянуть на конкретный случай, такой как дерандомизация полиномиальной проверки на тождественность. Возможно, это будет хорошей иллюстрацией к сказанному.
Вопрос такой: если дан некоторый многочлен, к примеру x² — y² — (x + y) (x — y), то равен ли он тождественно нулю? В данном случае ответ: да. Но в задаче может фигурировать очень сложный многочлен с переменными в очень высоких степенях, и в таком случае неочевидно, как можно его проверить, даже при помощи компьютера. Если попытаться полностью развернуть выражение, можно получить экспоненциальное число слагаемых.
Однако нам известен быстрый рандомизированный алгоритм для этой задачи, а именно: просто подставляем в выражение какие-то случайные величины (над некоторым случайным конечным полем) и смотрим, соблюдается тождество или нет. Вопрос в том, можно ли этот алгоритм дерандомизировать. То есть существует ли эффективный детерминистический алгоритм для проверки тождественного равенства многочлена нулю? Если немного побиться головой об эту задачу, то довольно быстро заберешься в дебри очень глубоких вопросов алгебраической геометрии. К примеру, можете ли вы предложить небольшой список чисел, таких, что для любого многочлена p(x), описанного небольшой арифметической формулой, достаточно подставить все числа из этого списка, и если p(x) = 0 для каждого из них, то он равен нулю всюду? Вроде бы так должно быть, поскольку все, что вам, по идее, нужно сделать, это выбрать для проверки некоторое «обобщенное» множество чисел, намного превышающее размер формулы для p. К примеру, если выяснится, что p(1) = 0, p(2) = 0, …, p(k) = 0, то либо p тождественно равен нулю, либо он нацело делится на многочлены (x — 1) … (x — k). Но существует ли ненулевое произведение (x — 1) … (x — k), которое можно представить арифметической формулой много меньшего размера, чем k? Это принципиальный вопрос. Если вы можете доказать, что такого многочлена не существует, то вы открываете путь к дерандомизации проверки на тождественность многочлена нулю (а это серьезный шаг к доказательству P = BPP).
Студент: Как вы считаете, не предложат ли три индийских математика элементарное доказательство?
Скотт: Я считаю, что для этого потребуется по крайней мере четыре индийских математика! Мы уже знаем, что если удастся доказать достаточно хорошую нижнюю оценку схемы, то удастся доказать и P = BPP. Но Импальяццо и Кабанец получили результат и в другом направлении: если хотите что-то дерандомизировать, то вам придется доказывать нижние оценки схем. Для меня это объясняет отчасти, почему до сих пор никому не удалось доказать, что P = BPP. Все потому, что мы не знаем, как доказывать нижние оценки схем. Эти две задачи почти — хотя и не совсем — идентичны.
Студент: Следует ли из P = BPP, что NP = MA?
Скотт: Почти. Если вы дерандомизируете PromiseBPP, то дерандомизируете и MA. Никто не знает, как дерандомизировать BPP, не дерандомизировав при этом и PromiseBPP.
Студент: Как вы ответили бы защитнику теории разумного замысла? Так, чтобы вас не застрелили?
Скотт: Знаете, на самом деле я не уверен. Это один из тех случаев, где, возможно, идет антропный отбор. Если бы человека можно было убедить в этом вопросе объективными данными, то, наверное, его уже убедили бы? Мне кажется, мы должны смириться с тем, что есть люди, для которых главное в вере — это не ее истинность или ошибочность, но скорее какие-то другие ее качества, к примеру ее роль в обществе. Эти люди играют в другую игру, где вера оценивается по каким-то другим стандартам. Это как баскетболисту выйти играть в регби.
Студент: Может ли теория сложности сыграть какую-то роль в противостоянии эволюции и разумного замысла?
Скотт: В той мере, в какой она там нужна, можно говорить лишь о своего рода тривиальной теории сложности. К примеру, одно то, что мы считаем NP-задачи экспоненциально трудными, не означает, что мы уверены, что любой конкретный пример такой задачи (скажем, появление в ходе эволюции работающего мозга или сетчатки глаза) должен быть трудным.
Студент: Когда Стивен Вайнберг читал лекцию в Институте теоретической физики Университета Ватерлоо, известном как Институт Периметра, его спросили: «Как во все это вписывается Бог?» Он ответил, что пора отбросить религию как артефакт нашей эволюции, потерявший всю свою ценность, и что рано или поздно мы все это перерастем. Вы с ним согласны?
Скотт: Я думаю, что здесь еще немало вопросов.
Студент: Вы говорите как политик.
Скотт: Послушайте, это горячая тема, о которой написаны книги вроде «Бог как иллюзия» Ричарда Докинза…
Студент: Это хорошая книга?
Скотт: Да. Докинз увлекательно пишет, и лучше всего у него получается разносить в пух и прах негодные аргументы. Во всяком случае, можно считать, что мир был бы откровенно лучше, если бы в нем не было войн или хотя бы не было юристов, и никто ни на кого не подавал бы в суд. И есть люди, которые хотят превратить эту идею в настоящую политическую программу. Я говорю не о тех, кто выступает против конкретных войн, таких как в Ираке, по конкретным причинам, я говорю об абсолютных пацифистах. Очевидная проблема с этой точкой зрения относится к теории игр. Да, мир был бы лучше без армий, но у других-то армия есть.
Ясно, что религия играет в жизни человека какую-то роль; в противном случае она не могла бы на протяжении тысяч лет быть такой вездесущей и так успешно сопротивляться очень серьезным попыткам ее выкорчевать. Возможно, к примеру, что те, кто верит, что Бог на их стороне, храбрее в бою. Или, может быть, религия — один из факторов, которые побуждают мужчин и женщин вступать в брак и рожать много детей, и потому она адаптивна чисто с точки зрения Дарвиновой теории. Много лет назад меня поразила своеобразная ирония ситуации: в современной Америке на побережье концентрируются типичные элиты, представители которых верят в дарвинизм и зачастую остаются одинокими до тридцати-сорока лет, а то и дольше, а во внутренних районах живет столь же типичный народ, представители которого отвергают дарвинизм, но вступают в брак молодыми и рожают по 7 детей, после чего у них появляется 49 внуков и 343 правнука[195]. Значит, на самом деле конкуренция идет не между «дарвинистами» и «антидарвинистами»; это просто спор между теоретиками дарвинизма и его практиками!
Если эта идея верна, то есть если религия на протяжении всей истории человечества действительно играет эту роль: побуждает человека выигрывать войны, заводить детей и т. п., то возникает вопрос: как можно победить религию, если не посредством другой, конкурирующей религии?
Студент: Конечно, именно об этом думают люди, когда решают, верить им в некоторую религию или нет.
Скотт: Я не говорю, что все это происходит осознанно или что люди действительно обдумывают этот вопрос с такой позиции. Может быть, кто-то и обдумывает, но ведь для того, чтобы их поведение объяснялось именно так, обдумывать не обязательно.
Студент: Мы можем завести много детей без всякой религии, если захотим.
Скотт: Конечно, можем, но заводим ли, в среднем? Я не назову реальных чисел, но в современном обществе действительно есть тенденция к тому, что религиозные люди в среднем более многодетны.
Кстати, есть еще один ключевой фактор: иногда иррациональность может оказаться в высшей степени рациональной, поскольку это единственный способ доказать другому человеку, что ты действительно чему-то предан. Это как если у вас на пороге появится некто и попросит у вас 100 долларов. Вы с гораздо большей вероятностью ему их дадите, если у него будут налитые кровью глаза и невменяемый вид — вы же не знаете, что он собирается сделать! Но чтобы подобная просьба была эффективной, иррациональность и невменяемость этого человека должна быть убедительными. Нельзя просто притвориться, вы это увидите. Нужно быть глубоко, по-настоящему иррациональным и убедительно демонстрировать, что готов на все. Если вы поверите, что человек будет защищать свою честь до смерти, вы, вероятно, не станете с ним связываться.
Так что теоретически религия — это способ продемонстрировать свою преданность чему-то. Ведь человек может говорить, что верит в определенные моральные принципы, но окружающие могут считать, что эти слова ничего не стоят, и не верить ему. С другой стороны, если у этого человека длинная борода, если он каждый день молится и, кажется, действительно верит, что при нарушении этих моральных принципов его ждет вечность в аду, то ясно, что он очень дорого платит за свои убеждения. Его искренность становится куда более правдоподобной. Так что, согласно этой теории, религия работает как способ публично заявить о своей приверженности определенному набору правил. Разумеется, правила эти могут быть хорошими, а могут быть и ужасными. Тем не менее такого рода публичное обязательство подчиняться некоему набору правил, подкрепленное сверхъестественными наградами и наказаниями, представляется важным элементом социальной организации общества на протяжении тысячелетий. Именно поэтому правители надеялись, что подданные не будут бунтовать, мужья рассчитывали на верность жен, жены верили, что мужья их не бросят и т. п., и т. п.
Так что я считаю, что Докинз, Хитченс и другие паладины антирелигиозной борьбы сталкиваются именно с такими силами из теории игр и, возможно, недостаточно учитывают это в своих книгах. Их задача облегчается, безусловно, тем, что их оппоненты не могут просто выйти и сказать: «Да, конечно, все это чепуха, но вот какие важные социальные функции она исполняет!» Вместо этого апологеты религий часто прибегают к легко опровергаемым аргументам (по крайней мере со времен Юма и Дарвина), а все потому, что не могут открыто заявить свою реальную позицию, хотя она значительно сильнее, чем кажется!
В целом человечество, возможно, когда-нибудь и правда перерастет религию (если проживет достаточно долго), поскольку ее объяснительную роль теперь лучше выполняет наука. Но я убежден, что прежде, чем это произойдет, нам по крайней мере придется лучше разобраться в социальных функциях, которые исполняла религия на протяжении всей истории и до сих пор исполняет на большей части территории Земли, и, возможно, предложить какие-то альтернативные социальные механизмы для решения подобных задач.
Студент: Я просто думал, есть ли еще случаи, когда иррациональность может быть предпочтительнее рациональности.
Скотт: И как результат?
Студент: Особенно при недостатке информации. Скажем, если политик чему-то предан и позже не изменит своим идеалам, то вы можете ощущать большую уверенность, что он выполнит свои обещания.
Скотт: Потому что у него есть убеждения. Он верит в то, что говорит. Для большинства избирателей сам факт веры важнее, чем ее содержание.
Студент: Я не уверен, что это соответствует общественным интересам.
Скотт: Да, в этом-то и проблема! Но как разубедить людей, овладевших искусством рациональной иррациональности? Сказав: «Нет, погодите, на самом деле все не так»? Вы что, шутите?
Или еще пример: бар знакомств. Успех там имеют те, кто лучше других умеют убедить себя (по крайней мере на какое-то время) в некоторой лжи: «Я здесь самый крутой» или «Я здесь самая соблазнительная». Это очень наглядный пример ситуации, когда иррациональность в определенном смысле лучше рациональности.
Студент: Обычно приводят пример, что если вы идете на таран и ждете, кто первый отвернет, то полезно просто сломать руль, чтобы он не поворачивался.
Скотт: Именно.
Студент: Почему информатика не относится к физике?
Скотт: Это объясняется отнюдь не философией, а скорее историей. Когда-то специалистами по теоретической информатике были либо математики, либо инженеры-электрики. Когда такой специальности не было, те, кто пошел бы учиться информатике, шли либо в математику, либо в электротехнику. Физике и так есть чем заняться; кроме того, чтобы стать физиком, нужно изучить уйму всякой всячины, которая вам, может, и не нужна, если вы просто хотите писать программы или даже размышлять о теории вычислений. Пол Грэм сказал, что информатика — это не столько единая дисциплина, сколько группа людей, объединившихся по исторической случайности, как когда-то Югославия[196]. Есть «математики», есть «хакеры», есть «экспериментаторы», и мы просто объединяем их всех на одной кафедре и надеемся, что они будут общаться между собой хотя бы иногда. Но я считаю (это уже клише), что границы между теоретической информатикой, математикой, физикой и т. п. будут все больше размываться и становиться все более формальными. Ясно, что территория огромна, но совершенно неясно, где провести границы.