Золотой билет

Любая компьютерная программа либо остановится и выдаст некий результат, либо будет работать бесконечно. Допустим, у нас есть алгоритм, который определяет, останавливается программа или нет. Применим его к самому себе и создадим программу, представленную на рисунке ниже.

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

Рис. 7.4. Программа

А нельзя ли примерно таким же способом доказать, что некоторые задачи не могут быть решены эффективно, т. е. не принадлежат классу P, в котором для любой задачи существует эффективный алгоритм? Конечно же, можно!

Для начала определим алгоритм Q, который принимает на вход код программы R и решает следующую задачу:

• Если программа R, получив на вход свой собственный код, за полиномиальное время выдает ответ «Да», ответить «Нет».

• В противном случае ответить «Да».

Теперь возьмем произвольный эффективный алгоритм S. Очевидно, что Q(S) ответит «Да» в том и только в том случае, когда S(S) ответит «Нет», а это значит, что ни один эффективный алгоритм никогда не совпадет с алгоритмом Q.

Несмотря на это, алгоритм Q вполне корректный, и задача, которую он выполняет, разрешима, – вот только за полиномиальное время с ней не справиться.

Раз Q не принадлежит классу P, тогда, если бы мы доказали, что Q лежит в NP, т. е. любое заданное решение быстро проверяется, это означало бы, что P ≠ NP, и проблема тысячелетия была бы решена.

Никто не знает, принадлежит ли Q классу NP; на самом деле это очень мало вероятно. По этой причине (а также по ряду других) любой «парадоксальный» подход к решению проблемы P и NP почти наверняка потерпит неудачу – по крайней мере, если с его помощью пытаться так вот «в лоб» доказать неравенство P и NP.

Схемы

В основе любого современного вычислительного устройства лежит интегральная схема.

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

Для начала рассмотрим один электрический провод, на который подается либо высокое напряжение, либо низкое. Возможны только два значения, интерпретируемые обычно как наличие тока или его отсутствие; эти значения кодируют два состояния – единицу и ноль, или «истину» и «ложь». Количество информации, передаваемое таким двузначным сигналом, получило название «бит» (англ. bit – сокращение от binary digit, т. е. «двоичная цифра»).

Рис. 7.5. Интегральная схема. Фото любезно предоставлено Пенсильванским университетом

Сам по себе провод – или даже несколько отдельных проводов – мало на что способны. Если мы хотим организовать какое-нибудь вычисление, то должны преобразовывать идущие по проводам сигналы. Простейший метод – инвертировать входное напряжение, т. е. реализовать логический вентиль «НЕ».

Рис. 7.6. Вентиль «НЕ»

Если на входе вентиля, т. е. слева от элемента «НЕ», будет высокое напряжение, на выходе оно станет низким, и наоборот.

Занимаясь каждым проводом в отдельности, полноценную схему не составить: на самом деле провода нужно специальным образом комбинировать. Вентиль «И» принимает на вход два или более сигнала и преобразует их в один; на выходе будет единица, если на все входы подается единица. Вентиль «ИЛИ» также принимает на вход два или более сигнала и преобразует их в один; на выходе будет единица, если хотя бы на один из входов подается единица.

Рис. 7.7. Вентили «И» и «ИЛИ»

Из таких простейших базовых элементов можно строить схемы, реализующие более сложные операции. Например, «исключающее ИЛИ» выдает единицу, когда ровно на один из входов подается единица.

Рис. 7.8. Вентиль «Исключающее ИЛИ»

Любую, даже самую сложную, функцию можно реализовать схемой из элементов «И», «ИЛИ» и «НЕ». Вернемся к вопросу о клике – группе жителей Королевства, в которой все дружат между собой. Чтобы определить, дружат ли Алекс, Боб и Венди, мы можем воспользоваться вентилем «И».

Рис. 7.9. «И» с тремя входами

Чтобы узнать, есть ли в компании из пяти человек – Алекс, Боб, Венди, Гарри и Диана – клика размера три, мы можем построить схему, изображенную на рис. 7.10.

В этой схеме десять элементов «И». Каждый элемент соответствует одной из десяти потенциальных клик размера три в нашей группе. А что, если в группе не 5 человек, а 20000? И нам нужно найти клику размера 50? Действуя так же, «в лоб», мы получим невероятно огромную схему, содержащую