Читать «Золотой билет» онлайн - страница 72

По большей части представляемые доказательства абсолютно нечитабельны или пестрят глупейшими ошибками, и научное сообщество их просто-напросто игнорирует. Однако в случае с Деолаликаром дело приняло совсем другой оборот: у ученого уже имелся целый ряд научных публикаций, а качество представленной работы выгодно отличало его от других претендентов. Некоторые специалисты полагали, что труд Деолаликара заслуживает самого пристального рассмотрения. Из-за этого твиты и блоги запестрели преждевременными сообщениями о том, что проблема тысячелетия решена. Доказательство изучали известные математики и кибернетики; в результате всплыли как мелкие и средние недочеты, так и серьезные изъяны. Уже 16 августа – всего через десять дней после выхода препринта Деолаликара – газета New York Times опубликовала статью под названием Step 1: Post Elusive Proof. Step 2: Watch Fireworks, в которой описывалась вся эта история. К тому времени научное сообщество пришло к единому мнению: доказательство принять нельзя, поскольку в нем содержатся серьезные ошибки. Вопрос о равенстве P и NP по-прежнему оставался открытым.

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

Допустим, вы уверены, что решили проблему равенства P и NP, и уже потираете руки в предвкушении чека на миллион долларов от Математического института Клэя. Не спешите радоваться: с вероятностью 99,9 % доказательство окажется неверным. Попробуйте понять, что с ним не так; ищите ошибку – и ваши поиски почти наверняка увенчаются успехом.

Давайте разберем несколько типичных ошибок, встречающихся у тех, кто думает, что все доказал.

Вероятно, первой неудачной попыткой доказать неравенство P и NP можно считать работу средневекового итальянского математика Джероламо Кардано – одного из первопроходцев в области теории вероятностей. В 1550 году Кардано разработал новую систему шифрования сообщений, которая, по его мнению, была очень надежной, поскольку для подбора ключа требовалось проверить огромное число вариантов. На самом деле взломать систему было не так уж сложно, ведь для расшифровки засекреченного сообщения перебирать все возможные варианты вовсе не обязательно.