Сон разума. Математическая логика и ее парадоксы
Шрифт:
* * *
СТИРАЛЬНЫЕ МАШИНЫ С НЕЧЕТКОЙ ЛОГИКОЙ
Чтобы оптимизировать длительность и качество стирки, полезно точно указать, является одежда очень грязной, слегка грязной или практически чистой. Простейшие стиральные машины с нечеткой логикой присваивают каждой загрузке белья значение загрязнения от 0 до 1. Затем к фиксированному интервалу стирки продолжительностью в десять минут добавляется определенное время в зависимости от степени загрязнения одежды. Машина может, например, определить, что для чистого белья (0) достаточно базового времени стирки, а для очень грязного (1) — на две минуты больше. Следовательно, если мы положим в стиральную машину слегка грязную рубашку, продолжительность стирки увеличится на одну минуту. В других, более сложных моделях, с целью экономии электроэнергии учитывается степень жирности (жирные пятна отстирываются тяжелее других) и вес загруженного белья.
* * *
«Любовь»
В первом приближении мы можем определить сложность как число операций, необходимых для решения задачи. Представим коммивояжера, которому нужно посетить несколько городов, после чего вернуться в исходный. Следовательно, его целью будет максимально сократить пройденный путь. Если этими городами будут, например, Париж (П), Лондон (Л), Берлин (Б) и Рим (Р) и коммивояжер начинает поездку в Париже, то его секретарь может составить расписание шестью разными способами: ПЛБРП, ПЛРБП, ПБЛРП, ПБРЛП, ПРБЛП и ПРЛБП. Учитывая примерные расстояния Париж — Лондон (455 км), Париж — Берлин (1050 км), Париж — Рим (1435 км), Лондон — Берлин (1095 км), Лондон — Рим (1855 км) и Берлин — Рим (1515 км), можно рассчитать общую длину каждого маршрута и выбрать кратчайший из них:
Учитывая данные, представленные в таблице, оптимальным будет маршрут Париж — Лондон — Берлин — Рим — Париж или он же, но в обратном направлении: Париж — Рим — Берлин — Лондон — Париж. Но что произойдет, если коммивояжеру нужно будет посетить не три города, а четыре, пять или любое другое количество городов? Для решения этой задачи всего для двадцати городов компьютеру средней производительности потребуется 80 тысяч лет, и в свете этого возможная потеря времени от неправильного выбора маршрута уже несущественна.
Если мы попытаемся решить задачу «грубой силой», то потребуется рассмотреть уже не шесть случаев — их число будет равно произведению 1·2·3· … и т. д. до 20. Запись этого числа содержит девятнадцать цифр. В математике это число называется 20 факториал и обозначается восклицательным знаком после числа. Так, 3! = 1·2·3 = 6; 4! = 1·2·3·4 = 24; в общем случае n! равен произведению первых n натуральных чисел.
Факториал — это пример функции, вычислить значение которой теоретически очень просто, однако на практике компьютеры пасуют перед этой задачей. Как мы уже отмечали в предыдущей главе, все рекурсивные функции являются вычислимыми. Напомним, что функция является рекурсивной, если значение f(n) можно вычислить на основе значений, которые принимает эта функция для чисел, меньших n. Факториал — это классический пример рекурсивной функции, так как если мы хотим вычислить 4! = 1·2·3·4, мы можем сначала найти произведение 1·2·3, а затем умножить его на 4. Но что представляет собой произведение 1·2·3? Оно равно 3! таким образом, если известно значение 3! то чтобы найти 4! достаточно одной операции. В общем случае n! = (n — 1)!·n — это доказывает, что факториал является рекурсивной, а следовательно, и вычислимой функцией. Для машины Тьюринга, способной работать бесконечное время, вычисление n! не представляет трудностей. Но на практике значения факториала возрастают столь быстро, что с ними вскоре становится невозможно работать.
График, показывающий рост значений факториала.
Предыдущий пример был бы не более чем любопытным фактом, если бы факториал не описывал число перестановок элементов конечных множеств, то есть число способов, которыми можно упорядочить их элементы. Так, фразы «3! = 6» и «множество {1, 2, 3} можно записать шестью разными способами (123, 132, 213, 231, 312 и 321)» содержат одинаковую информацию. Так как примитивный метод решения многих задач, схожих с задачей коммивояжера, требует последовательного перебора всех элементов множества, которое может быть достаточно большим, то скорость, с которой возрастают значения факториала, имеет фатальные последствия.
* * *
ИЗОБРЕТАТЕЛЬ ШАХМАТ
По легенде, персидский царь хотел наградить изобретателя шахмат и подарить ему все, что он пожелает. Тогда мудрец удивил царя просьбой, которая показалась скромной: он хотел получить одно зерно за первую клетку доски, два — за вторую, четыре — за третью и т. д. — на каждой клетке доски должно было находиться в два раза больше зерен, чем на предыдущей. Эта просьба показалась царю насмешкой, и он, рассерженный, повелел слугам немедленно исполнить просьбу мудреца и выслать ему столько зерна, сколько тот просил. Каково же было его удивление, когда один из советников на следующий день сообщил ему, что для этого не хватит зерна в амбарах всего мира. Функция, принимавшая значения 1, 2, 4, 8… возрастала столь быстро, что общее число зерен составило 18446744073 709551615.
* * *
В одном из простых определений сложными называются задачи, решение которых требует выполнения сопоставимого числа операций, а простыми считаются те, которые разрешимы не только с теоретической, но и с практической точки зрения, то есть в разумное время. Эти задачи часто обозначаются буквой Р (по первой букве английского слова «полином»), так как число операций для их решения примерно равно некоторому многочлену от времени выполнения.
Ученые заметили, что существуют задачи, найти решение которых очень сложно, а подтвердить его правильность относительно просто. Вернемся к примеру с отелем из главы 2, который на этот раз содержит конечное число комнат. Предположим, что группа из четырехсот человек хочет остановиться в отеле в те дни, когда там будет свободно всего сто номеров. Выбрать сто человек из четырехсот, не следуя какому-либо критерию, очень просто, однако заявка от группы сопровождалась одной странной просьбой: некоторые путешественники настолько не ладили друг с другом, что их нельзя было размещать в соседних номерах. Не стоит и думать, что эту задачу можно решить перебором всех возможных выборок ста человек из четырехсот, но при этом для любого предложенного решения достаточно будет подтвердить, что никакие два путешественника, которые не ладят друг с другом, не будут поселены в соседние номера. С этой задачей сможет справиться администратор отеля даже без помощи компьютера всего за несколько часов. Такие задачи, которые сложно решить, но легко проверить, математики относят к классу NP.
Пока что мы говорили о сложности задач как о неотъемлемой части их формулировки. Эта точка зрения априори ошибочна, так как сложной или простой является не задача сама по себе, а наш способ ее решения. Возможно, найденное нами решение требует выполнения множества операций, но при этом существует другое, более простое. В этом случае наше решение относится к классу NP, в то время как сама задача — к классу Р. Решение задачи о коммивояжере заключалось в переборе всех возможных маршрутов. Однако в таблице показано, что при смене порядка обхода городов на противоположный длина маршрута не меняется. Следовательно, выбор маршрута Париж — Лондон — Берлин — Рим — Париж ничем не отличается от маршрута Париж — Рим — Берлин — Лондон — Париж, поэтому достаточно рассмотреть половину исходных случаев. На практике подобное упрощение не слишком полезно, так как половина огромного числа по-прежнему остается огромным числом. Этот аспект имеет скорее философский характер: если в первом решении мы упустили из вида столь тривиальную деталь, то сколько подобных моментов мы еще не учли? Мы сказали, что наша исходная точка зрения априори ошибочна, поскольку неизвестно, существуют ли задачи, для которых сложность является неотъемлемым свойством их формулировки, а не решений. К числу таких задач, возможно, относится задача о коммивояжере, пока что никому не удалось доказать, что все ее решения являются сложными.