Сведение по Куку задачи факторизации к языку из NP
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Формулировка задачи
Задача факторизации 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.
