«Задачи бывают двух типов:
научные проблемы и тривиальные упражнения
».
(Перефразировка одной классической цитаты).

В теории сложности алгоритмов есть такое понятие «труднорешаемая задача». Это не такая задача, решить которую трудно, а такая, решить которую эффективно не получается. И не получается не потому, что интеллект не позволяет или руки кривые, а потому, что это в принципе невозможно сделать, имея в распоряжении даже весь набор знаний и инструментов, собранный человечеством к этому моменту. Но знания растут, а инструменты меняются, поэтому одни задачи из трудных превращаются в простые упражнения, и на их место приходят другие.

В данной статье я собираюсь порассуждать о труднорешаемых задачах. Если кому-то нужно узнать классификацию трудных задач и лежащую в ней теорию, следует обратиться к книге М. Гэри и Д. Джонсона «Вычислительные машины и труднорешаемые задачи».

Здесь я не претендую на научность и умышленно игнорирую теорию, лежащую в основе анализа сложности алгоритмов. Я пишу только свои рассуждения о трудных задачах, которые вполне могут быть поняты читателем неоднозначно. А в конце прихожу к выводу о том, что трудных задач в принципе не бывает, так как если задача не может быть решена, она является научной проблемой, а если может, то это уже неинтересное упражнение, так как ответ известен и решать нечего.

Что понимается под «эффективностью»?

Что значит, что задачу «в принципе невозможно решить эффективно»? Грубо говоря, это означает, что если дать её порешать каждому человеку на Земле, то ни один не сможет предложить эффективного алгоритма. Что значит «эффективного»? Если речь идет о какой-то частной задаче, скажем, посчитать число гамильтоновых циклов на прямоугольной решётке с заданным размером (например, 24×24), то эффективным будет любой алгоритм, решающий задачу за «разумное время». Сколько мы готовы ждать ответа? Ну, я мог бы подождать месяц или два непрерывных расчетов, это не так много, если есть источник бесперебойного питания для ЭВМ. А вот год ждать уже неразумно, а гораздо разумнее отыскать (построить) более мощную машину или выжать из алгоритма максимум эффективности путем ручной оптимизации или вообще сказать, что эту задачу мы решать не будем (иногда амбиции на получение нового результата нужно уменьшить).

А если взять решётку размером 22×22, то задача становится тривиальной, так как ответ известен и равен «13404209505893761748339786653564937498745897123531041248680272448954956» После того, как частная задача решена, она перестаёт быть задачей, и становится упражнением.

Только здесь есть одна тонкость: предполагается, что для одного и того же значения входного параметра ответ является одним и тем же.

Помимо времени работы программы важной является используемая оперативная память. Всегда должен быть «разумный» предел, и трудной часто является необходимость укладываться в этот предел. Вообще, при работе с труднорешаемыми задачами те компьютеры, на которых меньше 64 Гб памяти за компьютеры не считаются, они называются «калькуляторами». Немного пафосно звучит, но домашняя ЭВМ вовсе не обязана уметь вычислять, когда её задача – запускать браузер, почту, а также Quake или StarCraft.

Итак, труднорешаемой становится любая задача, которая не может быть решена «за разумное время» и с использованием «разумной» памяти (даже при использовании суперкомпьютеров). Понятно, что данное определение весьма расплывчато и едва ли дает возможность понять, что такое «трудно», а что – нет.

Частные и общие задачи

Нужно различать частные задачи и общие. Общая задача ставится для набора некоторых входных параметров. Например, задача о числе расстановок k ферзей на прямоугольной доске размером m×n. Это общая труднорешаемая задача с тремя параметрами. Её частным случаем является другая общая задача, когда доска квадратная, то есть m=n, а значит параметра уже два. Она тоже трудная. Её частным случаем является задача о 6 ферзях. Она трудная? Теперь, когда решение найдено, это вообще не задача, но и до этого трудной не считалась, так как допускала решение алгоритмом с полиномиальной сложностью. Но ведь до того, как решение было найдено, эту задачу пытались решать и никто не мог. Значит, была все-таки трудной? Трудно сказать…

В любом случае, это общая задача, а решением для неё будет не один единственный ответ, а некий способ указать ответ для любой из её возможных подзадач (для любого значения параметра n). После того, как этот способ найден (например, формула или производящая функция), задача становится тривиальной. Но трудным, возможно, остается её обобщение.

Частная задача – это задача, в которой значения входных параметров уже заданы. Решить задачу в частном случае, это означает сказать ответ для этого случая (например, конкретное число). А решить задачу в общем случае означает указать относительно простой способ получить ответ для любого значения входного параметра (хорошо, если это будет простая формула).

Про полиномиальную сложность

А если сложность O(n100), что тогда? Теоретически получается, что задача не трудная, а на самом деле непонятно.

В чем проблема? Проблема в том, что давать оценку задаче по асимптотической сложности неправильно. И чёткой демаркационной линии между «трудно» и «не трудно» провести в общем случае не получится. В каждом случае будет получаться так: если задача не решается, то она трудная, а если решается – тривиальная.

Рассмотрим пример. Задача, имеющая сложность O(2n) будет трудной, так как переход от n к n+1 удваивает необходимую для решения мощность, а удваивать мощность мы можем не так долго, как может сначала показаться. Это чем-то напоминает легенду про изобретателя шахмат, который попросил за своё изобретение столько зерна, сколько получится, если на первую клетку шахматной доски положить 1 зерно, на вторую – 2, на третью 4 и т. д. Кажется, что в итоге получится мало, а в реальности чудовищно много. Но в случае, когда n фиксировано, эта задача решается за O(1) ( Ух ты, как быстро! ), а если ответом является конкретное число (или конкретный вывод), то после одной единственной успешной попытки решения задача перестаёт быть задачей.

Действительно, например, после того, как число гамильтоновых циклов на решётке размером 24×24 будет найдено, это уже будет не задача, так как ответ однозначен и известен. А сейчас это трудная задача, решить которую пока никто не может. Хотя теоретическая мощность современных машин, в принципе, позволяет, но те, у кого эта мощность есть, её просто не решают. В общем же случае задача является трудной.

Вывод

Какой вывод можно сделать? С одной стороны существует классификация задач по трудности, но она очень сложная и запутанная (возможно, о ней пойдет речь в других статьях). С другой стороны, классификация не даёт ответ на вопрос, какую задачу мы можем решить «за разумное время», а какую не можем. Примеры из статьи показывать, что одни задачи решаются и становятся тривиальными, другие не решаются и поэтому называются трудными. Вообще получается, что трудных задач нет! Есть либо нерешённые проблемы, либо уже решённые упражнения.

Ошибка

Данный вывод, конечно, является неправильным. Но где же ошибка? — Кто знает?

Кстати, товарищи математики, сколько будет 00?

Обсуждение статьи на форуме в этой теме.