Полиномиальное сведение

Мы намереваемся исследовать пространство вычислительно сложных задач, чтобы в конечном итоге прибыть к математической характеристике большого класса.

Основным приемом в этом исследовании будет сравнение относительной сложности разных задач; нам хотелось бы найти формальное выражение для таких утверждений, как «задача X обладает как минимум не меньшей сложностью, чем задача Y».

Для формализации будет применен метод сведения: чтобы показать, что некоторая задача X по меньшей мере не менее сложна, чем другая задача Y, мы докажем, что «черный ящик», способный решить задачу X, также сможет решить задачу Y. (Другими словами, решение X будет достаточно мощным для того, чтобы также решить Y.)

Чтобы точно выразить этот критерий, мы предположим, что задача X в нашей вычислительной модели может быть напрямую решена с полиномиальным временем.

Допустим, имеется некий «черный ящик», способный решать экземпляры задачи X; если передать ему входные данные для экземпляра X, то «черный ящик» за один шаг вернет правильный ответ. А теперь зададимся следующим вопросом:

(*) Возможно ли решить произвольный экземпляр задачи Y с полиномиальным количеством стандартных вычислительных шагов, дополняемых полиномиальным количеством обращений к «черному ящику», решающему задачу X?

Если ответ на этот вопрос положителен, то мы используем запись Y ≤P X; это читается как «задача Y является полиномиальносводимой к X», или «сложность X по крайней мере не меньше сложности Y (в отношении полиномиального времени)».

Обратите внимание: в этом определении учитываются затраты времени на передачу входных данных «черному ящику», решающему X, и на получение ответа от «черного ящика».

У нашего определения ≤P имеется одно важное следствие: предположим, Y ≤P X и существует алгоритм с полиномиальным временем для решения X. Тогда польза от специализированного «черного ящика» для X не столь уж велика; его можно заменить алгоритмом с полиномиальным временем для X.

Подумайте, что произойдет с нашим алгоритмом для задачи Y, использующим полиномиальное количество шагов плюс полиномиальное количество вызовов «черного ящика».

Он превращается в алгоритм, использующий полиномиальное количество шагов плюс полиномиальное количество вызовов процедуры, выполняемой за полиномиальное время; другими словами, он превращается в алгоритм с полиномиальным временем. Таким образом, мы доказали следующий факт.

(8.1) Допустим, Y ≤P X. Если задача X решается за полиномиальное время, то и задача Y может быть решена за полиномиальное время.

Собственно, этот факт, хотя и неявно, уже использовался ранее в книге. Вспомните, как мы решали задачу о двудольном паросочетании с использованием полиномиального объема предварительной обработки и времени решения одного экземпляра задачи о максимальном потоке

. Так как задача о максимальном потоке может быть решена за полиномиальное время, мы заключили, что это возможно и для задачи о двудольном паросочетании.

Кроме того, задача сегментации изображения решалась с использованием полиномиального объема предварительной обработки и времени решения одного экземпляра задачи о минимальном разрезе с теми же последствиями.

Оба примера могут рассматриваться как прямые применения (8.1). В самом деле, (8.1) предоставляет отличный способ разработки алгоритмов с полиномиальным временем для новых задач: сведение к задаче, которую мы уже умеем решать за полиномиальное время.

Тем не менее в этой главе (8.1) будет использоваться для установления вычислительной неразрешимости некоторых задач.

Мы будем заниматься довольно нетривиальным делом: речь пойдет об оценке разрешимости задач даже в том случае, когда мы не знаем, как решать их за полиномиальное время. Для этой цели будет использовано утверждение, противоположное (8.1); оно достаточно важно, чтобы представить его как отдельный факт.

(8.2) Допустим, Y ≤P X. Если задача Y не решается за полиномиальное время, то и задача X не может быть решена за полиномиальное время.

Утверждение (8.2) очевидно эквивалентно (8.1), но оно подчеркивает наш общий план: если имеется заведомо сложная задача Y и мы показываем, что Y ≤P X, то сложность «распространяется» на X; задача X должна быть сложной, или в противном случае она могла бы использоваться для решения Y.

Так как на практике мы не знаем, возможно ли решить изучаемые задачи за полиномиальное время или нет, обозначение ≤P будет использоваться для установления относительной сложности между задачами.