Три вида задач
Разговоры о компьютерах обычно строятся на молчаливом допущении: машины становятся мощнее, значит, рано или поздно решится что угодно.
Допущение неверно, и неверно двумя разными способами.
Задачи делятся на три группы, и границы между ними проведены не мощностью железа, а математикой.
Первая: решаются быстро. Отсортировать миллион чисел, найти кратчайший путь по карте, проверить, есть ли слово в словаре. Тут всё хорошо: растёт задача — время растёт умеренно.
Вторая: решаются, но не успеем. Решение существует и известно, как его искать. Просто искать придётся дольше, чем существует Вселенная.
Третья: не решаются никогда. Доказано, что алгоритма нет. Не «пока не нашли» — а нет и не будет.
Вторая и третья группы — самое интересное, и они меняют представление о том, что вообще может машина.
Что такое алгоритм
Сначала договоримся о слове, потому что дальше всё на нём держится.
Алгоритм — это точная последовательность действий, приводящая к результату за конечное число шагов. Ключевых требований три: однозначность (на каждом шаге понятно, что делать), конечность (когда-нибудь кончится), результативность (в конце получится ответ).
Слово происходит от имени Аль-Хорезми, среднеазиатского математика IX века: его книгу об индийском счёте перевели на латынь, и искажённое имя автора стало обозначать способ вычисления вообще.
Важно, что алгоритм не обязан быть компьютерным. Рецепт борща, инструкция по сборке шкафа, способ деления в столбик — алгоритмы. Компьютер просто выполняет их быстро и не отвлекаясь.
Почему быстрая машина не спасает
Теперь ключевая идея, которую стоит понять один раз и на всю жизнь.
Важно не то, сколько времени алгоритм работает на конкретной задаче. Важно, как это время растёт, когда задача становится больше.
Сравним два роста.
Алгоритм A: задача вдвое больше — времени вдвое больше. Было 10 городов и секунда — стало 20 городов и две секунды. Удвоил мощность машины — удвоил посильный размер задачи.
Алгоритм B: каждый новый элемент удваивает время. Было 10 элементов и секунда. Стало 20 — тысяча секунд. Стало 30 — миллион. Стало 60 — миллиард миллиардов секунд, это в сотни миллионов раз дольше возраста Вселенной.
И вот главное. Удвой мощность компьютера для алгоритма B — и ты выиграешь один элемент. Не вдвое больше, а плюс один. Сделай компьютер в тысячу раз быстрее — выиграешь десять элементов.
Отсюда вывод, который обычно и удивляет: против такого роста железо бессильно. Тут нужен другой алгоритм, а не другая машина.
Задача, которую все знают
Классический пример задачи из второй группы — про коммивояжёра.
Есть города и расстояния между ними. Надо объехать все по одному разу и вернуться, потратив как можно меньше.
Звучит проще некуда. Решение очевидно: перебрать все маршруты и выбрать короткий.
Теперь посчитаем. Для 5 городов маршрутов десятки. Для 10 — сотни тысяч. Для 20 — больше, чем секунд прошло с начала Вселенной. Для 60 — число, для которого не хватит атомов в наблюдаемой Вселенной, если записывать его камешками.
Заметь: задача не выдуманная и не редкая. Её решают каждый день — развозя посылки, планируя маршруты автобусов, сверля отверстия в плате.
Как же с ней справляются? Никак — в смысле точного решения. С ней мирятся:
- Ищут не лучший маршрут, а хороший: на несколько процентов хуже оптимального, зато за секунду.
- Пользуются приёмами, которые обычно работают, хотя гарантий не дают.
- Сокращают перебор, заранее отбрасывая заведомо плохие ветки.
И это типичная инженерная развязка: когда точный ответ недостижим, меняют требование — с «наилучшего» на «достаточно хорошего».
Задачи, у которых решения нет вовсе
Теперь третья группа, и она интереснее всего, потому что речь не о нехватке времени.
В 1936 году Алан Тьюринг доказал, что существует задача, для которой алгоритма нет в принципе. Называется она проблемой остановки.
Формулировка простая. Требуется написать программу, которая, получив на вход любую другую программу и её данные, отвечает: остановится ли та когда-нибудь или будет работать вечно.
Задача полезная: такая программа ловила бы зависания до запуска.
Тьюринг доказал, что её не существует. Ход доказательства можно передать без математики.
Почему это не повод унывать
Из сказанного легко сделать мрачный вывод. Он был бы неверным.
Невозможность в общем случае не значит невозможность в частных. Программ, про которые нельзя сказать, зациклятся ли они, полно в теории; на практике анализаторы кода прекрасно ловят огромную часть зависаний. Просто они не обещают поймать все.
Приблизительное часто достаточно. Маршрут на процент хуже идеального доставит посылки ничуть не хуже.
Ограничение — это знание. Понимать, что задача неразрешима, полезнее, чем годами искать решение. Огромное количество сил в истории математики было потрачено на поиски того, чего нет, — пока не доказали, что нет.
Границы двигаются иначе, чем кажется. Успехи в трудных задачах приходят не от роста мощности, а от новых подходов: другой алгоритм, другая постановка, отказ от точности ради скорости.
Что из этого стоит унести
Несколько мыслей, полезных вне программирования.
Спрашивай, как растёт. Не «сколько это займёт сейчас», а «что будет, когда станет вдвое больше». Вопрос отделяет решения, которые доживут до роста, от тех, что рухнут.
Различай «трудно» и «невозможно». Это разные вещи, и путать их дорого в обе стороны: упорствовать в невозможном и сдаваться перед трудным одинаково неприятно.
Помни, что доказанная невозможность — результат. В отличие от «у меня не получилось», она говорит нечто о мире, а не о тебе.
Меняй требование, если не сходится. Когда точного ответа нет, почти всегда существует вопрос попроще, ответ на который решает исходную задачу практически. Умение найти такой вопрос — и есть инженерия.
Задачи, которые легко проверить и трудно решить
Есть особая порода задач, о которой стоит сказать отдельно, — на ней держится половина современной криптографии.
Заметь асимметрию на простом примере. Головоломку судоку трудно решать и мгновенно проверять: увидев заполненную сетку, ты за минуту убедишься, что всё верно. То же с разложением числа на множители: найти множители большого числа тяжело, а перемножить найденное и сверить — секунда.
Класс таких задач — «решение ищется долго, проверяется быстро» — обозначают буквами NP. Задачи, которые и решаются быстро, — P.
И вот главный открытый вопрос всей информатики: совпадают ли эти два класса? Иначе говоря, верно ли, что у всякой задачи с быстрой проверкой есть и быстрое решение, просто мы его не нашли?
Почти все специалисты считают, что не совпадают, — но доказательства нет уже полвека. За него назначена премия в миллион долларов, и она не выплачена.
Практическая сторона вопроса огромна. Если вдруг окажется, что классы совпадают и быстрый способ есть, рухнет вся защита, построенная на трудности разложения чисел, — то есть банковские переводы, подписи, защищённая связь. Одновременно решатся задачи планирования, укладки, расписаний, на которых человечество теряет миллиарды.
Любопытный поворот: мы живём в мире, безопасность которого основана на нерешённой математической задаче. Не на доказанной невозможности — а на том, что решение очень долго ищут и не находят.
Главное в трёх строчках
- Важна не скорость алгоритма, а то, как растёт время при увеличении задачи: против показательного роста рост мощности машины бессилен — удвоение мощности добавляет один элемент.
- Часть практических задач точно не решается за разумное время, и с ними мирятся, заменяя «наилучший ответ» на «достаточно хороший».
- Есть задачи, для которых алгоритма не существует вовсе, и это доказано: проблема остановки неразрешима не из-за нехватки мощности, а из-за логического противоречия.