Сведение по Куку задачи факторизации к языку из NP — различия между версиями
| Строка 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''': | ||
| Строка 48: | Строка 48: | ||
==Принадлежность языка FACTOR классу NP== | ==Принадлежность языка FACTOR классу NP== | ||
| − | < | + | <tex>\mbox{FACTOR} \in \mbox{NP}</tex>. |
Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''': | Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''': | ||
Версия 16:36, 19 марта 2010
Формулировка задачи
Задача факторизации FACTORIZE — это задача разложения натурального числа на простые множители.
Сведение задачи факторизации к языку FACTOR
Рассмотрим язык .
Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа .
Пусть функция f разрешает язык FACTOR:
Тогда, воспользовавшись двоичным поиском, можно написать функцию p, работающую за полином от длины входа и возвращающую список A простых делителей n:
p(n)
{
n' = n;
A = {};
while (n' > 1)
{
if (!f(n', n')) //если число простое - добавляем его в список делителей и завершаем цикл
{
A.add(n');
n' = 1;
break;
}
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.
