Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В теории вычислительной сложности числовой алгоритм работает за псевдополиномиальное время, если его время работы является полиномом от числового значения входных данных (наибольшего целого числа, присутствующего во входных данных), но не обязательно от длины входных данных (количества бит, необходимых для его представления), что характерно для алгоритмов, работающих за полиномиальное время. Как правило, числовое значение входных данных растет экспоненциально с увеличением длины входных данных, поэтому алгоритм, работающий за псевдополиномиальное время, не обязательно работает за полиномиальное время относительно длины входных данных. NP-полная задача, для которой известны алгоритмы, работающие за псевдополиномиальное время, называется слабо NP-полной. NP-полная задача называется строго NP-полной, если доказано, что она не может быть решена алгоритмом, работающим за псевдополиномиальное время, если P = NP. Аналогично определяются сильные и слабые виды NP-трудности.
In computational complexity theory, a numeric algorithm runs in pseudo polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. In general, the numeric value of the input is exponential in the input length, which is why a pseudo polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An NP complete problem with known pseudo polynomial time algorithms is called weakly NP complete. An NP complete problem is called strongly NP complete if it is proven that it cannot be solved by a pseudo polynomial time algorithm unless P = NP. The strong/weak kinds of NP hardness are defined analogously.
Испытание первичности
Рассмотрим проблему проверки того, является ли число n простым, наивно проверяя, не делится ли n нацело на каждое число в диапазоне от 2 до n-1. Этот подход может потребовать до n-1 делений, что является сублинейным по значению n, но экспоненциальным по длине n (которая составляет примерно log₂n). Например, число n, немного меньшее 10 000 000 000, потребует до 100 000 делений, хотя длина n составляет всего 11 цифр. Более того, можно легко составить входные данные (например, 300-значное число), для которых этот алгоритм станет непрактичным. Поскольку вычислительная сложность измеряет сложность относительно длины (кодированного) ввода, этот наивный алгоритм фактически экспоненциальный. Однако он является псевдополиномиальным по времени. Противопоставьте этот алгоритм истинно полиномиальному числовому алгоритму, например, простому алгоритму сложения: сложение двух 9-значных чисел занимает около 9 простых шагов, и в целом алгоритм действительно линеен по длине ввода. По сравнению с самими числами, которые складываются (в миллиардах), алгоритм можно назвать "псевдологарифмическим по времени", хотя такой термин не является стандартным. Таким образом, сложение 300-значных чисел не является непрактичным. Аналогично, длинное деление является квадратичным: число с m цифрами можно разделить на число с n цифрами за O(mn) шагов (см. нотацию «Большое О»). В случае проверки простоты оказывается, что существует другой алгоритм для проверки того, является ли n простым (открытый в 2002 году), который работает за время O(log¹²n).
Consider the problem of testing whether a number n is prime, by naively checking whether no number in divides evenly. This approach can take up to divisions, which is sub linear in the value of n but exponential in the length of n (which is about ). For example, a number n slightly less than 10,000,000,000 would require up to approximately 100,000 divisions, even though the length of n is only 11 digits. Moreover one can easily write down an input (say, a 300 digit number) for which this algorithm is impractical. Since computational complexity measures difficulty with respect to the length of the (encoded) input, this naive algorithm is actually exponential. It is, however, pseudo polynomial time. Contrast this algorithm with a true polynomial numeric algorithm—say, the straightforward algorithm for addition: Adding two 9 digit numbers takes around 9 simple steps, and in general the algorithm is truly linear in the length of the input. Compared with the actual numbers being added (in the billions), the algorithm could be called "pseudo logarithmic time", though such a term is not standard. Thus, adding 300 digit numbers is not impractical. Similarly, long division is quadratic: an m digit number can be divided by a n digit number in steps (see Big O notation.) In the case of primality, it turns out there is a different algorithm for testing whether n is prime (discovered in 2002) that runs in time .