Читать «Золотой билет» онлайн - страница 33
Лэнс Фотноу
Математика
В 1928 году выдающийся немецкий математик Давид Гильберт сформулировал свою знаменитую проблему разрешимости –
Допустим, у нас есть некое математическое утверждение и нам требуется найти относительно короткое доказательство, которое, к примеру, уместилось бы в тоненькой книжке. Эта задача лежит в классе NP, поскольку оценить длину уже имеющегося доказательства легко, а создать его совсем не просто; будь у нас на руках все возможные доказательства, мы нашли бы искомое обычным перебором. Вот почему математики, которым удалось придумать какое-нибудь хитрое доказательство, становятся знаменитыми.
Определить условия истинности логического выражения тоже иногда бывает очень трудно, даже если выражение это не слишком сложное. Из данной проблемы выросла целая теория, связавшая вместе большинство NP-задач; подробнее мы познакомимся с ней в следующей главе.
Решение головоломки «Путешествие по додекаэдру»
Рис. 3.18. Обход додекаэдра
Глава 4. Самые трудные задачи класса NP
Психолог проводит эксперимент над математиком. Математика посадили в маленький деревянный сарай; на полу лежит лучина для растопки, рядом стоит стол, а на нем – ведро с водой. Психолог поджигает лучину. Математик хватает ведро и заливает огонь водой.
Пока все идет по плану. Психолог повторяет эксперимент, изменив одну незначительную деталь. Математика снова сажают в сарай; внутри тот же стол, на полу такая же лучина, есть и ведро с водой, но стоит оно не на столе, а рядом с лучиной на полу. Психолог поджигает лучину. Математик хватает ведро и ставит его на стол. В результате сарай выгорел дотла; математика, к счастью, успели в последний момент вытащить.
«Почему вы просто не залили огонь?!» – спрашивает психолог. «Я свел новую задачу к уже решенной», – отвечает математик.
