Почему факторинг в NP, но не в P?

Факторинг: Gven целое число N, найти целые числа 1 < a, b < N, что N = ab, если они существуют, в противном случае N является простым.

Я знаю, что тестирование примитивности в P, но почему не факторинг?

Вот мой алгоритм:

For each a = 1 ... sqrt(N)
    if(N % a == 0)
        b = N/a
        add (a,b) to the result
    Endif
EndFor

Это выполняется в O (sqrt (N)).

Ответ 1

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

Например, предположим, что мы факторизуем число n вашим алгоритмом. Если n является простым, вам нужно проверить как минимум sqrt(N) факторы. (Или, альтернативно, для этого можно вычислить таблицу простых чисел, но она все еще не линейна).

В любом случае, вы тестируете sqrt(N) раз. Но размер проблемы определяется как S=log2(N). Итак, мы имеем N=2^S. Поэтому a sqrt(2^S)=2^(S/2), который является экспоненциальным.