ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.02.2021
Просмотров: 135
Скачиваний: 1
Задачи
,
труднорешаемость
которых
доказуема
После
того
как
мы
обсудили
формальное
содержание
понятия
"
труднорешаемая
задача
",
уместно
дать
краткий
обзор
современного
состояния
наших
знаний
о
существовании
труднорешаемых
задач
.
Сначала
охарактеризуем
различия
между
двумя
аспектами
труднорешаемости
,
которые
отражены
в
нашем
определении
Первый
аспект
,
который
обычно
имеется
в
виду
,
состоит
в
том
,
что
для
отыскания
решения
требуется
экспоненциальное
время
.
Второй
заключается
в
том
,
что
искомое
решение
настолько
велико
,
что
не
может
быть
представлено
в
виде
выражения
,
длина
которого
была
бы
ограничена
полиномом
от
длины
входа
.
Вторая
ситуация
возникает
,
например
,
если
в
задаче
о
коммивояжере
в
качестве
дополнительного
параметра
фигурирует
число
В
и
требуется
найти
все
маршруты
длины
,
не
превосходящей
В
.
Легко
построить
индивидуальную
задачу
о
комми
-
вояжере
,
в
которой
имеется
экспоненциальное
число
маршрутов
длины
,
не
превосходящей
В
,
поэтому
не
существует
алгоритма
с
полиномиальной
временной
сложностью
,
который
все
их
перечисляет
.
Труднорешаемостью
этого
вида
нельзя
ни
в
коем
случае
пренебрегать
,
и
очень
важно
ее
своевременно
обнаружить
.
В
большинстве
случаев
,
однако
,
ее
наличие
ясно
из
постановки
задачи
.
Этот
аспект
труднорешаемости
обычно
можно
рассматривать
как
указание
на
то
,
что
постановка
задачи
не
реалистична
,
поскольку
мы
запрашиваем
больше
информации
,
чем
когда
-
либо
сможем
использовать
.
В
связи
с
этим
с
настоящего
момента
и
до
конца
книги
мы
будем
рассматривать
только
первый
тип
труднорешаемости
.
А
именно
будут
изучаться
только
такие
задачи
,
длина
решения
которых
ограничена
полиномиальной
функцией
от
длины
входной
информации
.
Первые
результаты
о
труднорешаемости
задач
—
классические
результаты
о
неразрешимости
—
были
получены
А
.
Тьюрингом
.
Около
40
лет
назад
Тьюринг
доказал
,
что
некоторые
задачи
даже
"
неразрешимы
"
в
том
смысле
,
что
вообще
не
существует
алгоритма
их
решения
.
Он
доказал
,
например
,
что
невозможно
указать
алгоритм
,
который
по
произвольной
программе
определял
бы
,
остановится
ли
эта
программа
на
произвольно
заданном
входе
или
нет
.
Известно
большое
число
других
неразрешимых
задач
.
К
ним
относятся
,
в
частности
,
задача
выяснения
тривиальности
конечно
-
порожденных
групп
,
десятая
проблема
Гильберта
(
разрешимость
в
целых
числах
полиномиальных
уравнений
),
а
также
несколько
задач
о
покрытии
плоскости
равными
областями
.
Поскольку
эти
задачи
не
могут
быть
решены
никаким
алгоритмом
,
то
тем
более
они
не
разрешимы
и
полиномиальным
алгоритмом
и
,
значит
,
действительно
труднорешаемы
в
самом
сильном
смысле
.
Первые
примеры
труднорешаемых
"
разрешимых
"
задач
были
получены
в
начале
60-
х
годов
,
как
один
из
результатов
работы
Хартманиса
и
Стирнза
по
"
иерархиям
"
сложности
.
Однако
эти
примеры
включали
только
"
искусственные
"
задачи
,
специально
построенные
,
чтобы
обладать
соответствующими
свойствами
.
Только
в
начале
70-
х
годов
Мейеру
и
Сток
-
Мейеру
,
Фишеру
и
Рабину
и
нескольким
другим
авторам
удалось
показать
,
что
некоторые
"
естественные
"
раз
-
решимые
задачи
труднорешаемы
.
В
число
этих
задач
вошло
большое
число
изучавшихся
ранее
задач
из
теории
автоматов
,
формальной
теории
языков
и
математической
логики
.
На
самом
деле
было
показано
,
что
эти
задачи
не
могут
быть
решены
за
полиномиальное
время
даже
с
,
помощью
"
недетерминированного
"
вычислительного
устройства
,
обладающего
способностью
параллельно
выполнять
неограниченное
количество
независимых
вычислений
.
Все
известные
в
настоящее
время
задачи
,
труднорешаемость
которых
доказана
,
попадают
в
один
из
перечисленных
классов
:
они
либо
вовсе
неразрешимы
,
либо
труднорешаемы
недетерминированной
машиной
.
Однако
большинство
представляющихся
труднорешаемыми
практических
задач
в
действительности
разрешимы
и
,
более
того
,
могут
быть
решены
за
полиномиальное
аремя
с
помощью
недетерминированного
вычислительного
устройства
.
Таким
образом
,
известные
методы
недостаточно
сильны
,
чтобы
установить
труднорешаемость
этих
задач
.
