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