dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

1. Задачи из классов NP и P, NP+ и P+

к Оглавлению

Как соотносятся между собой тяготы (затраты времени, сил и т.п.) между поиском ответа на вопрос и проверкой полученного ответа на вопрос? Из истории науки мы знаем, насколько трудными и долгими могли быть поиски ответов на возникшие вопросы, и насколько стремительно люди убеждались в правильности найденного ответа – после того, как он был найден.

Из недавней эпохи фундаментальных открытий в качестве примеров можно взять теоремы Гёделя в математике и уравнения для теории относительности и квантовой механики в физике. Одна теорема или формула позволяла не только решить отдельный принципиальный вопрос, но и обнаружить массу сопутствующих ответов, увязав множество фактов в целостную картину.

А может, раз проверка найденного ответа оказывается относительно простым делом, то и поиски ответа тоже можно сделать занятием относительно лёгким? Тогда осталось «только» найти такой способ поиска ответов на возникающие вопросы, который был бы примерно таким же лёгким, как проверка ответов. Разумеется, речь идёт о поиске правильного ответа на вопрос. Неправильный ответ найти – проще простого.

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

А именно, задача из класса NP – это:

1.1. Проверка при помощи некоторого алгоритма L(x, y) того, что «теорема» x истинна из-за «доказательства» y.

1.2. Время (количество «шагов») работы L(x, y) полиномиально от размеров |x|, |y|. Считаем, что время np_1(|x|, |y|), где p_1(|x|, |y|) – некоторый полином.

Замечание: Явное представление полинома p_1(|x|, |y|) – не является частью задачи. Просто «существует полином p_1(|x|, |y|)…»

1.3. Если в результате проверки выясняется, что «y доказывает x», то L(х, y) возвращает 1, в противном случае L(х, y) возвращает 0.

1.4. Размер |y| имеет полиномиальное ограничение относительно размера |x| - и при превышении этого ограничения L(x, y) вернет 0:

|y| ≤ p_2(|x|), где p_2(|x|) - некоторый полином, иначе верно: L(x, y) = 0:

Замечание: Если размер |y| превышает заданное через |x| ограничение, то можно считать, что алгоритм L(x, y) вернёт 0 так быстро, словно размер |y| не превышает максимально допустимого при данном x размера |y|.  Поясню:

Полиномиальное от размера |x| ограничение на размер |y| является частью определения задачи из класса NP. Но, в отличие от замечания пункта 1.2, не понятно (я не нашёл в учебниках прямого ответа), представлен данный ограничивающий алгоритм в явном виде как часть задачи или просто «существует…». Однако по контексту изложения в учебниках теории алгоритмов – полиномиальное ограничение на размер |y| задаётся явным образом в задачах из класса NP, так как всегда известен тот круг «доказательств», внутри которого только и может находиться подходящее «доказательство» для «теоремы» x.

Значит, при превышении данного явного ограничения на размер «доказательства» сразу возникает информация о непригодности «доказательства», даже не рассматривая его целиком. Это – вычисление, значит, оно может быть представлено посредством алгоритма в соответствии с тезисом Чёрча . Пусть для «слишком больших» доказательств y это тоже будет алгоритм L(x, y) – возвращающий 0 и делающий это за полиномиальное от размера |x| (но не от размера |y|, когда |y| слишком велик) количество шагов. Поэтому далее будем рассматривать только такие задачи из класса NP, которые соответствуют данному замечанию.

Как найти этот полином p_2(|x|) по алгоритму L(x, y) - не принципиально для данной работы, потому что в данной работе будет использован отдельный аргумент, задающий максимальный размер корректного доказательства – когда потребуется ограничение на размер доказательства.

Кстати, если бы мы не могли свести задачу к варианту из замечания (с известным явным ограничением на допустимый размер |y|), то у нас просто не было бы разрешимой разницы между работой алгоритма проверки L(x, y) для «нормальных» и «запредельно больших» доказательств y. И – вообще говоря – тогда может всегда оставаться возможность, что для какого-то гигантского по размеру доказательства y алгоритм L(x, y) вернёт 1 при заданной конкретной теореме x.

Неразрешимость этой проблемы (распознать, что исчезла возможность найти для данного фиксированного x корректное доказательство с ростом размера доказательства) вытекала бы из неразрешимости проблемы остановки (можно легко свести). И тогда неразрешимость вопроса о сведении класса NP к P доказывалась бы элементарно (с помощью нюанса из пункта 5 ниже). Это не то же самое, что неравенство NPP, но близко к тому. Поэтому явное ограничение полиномом от |x| на допустимый размер |y| будем считать частью задачи из класса NP.

1.5. Композиция p_0(|x|) = p_1(|x|, p_2(|x|)) задаёт ограничение на время работы L(x, y) относительно размеров |x|. Это свойство соответствует замечанию, сделанному в предыдущем пункте. В то же время, данное ограничение в явном виде (как готовый алгоритм) не является частью задачи из класса NP, так как один из алгоритмов в композиции – который был определён в пункте 1.2 – не задан явно для задачи.

1.6. Далее будем считать, что задача из класса NP полностью задаётся алгоритмом проверки L(x, y), который соответствует замечанию из пункта 1.4 и ограничивающий алгоритм пункта 1.4 можно «вычислить» из программного текста алгоритма L(x, y).

Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

Recent Posts from This Journal

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments