Главная > Интеллектуальные системы > Системы искусственного интеллекта
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.8. Класс NP-полных задач

С помощью теоремы Кука для всех задач одновременно устанавливается отношение сводимости логическая разрешимость”. Но отношение сводимости является транзитивным. Поэтому если нам удастся доказать, что логическая разрешимость сводима к некоторой задаче которая сама сводится к то мы получим класс эквивалентных задач.

Это фактически заставляет уточнить границы класса III путем разбиения его на две части в зависимости от того, смогли ли мы доказать принадлежность/непринадлежность задачи классу

Определение. Задача называется -полной в том и только в том случае, если она является NP-полной и попадает в класс

Для лучшего понимания проблемы рассмотрим рис. 4.9.

Получение результата сегодня кажется невероятным. Для большинства действительно сложных классических задач была доказана принадлежность к классу -сложных. Но, что еще более удивительно, почти все они попадают в класс т. е. являются NP-полными, и, следовательно, в этом смысле

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

Напомним два других свойства -полных задач: мы не знаем, являются ли они неполиномиальными, и не знаем для их решения детерминированного полиномиально ограниченного алгоритма.

Рис. 4.9. Пример сортировки первого типа.

Приведем для примера несколько доказательств эквивалентности.

Идея состоит в том, чтобы перевести задачу из одного класса задач в другой. Трудность заключается в том, что мы не умеем как следует решать основную задачу — задачу логической разрешимости. Но принципы моделирования и преобразования условий могут успешно использоваться в конкретных случаях.

В действительности при изучении этих проблем никогда не следует упускать из виду, что даже если теоретическая принадлежность некоторой общей задачи к классу -полных доказана, любая конкретная задача с уточненными данными может быть все-таки решена. Не является невозможным решение этой уточненной задачи за полиномиальное время. Единственное, что утверждает теория: для общего случая не существует единого полиномиального алгоритма.

<< Предыдущий параграф Следующий параграф >>
Оглавление