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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>.  
 
Рассмотрим язык <math>\mbox{FACTOR} = \{(n, x) \mid \exists k<x, ~ k \neq 1,~ n~\vdots~k\}</math>.  
  
Используя его в качестве оракула, можно за полиномиальное время найти нетривиальные простые делители числа <math>n</math>.  
+
Используя его в качестве оракула, можно за полиномиальное время найти простые делители числа <math>n</math>.  
  
 
Пусть функция '''f''' разрешает язык '''FACTOR''':
 
Пусть функция '''f''' разрешает язык '''FACTOR''':
Строка 16: Строка 16:
 
</math>
 
</math>
  
Тогда можно написать функцию '''p''', работающую не медленнее, чем за полином, и возвращающую список ''A'' нетривиальных простых делителей '''n''':
+
Тогда можно написать функцию '''p''', работающую за полином от длины входа и возвращающую список ''A'' простых делителей '''n''':
 
<code>
 
<code>
 
  p(n)
 
  p(n)
Строка 22: Строка 22:
 
   n' = n;
 
   n' = n;
 
   A = {};
 
   A = {};
   '''for''' (b = 2; b <= n / 2; b++) //''b - текущий простой делитель''
+
   '''while''' (n' >  1)
  {
+
  {
    '''while''' (f(n', b + 1))
+
    '''if''' (!f(n', n'))
       {
+
    {
      n' /= b;
+
      A.add(n');
      A.add(b);
+
      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;
 
   '''return''' A;
 
  }
 
  }

Версия 16:26, 19 марта 2010

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

Задача факторизации 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)
{
 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

[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.