Равенство классов P и NP в технологии предвидения

Изображение пользователя С.А.Кравченко

Равенство классов P и NP в технологии предвидения будущего.

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

В конечном счете проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти?
Проще говоря, действительно ли задачу легче проверить, чем решить?

Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее (не доказано).

Содержание проблемы

Отношения между классами P и NP рассматриваются в теории вычислительной сложности, изучающей ресурсы, необходимые для решения некоторой задачи. Наиболее общие ресурсы — это время (сколько нужно сделать шагов) и память (сколько памяти потребуется для решения задачи).
Из определения классов P и NP сразу вытекает следствие: Р является подмножеством NP. Однако до сих пор ничего не известно о строгости этого включения, т. е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные задачи из класса NP можно решить за экспоненциальное время, что почти всегда неприемлемо.
Впервые вопрос о равенстве классов был поставлен независимо Стивеном Куком в 1971 году и Леонидом Левиным в 1973. В настоящее время большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 году среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.
В настоящий момент проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.

Теперь о технологии предвидении и предвосхищении будущего

Множество тем предвидения всегда будет больше множества опыта экспертов, на основании которых строятся экспертные системы и проверка правильности решения задачи (предвидения и предвосхищения в том числе).
Технология, в том числе и технология предвидения, которую мы создаем (ИСС-технология), включает в себя и алгоритмы, т. е точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.
Предполагается, что технология содержит и множество NP, то есть множество алгоритмов проверки задач (множество задач распознавания, решение которых можно «быстро» проверить).

Проблема определения и осознания процесса предвидения и, как следствие, предвосхищения.
Вопрос. К какому виду деятельности относится предвидение: рациональному или иррациональному, логическому или интуитивному, технологическому или творческому?
Ответ. Предвидение (и предвосхищение) охватывает все виды деятельности: иррациональный и рациональный, интуитивный и логический, творческий и технологический.

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

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

Понятия:

Алгори́тм — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.
Классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных).
Классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания, решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за время, не превосходящее полинома от размера данных) проверить на машине Тьюринга.
Эквивалентно класс NP можно определить как содержащий задачи, которые можно «быстро» решить на недетерминированной машине.
Технология (от греч. τέχνη — искусство, мастерство, умение; др.-греч. λόγος — мысль, причина; методика, способ производства) — комплекс организационных мер, операций и приемов, направленных на изготовление, обслуживание, ремонт и/или эксплуатацию изделия с номинальным качеством и оптимальными затратами, и обусловленных текущим уровнем развития науки, техники и общества в целом.

Источники:
Сайт Википедия - http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%....

Статья не завершена.
14 октября 2010.
С.А.Кравченко.

About С.А.Кравченко