Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Третий вопрос: почему распределение, рожденное этим алгоритмом, будет стабильным?

Верно: потому что если бы это было не так, то возникла бы одна семейная пара (скажем, Боб и Алиса) и другая семейная пара (скажем, Чарли и Ева), такие, что и Боб, и Ева предпочитают друг друга своим супругам. Но в таком случае Боб должен был сделать предложение Еве прежде, чем Алисе. И если Чарли тоже сделал предложение Еве, то Ева тоже сразу дала бы понять, что предпочитает Боба. Возникает противоречие.

В частности, мы показали, как и было обещано, что существует стабильное распределение на пары, а именно распределение, полученное посредством алгоритма Гейла — Шейпли.

Задачи

1. Мы видели, что задача 3-SAT относится к NP-полным. Напротив, оказывается, что задача 2-SAT — вариант, в котором в каждом предложении разрешены лишь две переменные, — решается за полиномиальное время. Объясните, почему.

2. Вспомним, что EXP — это класс задач, решаемых за экспоненциальное время. Можно определить также класс NEXP: класс задач, для которых ответ «да» может быть проверен за экспоненциальное время. Иными словами, NEXP для EXP то же самое, что NP для P. Далее, мы не знаем, верно ли P = NP, и не знаем также, верно ли EXP = NEXP. Но мы точно знаем, что если P = NP, то EXP = NEXP. Почему?

3. Покажите, что P не равняется SPACE(n) (множеству задач, решаемых с использованием линейного объема памяти). Подсказка: вам не нужно доказывать, что P не входит в SPACE(n) или что SPACE(n) не входит в P, нужно доказать только, что верно то или другое.

4. Покажите, что если P = NP, то существует алгоритм полиномиального времени, позволяющий не только определить, является ли булева формула выполнимой, но и найти входную строку, для которой она выполняется, если таковая существует.

5. [Повышенной сложности.] Приведите в явном виде алгоритм, позволяющий найти входную строку (если таковая существует), для которой выполняется формула, и выполняемый за полиномиальное время, при условии, что P = NP. (Если формула невыполнима, ваш алгоритм может вести себя произвольным образом.) Иными словами, приведите алгоритм для задачи 4, который можно реализовать и выполнить прямо сейчас, без привлечения какой бы то ни было подпрограммы, которая, как вы полагаете, существует, но которую вы не в состоянии описать.

7. Случайность

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

Конечно, если вы хотите изучать квантовые вычисления, то первым делом вам придется разобраться в рандомизированных вычислениях. Я имею в виду, что квантовые амплитуды только тогда становятся нам интересны, когда отражают какое-то поведение, которое не отражают классические вероятности: контекстуальность, интерференцию, запутанность (в противовес корреляции) и т. п. Так что мы не можем даже начать разговор о квантовой механике, не поняв сначала, с чем, собственно, мы ее сравниваем.

Итак, что такое случайность? Вообще-то это глубокий философский вопрос, но я человек простой. Поэтому мы имеем некоторую вероятность p, представляющую собой действительное число в единичном интервале [0, 1]. Это и есть случайность.

Но разве не было в этой области крупного достижения в 1930-е гг., когда Колмогоров подвел под вероятность аксиоматический базис? Да, было! Но в этой главе нас интересует только распределение вероятностей по конечному числу событий, так что тонкие вопросы интегрируемости, измеримости и т. п. у нас не возникнут. На мой взгляд, теория вероятностей — это еще один пример области, в которой математики сразу же уходят в пространства бесконечных размерностей, чтобы решить для себя проблему безделья и найти побольше нетривиальных задач для решения! И это прекрасно — чем бы дитя ни тешилось. Я вовсе не критикую. Но нам в теоретической информатике вполне хватает возни с выбором из 2n вариантов. Выбор из 2ℵ₀ нужен нам, как пятое колесо в телеге.

Ну хорошо, пусть нам дано некоторое «событие» A — скажем, что завтра пойдет дождь, и мы можем говорить о действительном числе Pr [A], лежащем в [0, 1], которое представляет собой вероятность того, что A произойдет. (Или, скорее, вероятность, с которой мы думаем, что A произойдет, — но я уже говорил вам, что я человек простой.) Кроме того, вероятности различных событий состоят в некоторых очевидных отношениях, но нам, возможно, полезно будет посмотреть их в явном виде, на случай, если вы никогда их не видели.

Во-первых, вероятность того, что A не произойдет, равна 1 минус вероятность того, что A произойдет:

Pr[не (A)] = 1 — Pr[A].

Согласны? Я так и думал.

Во-вторых, если у нас есть два события, A и B, то

Pr[A или B] = Pr[A] + Pr[B] — Pr[A и B].

В-третьих, непосредственное следствие из вышесказанного, известное как неравенство Буля, или аддитивное неравенство или граница объединения:

Pr[A или B] ≤ Pr[A] + Pr[B].

Или на обычном языке: если маловероятно, что вы утонете, и маловероятно, что станете жертвой удара молнии, то у вас хорошие шансы на то, что вы и не утонете, и не погибнете от удара молнии, независимо от того, повышает или понижает удар молнии ваши шансы утонуть. Один из немногих поводов для оптимизма в этой жизни.

Несмотря на тривиальность, граница объединения является, вероятно, самым полезным фактом во всей теоретической информатике. Я лично использую это свойство раз по 200 в каждой своей статье.

Что еще? Если задана случайная числовая переменная X, то математическое ожидание X, или E[X], определяется как Σk Pr[X = k]k. Тогда если даны две произвольные случайные переменные X и Y, то