Сведение по Куку задачи факторизации к языку из NP — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 12 промежуточных версий 5 участников) | |||
Строка 2: | Строка 2: | ||
Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители. | Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители. | ||
==Сведение задачи факторизации к языку FACTOR== | ==Сведение задачи факторизации к языку FACTOR== | ||
− | Рассмотрим язык < | + | Рассмотрим язык <tex>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</tex>. |
− | Используя его в качестве оракула, можно за полиномиальное время найти | + | Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа <math>n</math>. |
Пусть функция '''f''' разрешает язык '''FACTOR''': | Пусть функция '''f''' разрешает язык '''FACTOR''': | ||
− | < | + | <tex> |
\mbox{f(n, x)}= | \mbox{f(n, x)}= | ||
\begin{cases} | \begin{cases} | ||
Строка 14: | Строка 14: | ||
\mbox{false}, ~(n, x) \not\in \mbox{FACTOR} | \mbox{false}, ~(n, x) \not\in \mbox{FACTOR} | ||
\end{cases} | \end{cases} | ||
− | </ | + | </tex> |
− | Тогда можно написать функцию '''p''', работающую | + | Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''': |
<code> | <code> | ||
− | + | p(n) { | |
− | + | A = {}; | |
− | + | '''while''' (n > 1) { | |
− | + | '''if''' (!f(n, n)) { //''если число простое - добавляем его в список делителей и завершаем цикл'' | |
+ | A.add(n); | ||
+ | n = 1; | ||
+ | '''break'''; | ||
+ | } | ||
+ | // ''Поддерживаем инвариант: у числа n' есть простой делитель x, такой что L <= x < R'' | ||
+ | R = n; | ||
+ | L = 2; | ||
+ | '''while''' (R > L + 1) { //''находим наименьший простой делитель'' | ||
+ | c = (L + R) / 2; | ||
+ | '''if''' (f(n, c)) | ||
+ | R = c; | ||
+ | '''else''' | ||
+ | L = c; | ||
+ | } | ||
+ | A.add(L); | ||
+ | n = n / L; | ||
+ | } | ||
+ | '''return''' A; | ||
+ | } | ||
</code> | </code> | ||
==Принадлежность языка FACTOR классу NP== | ==Принадлежность языка FACTOR классу NP== | ||
− | < | + | <tex>\mbox{FACTOR} \in \mbox{NP}</tex>. |
Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''': | Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''': | ||
Строка 39: | Строка 58: | ||
</code> | </code> | ||
− | Таким образом, задача '''FACTORIZE''' сводится по Куку за полиномиальное время к языку '''FACTOR''', принадлежащему классу '''NP'''. | + | Таким образом, задача '''FACTORIZE''' [[Сведение по Куку|сводится по Куку]] за полиномиальное время к языку '''FACTOR''', принадлежащему классу [[Класс NP|'''NP''']]. |
Текущая версия на 19:12, 4 сентября 2022
Формулировка задачи
Задача факторизации FACTORIZE — это задача разложения натурального числа на простые множители.
Сведение задачи факторизации к языку FACTOR
Рассмотрим язык
.Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа
.Пусть функция f разрешает язык FACTOR:
Тогда, воспользовавшись двоичным поиском, можно написать функцию p, работающую за полином от длины входа и возвращающую список A простых делителей n:
p(n) {
A = {}; while (n > 1) { if (!f(n, n)) { //если число простое - добавляем его в список делителей и завершаем цикл A.add(n); n = 1; break; } // Поддерживаем инвариант: у числа n' есть простой делитель x, такой что L <= x < R R = n; L = 2; while (R > L + 1) { //находим наименьший простой делитель c = (L + R) / 2; if (f(n, c)) R = c; else L = c; } A.add(L); n = n / L; } return A;
}
Принадлежность языка FACTOR классу NP
.
Сертификатом y является нетривиальный делитель числа n, а верификатором - функция, которая проверяет, является ли y делителем n и меньше ли он числа x:
R(<n, x>, y) { if ((y >= x) || (y <= 1)) return false; if (n % y != 0) return false; return true; }
Таким образом, задача FACTORIZE сводится по Куку за полиномиальное время к языку FACTOR, принадлежащему классу NP.