Сведение по Куку задачи факторизации к языку из NP — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 7 промежуточных версий 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>. | Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа <math>n</math>. | ||
Строка 8: | Строка 8: | ||
Пусть функция '''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''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''': | Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''': | ||
<code> | <code> | ||
− | + | p(n) { | |
− | |||
− | |||
A = {}; | A = {}; | ||
− | '''while''' (n | + | '''while''' (n > 1) { |
− | + | '''if''' (!f(n, n)) { //''если число простое - добавляем его в список делителей и завершаем цикл'' | |
− | '''if''' (!f(n | + | A.add(n); |
− | + | n = 1; | |
− | A.add(n | ||
− | n | ||
'''break'''; | '''break'''; | ||
− | + | } | |
− | + | // ''Поддерживаем инвариант: у числа n' есть простой делитель x, такой что L <= x < R'' | |
− | + | R = n; | |
− | '''while''' ( | + | L = 2; |
− | + | '''while''' (R > L + 1) { //''находим наименьший простой делитель'' | |
− | c = ( | + | c = (L + R) / 2; |
− | '''if''' (f(n | + | '''if''' (f(n, c)) |
− | + | R = c; | |
'''else''' | '''else''' | ||
− | + | L = c; | |
− | + | } | |
− | A.add( | + | A.add(L); |
− | n | + | n = n / L; |
− | + | } | |
'''return''' A; | '''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''': | ||
Строка 62: | Строка 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.