Сведение по Куку задачи факторизации к языку из NP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 5 участников)
Строка 2: Строка 2:
 
Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители.  
 
Задача факторизации '''FACTORIZE''' — это задача разложения натурального числа на простые множители.  
 
==Сведение задачи факторизации к языку FACTOR==
 
==Сведение задачи факторизации к языку FACTOR==
−
Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>.  
+
Рассмотрим язык <tex>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</tex>.  
  
−
Используя его в качестве оракула, можно за полиномиальное время найти нетривиальные простые делители числа <math>n</math>.  
+
Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа <math>n</math>.  
  
 
Пусть функция '''f''' разрешает язык '''FACTOR''':
 
Пусть функция '''f''' разрешает язык '''FACTOR''':
  
−
<math>
+
<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}
−
</math>
+
</tex>
  
−
Тогда можно написать функцию '''p''', работающую не медленнее, чем за полином, и возвращающую список ''A'' нетривиальных простых делителей '''n''':
+
Тогда, воспользовавшись двоичным поиском, можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''':
 
<code>
 
<code>
−
p(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;
 +
}
 
</code>
 
</code>
  
 
==Принадлежность языка FACTOR классу NP==
 
==Принадлежность языка FACTOR классу NP==
−
<math>\mbox{FACTOR} \in \mbox{NP}</math>.  
+
<tex>\mbox{FACTOR} \in \mbox{NP}</tex>.  
  
 
Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''':
 
Сертификатом '''y''' является нетривиальный делитель числа '''n''', а верификатором - функция, которая проверяет, является ли '''y''' делителем '''n''' и меньше ли он числа '''x''':
Строка 39: Строка 58:
 
</code>
 
</code>
  
−
Таким образом, задача '''FACTORIZE''' сводится по Куку за полиномиальное время к языку '''FACTOR''', принадлежащему классу '''NP'''.
+
Таким образом, задача '''FACTORIZE''' [[Сведение по Куку|сводится по Куку]] за полиномиальное время к языку '''FACTOR''', принадлежащему классу [[Класс NP|'''NP''']].

Текущая версия на 19:12, 4 сентября 2022

Формулировка задачи

Задача факторизации FACTORIZE — это задача разложения натурального числа на простые множители.

Сведение задачи факторизации к языку FACTOR

Рассмотрим язык [math]\mbox{FACTOR} = \{(n, x) \mid \exists k\lt 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: 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

[math]\mbox{FACTOR} \in \mbox{NP}[/math].

Сертификатом 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.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Сведение_по_Куку_задачи_факторизации_к_языку_из_NP&oldid=84587»