Изменчивая природа математического доказательства. Доказать нельзя поверить

Естественно рассматривать построения Пенроуза с точки зрения теоремы Гёделя о неполноте. В любой логической системе, которая не проще арифметики, найдутся истинные утверждения, недоказуемые в рамках этой системы. Поэтому компьютер всегда будет ограниченным в своих достижениях, какой язык и какую систему логики мы бы ни использовали. Человек может работать с утверждением Гёделя эвристически, или собирая данные, или ограничиваясь правдоподобными рассуждениями, или привлекая вероятностные соображения. Человек может шагнуть за рамки логической системы и воспользоваться любыми средствами для построения доказательства. А компьютер не сможет подойти к задаче вообще. Компьютерные специалисты (см.[MCC]) любят указывать, что компьютерный язык LISP очень подходит для работы с явлением Гёделя. И мы можем строить системы, которые избегают гёделевских утверждений. Однако рассуждение Гёделя о неполноте имеет подлинный философский вес.

Легко представить себе, что для многих классически образованных математиков-теоретиков очень важно овладеть идеями Пенроуза. Мало кто из нас хочет верить, что наступит день, когда нас вытеснят машины, работающие на силиконовых чипах. В сообществе специалистов по компьютерным наукам есть и те, которые с энтузиазмом Пенроузу оппонируют. Четко и занимательно написанная статья [MCC] — пример аргументов, противостоящих идеям Пенроуза.

Сообщество ученых, занимающихся проблемами ИИ, продолжает процветать — в МИТ и Калтех, например, есть энергичные группы. В этой дисциплине, без сомнения, имеется много интересных вопросов. Но если вы посетите встречи специалистов ИИ, то поразитесь, как много времени они проводят, споря об определениях. Как математики мы понимаем важность формулирования верных определений, с тем чтобы все дальнейшее из них следовало. Но этому этапу мы уделяем небольшое время, а затем двигаемся дальше. В предмете искусственного интеллекта больше органических компонентов, ведь это попытка применить математические принципы к функционированию человеческого мозга — и поэтому на него воздействуют силы и давления, к которым теоретическая математика нечувствительна. Роджер Пенроуз задел за живое, размышляя об усилиях ИИ-сообщества. Его идеи звучат в математических науках.

11.7 Задача P/NP

Теория сложности — это инструмент для измерения того, насколько сложна задача (с вычислительной точки зрения) или сколько времени компьютер будет работать над ее решением. Как уже в этой книге было сказано, вычисления (и теория вычислений) занимают все больше места в современной математике. Особый интерес представляет вопрос о том, какие задачи можно решить за разумное время, а какие потребуют неопределенного или практически нереального времени. Последние называют вычислительно сложными, а первые — осуществимыми. Например, задача разложения на множители 200-значного целого числа вычислительно дорогая. Ее решение может занять годы, даже на самом быстродействующем компьютере. Но, допустим, вместо этой задачи я ставлю другую:

Дано 200-значное число N. Утверждается, что два 100-значных числа p и q являются его простыми делителями. Проверьте это утверждение, пожалуйста.

А вот эта задача занимает всего несколько секунд (они будут израсходованы в основном на то, чтобы ввести числа в компьютер).

Здесь мы рассмотрим вопросы, относящиеся к задаче NP-полноты. Многие считают, что это самая важная задача в математике и компьютерных науках. У нее есть далеко идущие следствия, касающиеся того, что мы можем делать с компьютерами сейчас и что мы сможем делать с ними в будущем. Многие фундаментальные идеи в криптографии опираются на вопросы вычислительной сложности. В этом разделе мы обсудим некоторые из этих идей. 

11.7.1 Сложность задачи

Теория сложности — это средство измерения того, насколько задача сложна или сколько компьютерного времени потребуется для ее решения. Мы измеряем сложность следующим образом. Допустим, что в формулировку частного случая задачи входят n заданных начальных значений. Сколько шагов[122] займет ее выполнение (как функция от n)? Можем мы построить эффективную оценку числа этих шагов, которая работала бы для асимптотически больших значений n?

Рассмотрим пример: n игральных карт рассыпали на пол. Ваша задача — собрать их по порядку. Сколько шагов займет этот процесс?

Не более чем за n шагов (просто проверив каждую карту) вы сможете положить на место первую карту. Не более чем за n-1 шагов вы положите на место вторую карту, и не более чем за n-2 — третью. И так далее. В конце концов, вам потребуется не более