Читать «Золотой билет. P, NP и границы возможного» онлайн - страница 69

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

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

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

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

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

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

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

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

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

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

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

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

3 481 788 616 673 927 174 126 704 329 430 033 822 428 741 136 969 800 292 509 234 146 086 195 855 824 730 457 281 170 250 134 309 383 506 694 008 809 661 825 431 661 561 845 957 650 386 210 936 569 600

элементов «И».

Рис. 7.10. Схема для клики размера три

Вы спросите, причем тут классы P, NP и вопрос об их равенстве? Дело в том, что для любой задачи из P, т. е. задачи, для которой существует эффективный алгоритм, существует также относительно небольшая схема из элементов «И», «ИЛИ» и «НЕ», которая ее решает. Если мы докажем, что некоторую задачу из NP (например, задачу о клике) нельзя решить при помощи небольшой схемы, это будет означать, что P ≠ NP.

Существуют ли маленькие схемы для задачи о клике? Равны классы P и NP или не равны? Вопросы эти очень тесно взаимосвязаны, и ответа на них ученые пока не знают; однако сейчас уже мало кто верит, что задача о клике реализуется маленькой схемой, как, впрочем, и в то, что P = NP.