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

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