Библиотека

ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ стр. 28

Размер шрифта
-
+
Тема

путь, чтобы не гонять кучу машин неведомыми тропами. Конечный эффект тот же.

Таким образом, множество труднорешаемых задач (NP задач) относится к задачам, решаемым недетерминированной машиной за полиномиальное время. А проблему сложности вычислений математики выразили в виде формулы, которую все-таки приведу из-за ее краткости и «нетрудности» печати:

P = NP?

Интересно, говорят этой формулой математики, совпадают ли множество задач, решаемых за полиномиальное время и множество NP задач? Может просто толку пока не хватает найти простые решения…

Как бы там ни было, а задачи, для которых простые (полиномиальные) решения пока не найдены, существуют. И чем дальше, тем больше математики упорствуют в этой (недоказанной) уверенности. Более того, они коллекционируют типовые труднорешаемые задачи, которых уже набралось не менее тысячи. Более того, утверждают, что одни труднорешаемые задачи сводятся к другим труднорешаемым задачам. Поэтому даже используется для таких задач термин "NP–полные" задачи. И делается радикальное заявление: если хоть для одной NP–полной задачи будет найдено простое (полиномиальное) решение, тогда простое решение будет найдено и для всех остальных NP–полных задач. Тогда будет доказано P=NP и проблема сложности вычислений в этом ее виде будет закрыта!

ПОСЛЕСЛОВИЕ

Самой первой NP–полной задачей стала задача нахождения клик графа, то есть полных подграфов данного графа с конкретным числом вершин…

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

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

Переход на страницу
Ваш комментарий
Рейтинг

Имя, оценка и комментарий будут опубликованы после модерации. Не указывайте личные данные. Политика конфиденциальности.

Советуем почитать

Рекомендуемые жанры