Шрифт:
Интервал:
Закладка:
Но проверить решение такой задачи можно за полиномиальное время. Вся сложность в том, чтобы знать «траекторию решения». А вот снять проблему выбора правильной траектории позволяет недетерминированная машина Тьюринга, которую можно представить как сколь угодно большое число (обычных детерминированных) машин, каждая из которых делает попытку добраться до решения задачи по одной из возможных траекторий. У кого из читателей фантазия при этом отказывает, могут просто представить себе бога (говорят – «оракула»), который подсказывает правильный путь, чтобы не гонять кучу машин неведомыми тропами. Конечный эффект тот же.
Таким образом, множество труднорешаемых задач (NP задач) относится к задачам, решаемым недетерминированной машиной за полиномиальное время. А проблему сложности вычислений математики выразили в виде формулы, которую все-таки приведу из-за ее краткости и «нетрудности» печати:
P = NP?
Интересно, говорят этой формулой математики, совпадают ли множество задач, решаемых за полиномиальное время и множество NP задач? Может просто толку пока не хватает найти простые решения…
Как бы там ни было, а задачи, для которых простые (полиномиальные) решения пока не найдены, существуют. И чем дальше, тем больше математики упорствуют в этой (недоказанной) уверенности. Более того, они коллекционируют типовые труднорешаемые задачи, которых уже набралось не менее тысячи. Более того, утверждают, что одни труднорешаемые задачи сводятся к другим труднорешаемым задачам. Поэтому даже используется для таких задач термин "NP–полные" задачи. И делается радикальное заявление: если хоть для одной NP–полной задачи будет найдено простое (полиномиальное) решение, тогда простое решение будет найдено и для всех остальных NP–полных задач. Тогда будет доказано P=NP и проблема сложности вычислений в этом ее виде будет закрыта!
ПОСЛЕСЛОВИЕ
Самой первой NP–полной задачей стала задача нахождения клик графа, то есть полных подграфов данного графа с конкретным числом вершин…
Но в середине семидесятых годов были опубликованы так называемые "алгоритмы Магу", которые исключили из числа переборных не только задачи типа «восьми ферзей» (прежде стандартный полигон для эвристических алгоритмов «искусственного интеллекта»), но там и клики графа также находятся с помощью несложных манипуляций на уровне алгебры высказываний (преобразования выражения к ДНФ), что ни как не выше полиномиальной сложности.
Мало радости признаваться в собственной бестолковости и некомпетентности, но проблема трудно решаемых задач для меня существует в несколько извращенном виде.
- Рассказы о математике с примерами на языках Python и C (СИ) - Елисеев Дмитрий Сергеевич - Математика
- Том 27. Поэзия чисел. Прекрасное и математика - Антонио Дуран - Математика
- Сборник задач по математике с решениями для поступающих в вузы - Альберт Рывкин - Математика
- Том 18. Открытие без границ. Бесконечность в математике - Энрике Грасиан - Математика
- Математика. Поиск истины. - Клайн Морис - Математика
- Математика. Поиск истины. - Морис Клайн - Математика
- Математика. Утрата определенности. - Морис Клайн - Математика
- Для юных математиков. Веселые задачи - Яков Перельман - Математика
- Вероятность как форма научного мышления - Виктор Лёвин - Математика
- Удовольствие от Х.Увлекательная экскурсия в мир математики от одного из лучших преподавателей в мир - Стивен Строгац - Математика