Почему алгоритм наивного теста на простоту не является полиномиальным

Question

Я хотел бы понять, почему следующий алгоритм наивного теста на простоту не является полиномиальным.

IsPrime (n: an integer)
Begin
   For i=2 to n-1 do
     If (n % i == 0) then
        return (no)
     EndIf
   EndFor

   return (yes)
End

Этот алгоритм называется экспоненциальным по размеру входа n . Почему это правда? И почему следующий алгоритм проверки сортировки называется полиномиальным, а не экспоненциальным?

IsSorted (T[n]: an array of n integer)
Begin
  For i = 1 to n-1 do
     If (T[i] > T[i+1]) then
        return (no)
     EndIf
  EndFor

  return (yes)
End

Answer 1

Во-вторых, ответ, данный Генри, алгоритм в исходном вопросе фактически имеет полиномиально ограниченное время выполнения - если унарное кодирование используется для ввода!

Точнее, границы времени выполнения зависят не только от самого алгоритма, но и от используемой схемы кодирования. Рассмотрим следующий алгоритм в C-подобном синтаксисе.

INPUT: integer n
for (int i = 0; i < n; i++)
{
    wait one second
}

По-видимому, алгоритму требуется n секунд для завершения; время линейно в n. Если вход кодируется с использованием унарного кодирования , количество времени линейно масштабируется по длине кодирования n. Однако, если n закодировано с использованием двоичного кодирования , количество времени масштабируется экспоненциально при длине кодирования n (поскольку длина кодирования n логарифмически масштабируется при значении n) .

Короче говоря, утверждение о том, что алгоритм, о котором идет речь, является не полиномиальным без какой-либо дополнительной информации, неверно. Однако очевидно, что существует соглашение, что двоичное кодирование (или любая другая позиционная запись) используется, если не указано иное.

При этом я утверждаю, что зависимость времени выполнения, привязанного к схеме кодирования, обычно преподается немного неточно. Термин псевдополином также плавает вокруг.

Answer 2

Наивный тест в первую очередь является полиномиальным в значении входа (то есть фактического числа, которое получает функция), но экспоненциальным в размере (биты, байты, и т. д.) ввода.

Если у вас есть число n, состоящее из b битов, у нас есть b = O(log n), а также n = O(2<sup>b</sup>).

Время работы, таким образом, O(n) или O(2<sup>b</sup>).

Answer 3

Размер ввода обычно измеряется в битах. Для представления числа n входной размер будет log2 (n). Примитивный критерий примитивности является линейным по n, но экспоненциальным по log2 (n).