15
правок
Изменения
Новая страница: «==Формулировка задачи== Задача факторизации '''FACTORIZE''' — это задача разложения натурального…»
==Формулировка задачи==
Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители.
==Сведение задачи факторизации к языку FACTOR==
Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>.
Используя его в качестве оракула, можно за полиномиальное время найти нетривиальные простые делители числа <math>n</math>.
Пусть функция '''f''' разрешает язык '''FACTOR''':
<math>
\mbox{f(n, x)}=
\begin{cases}
\mbox{true}, ~(n, x) \in \mbox {FACTOR} \\
\mbox{false}, ~(n, x) \not\in \mbox{FACTOR}
\end{cases}
</math>
Тогда можно написать функцию '''p''', работающую не медленнее, чем за полином, и возвращающую список ''A'' нетривиальных простых делителей '''n''':
<code>
p(n)
{
b = 2;
t = 3;
A = {};
'''while''' (t <= n/2 + 1)
{
'''while''' (f(n, t))
{
n /= b;
A.add(b);
}
'''while''' ((t < n/2 + 1)&&(!f(n, t)))
{
t++;
}
b = t - 1;
}
'''return''' A;
}
</code>
==Принадлежность языка FACTOR классу NP==
<math>\mbox{FACTOR} \in \mbox{NP}</math>.
Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''':
<code>
R(<n, x>, y)
{
'''if''' ((y >= x) || (y <= 1))
'''return''' false;
'''if''' (n % y != 0)
'''return''' false;
'''return''' true;
}
</code>
Таким образом, задача '''FACTORIZE''' сводится по Куку за полиномиальное время к языку '''FACTOR''', принадлежащему классу '''NP'''.
Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители.
==Сведение задачи факторизации к языку FACTOR==
Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>.
Используя его в качестве оракула, можно за полиномиальное время найти нетривиальные простые делители числа <math>n</math>.
Пусть функция '''f''' разрешает язык '''FACTOR''':
<math>
\mbox{f(n, x)}=
\begin{cases}
\mbox{true}, ~(n, x) \in \mbox {FACTOR} \\
\mbox{false}, ~(n, x) \not\in \mbox{FACTOR}
\end{cases}
</math>
Тогда можно написать функцию '''p''', работающую не медленнее, чем за полином, и возвращающую список ''A'' нетривиальных простых делителей '''n''':
<code>
p(n)
{
b = 2;
t = 3;
A = {};
'''while''' (t <= n/2 + 1)
{
'''while''' (f(n, t))
{
n /= b;
A.add(b);
}
'''while''' ((t < n/2 + 1)&&(!f(n, t)))
{
t++;
}
b = t - 1;
}
'''return''' A;
}
</code>
==Принадлежность языка FACTOR классу NP==
<math>\mbox{FACTOR} \in \mbox{NP}</math>.
Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''':
<code>
R(<n, x>, y)
{
'''if''' ((y >= x) || (y <= 1))
'''return''' false;
'''if''' (n % y != 0)
'''return''' false;
'''return''' true;
}
</code>
Таким образом, задача '''FACTORIZE''' сводится по Куку за полиномиальное время к языку '''FACTOR''', принадлежащему классу '''NP'''.
