什么是伪多项式时间?它与多项式时间有何不同? [英] What is pseudopolynomial time? How does it differ from polynomial time?

问题描述

什么是伪多项式时间?它与多项式时间有何不同?一些在伪多项式时间内运行的算法具有 O(nW) 之类的运行时间(对于 0/1 背包问题)或O(√n)(用于试验划分)；为什么那不算是多项式时间?

解决方案

要理解多项式时间和伪多项式时间的区别，我们需要从形式化多项式时间"的含义开始.

多项式时间的常见直觉是某个 k 的时间 O(n^k)".例如，选择排序在时间 O(n²) 内运行，这是多项式时间，而暴力求解 TSP 需要时间 O(n · n!)，这不是多项式时间.>

这些运行时都引用了一些跟踪输入大小的变量 n.例如，在选择排序中，n 指的是数组中元素的数量，而在 TSP 中，n 指的是图中节点的数量.为了在上下文中标准化n"的实际含义，时间复杂度的正式定义将问题的大小"定义如下:

<块引用>

问题输入的大小是写出该输入所需的位数.

例如，如果排序算法的输入是一个 32 位整数数组，则输入的大小将为 32n，其中 n 是数组中的条目数.在具有 n 个节点和 m 个边的图中，输入可能被指定为所有节点的列表，然后是所有边的列表，这需要 Ω(n + m) 位.

给定这个定义，多项式时间的正式定义如下:

<块引用>

如果一个算法的运行时间是 O(x^k) 对于某个常数 k，则该算法在多项式时间内运行，其中 x 表示提供给算法的输入位数.

当使用处理图形、列表、树等的算法时，这个定义或多或少与传统定义一致.例如，假设您有一个对 32 位整数数组进行排序的排序算法.如果您使用选择排序之类的方法来执行此操作，作为数组中输入元素数量的函数，运行时间将为 O(n²).但是输入数组中的元素数 n 与输入的位数如何对应呢?如前所述，输入的位数将为 x = 32n.因此，如果我们用 x 而不是 n 来表示算法的运行时间，我们会得到运行时间为 O(x²)，因此算法在多项式时间内运行.

类似地，假设您对图进行深度优先搜索，这需要时间 O(m +n)，其中 m 是图中的边数，n 是节点数.这与给定的输入位数有什么关系?好吧，如果我们假设输入被指定为邻接表(所有节点和边的列表)，那么如前所述，输入比特的数量将是 x = Ω(m + n).因此，运行时间将为 O(x)，因此算法在多项式时间内运行.

然而，当我们开始谈论对数字进行运算的算法时，事情就崩溃了.让我们考虑测试一个数是否为素数的问题.给定一个数 n，您可以使用以下算法测试 n 是否为素数:

function isPrime(n):对于 i 从 2 到 n - 1:如果 (n mod i) = 0，则返回 false返回真

那么这段代码的时间复杂度是多少?好吧，这个内部循环运行 O(n) 次，每次都做一些工作来计算 n mod i(作为一个非常保守的上限，这当然可以在 O(n³)).因此，这个整体算法的运行时间为 O(n⁴) 并且可能要快得多.

2004 年，三位计算机科学家发表了一篇名为PRIMES is in P的论文 给出一个多项式时间算法来测试一个数是否为素数.这被认为是具有里程碑意义的结果.那么有什么大不了的呢?我们不是已经有一个多项式时间算法，即上面的那个吗?

不幸的是，我们没有.请记住，时间复杂度的正式定义谈到了算法的复杂度作为输入位数的函数.我们的算法在 O(n⁴)，但是作为输入位数的函数是什么?好吧，写出数字 n 需要 O(log n) 位.因此，如果让 x 为写出输入 n 所需的位数，则该算法的运行时间实际上是 O(2^4x)，不是x 中的多项式.

这是多项式时间和伪多项式时间之间区别的核心.一方面，我们的算法是O(n⁴)，看起来像一个多项式，但另一方面，在多项式时间的正式定义下，它不是多项式时间.

要直观了解为什么该算法不是多项式时间算法，请考虑以下问题.假设我希望算法必须做很多工作.如果我写出这样的输入:

<块引用>

10001010101011

那么它需要一些最坏情况下的时间，比如 T，才能完成.如果我现在在数字末尾添加一位，如下所示:

<块引用>

100010101010111

运行时间现在(在最坏的情况下)为 2T.只需多加一点，我就可以将算法的工作量加倍！

如果运行时间是输入数值中的多项式，而不是表示它所需的位数，那么算法会在伪多项式时间中运行.我们的素数测试算法是伪多项式时间算法，因为它在 O(n⁴) 时间内运行，但它不是多项式时间算法，因为作为写出所需的位数 x 的函数输入，运行时间是 O(2^4x).PRIMES is in P"论文如此重要的原因是它的运行时间(大约)是 O(log¹² n)，作为比特数的函数是 O(x¹²).

那么为什么这很重要?好吧，我们有许多用于分解整数的伪多项式时间算法.但是，从技术上讲，这些算法是指数时间算法.这对密码学非常有用:如果您想使用 RSA 加密，您需要能够相信我们不能轻易分解数字.通过将数字中的位数增加到一个很大的值(例如 1024 位)，您可以使伪多项式时间因式分解算法必须花费的时间变得如此之大，以至于完全不可能将数字.另一方面，如果我们可以找到一个多项式时间分解算法，则不一定是这种情况.添加更多的位可能会导致工作量增长很多，但增长只会是多项式增长，而不是指数增长.

也就是说，在许多情况下，伪多项式时间算法非常好，因为数字的大小不会太大.例如，计数排序 的运行时间为 O(n + U)，其中 U 是数组中的最大数.这是伪多项式时间(因为 U 的数值需要 O(log U) 位来写出，所以运行时间是输入大小的指数).如果我们人为地约束 U 以使 U 不会太大(例如，如果我们让 U 为 2)，那么运行时间为 O(n)，这实际上是多项式时间.这就是基数排序的工作原理:通过一次一位处理数字，每一轮的运行时间是 O(n)，所以总的运行时间是 O(n log U).这实际上是多项式时间，因为写出n个数字进行排序使用Ω(n)位，log U的值与写出最大值所需的位数成正比数组.

希望这有帮助！

What is pseudopolynomial time? How does it differ from polynomial time? Some algorithms that run in pseudopolynomial time have runtimes like O(nW) (for the 0/1 Knapsack Problem) or O(√n) (for trial division); why doesn't that count as polynomial time?

解决方案

To understand the difference between polynomial time and pseudopolynomial time, we need to start off by formalizing what "polynomial time" means.

The common intuition for polynomial time is "time O(n^k) for some k." For example, selection sort runs in time O(n²), which is polynomial time, while brute-force solving TSP takes time O(n · n!), which isn't polynomial time.

These runtimes all refer to some variable n that tracks the size of the input. For example, in selection sort, n refers to the number of elements in the array, while in TSP n refers to the number of nodes in the graph. In order to standardize the definition of what "n" actually means in this context, the formal definition of time complexity defines the "size" of a problem as follows:

The size of the input to a problem is the number of bits required to write out that input.

For example, if the input to a sorting algorithm is an array of 32-bit integers, then the size of the input would be 32n, where n is the number of entries in the array. In a graph with n nodes and m edges, the input might be specified as a list of all the nodes followed by a list of all the edges, which would require Ω(n + m) bits.

Given this definition, the formal definition of polynomial time is the following:

An algorithm runs in polynomial time if its runtime is O(x^k) for some constant k, where x denotes the number of bits of input given to the algorithm.

When working with algorithms that process graphs, lists, trees, etc., this definition more or less agrees with the conventional definition. For example, suppose you have a sorting algorithm that sorts arrays of 32-bit integers. If you use something like selection sort to do this, the runtime, as a function of the number of input elements in the array, will be O(n²). But how does n, the number of elements in the input array, correspond to the the number of bits of input? As mentioned earlier, the number of bits of input will be x = 32n. Therefore, if we express the runtime of the algorithm in terms of x rather than n, we get that the runtime is O(x²), and so the algorithm runs in polynomial time.

Similarly, suppose that you do depth-first search on a graph, which takes time O(m + n), where m is the number of edges in the graph and n is the number of nodes. How does this relate to the number of bits of input given? Well, if we assume that the input is specified as an adjacency list (a list of all the nodes and edges), then as mentioned earlier the number of input bits will be x = Ω(m + n). Therefore, the runtime will be O(x), so the algorithm runs in polynomial time.

Things break down, however, when we start talking about algorithms that operate on numbers. Let's consider the problem of testing whether a number is prime or not. Given a number n, you can test if n is prime using the following algorithm:

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

So what's the time complexity of this code? Well, that inner loop runs O(n) times and each time does some amount of work to compute n mod i (as a really conservative upper bound, this can certainly be done in time O(n³)). Therefore, this overall algorithm runs in time O(n⁴) and possibly a lot faster.

In 2004, three computer scientists published a paper called PRIMES is in P giving a polynomial-time algorithm for testing whether a number is prime. It was considered a landmark result. So what's the big deal? Don't we already have a polynomial-time algorithm for this, namely the one above?

Unfortunately, we don't. Remember, the formal definition of time complexity talks about the complexity of the algorithm as a function of the number of bits of input. Our algorithm runs in time O(n⁴), but what is that as a function of the number of input bits? Well, writing out the number n takes O(log n) bits. Therefore, if we let x be the number of bits required to write out the input n, the runtime of this algorithm is actually O(2^4x), which is not a polynomial in x.

This is the heart of the distinction between polynomial time and pseudopolynomial time. On the one hand, our algorithm is O(n⁴), which looks like a polynomial, but on the other hand, under the formal definition of polynomial time, it's not polynomial-time.

To get an intuition for why the algorithm isn't a polynomial-time algorithm, think about the following. Suppose I want the algorithm to have to do a lot of work. If I write out an input like this:

10001010101011

then it will take some worst-case amount of time, say T, to complete. If I now add a single bit to the end of the number, like this:

100010101010111

The runtime will now (in the worst case) be 2T. I can double the amount of work the algorithm does just by adding one more bit!

An algorithm runs in pseudopolynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it. Our prime testing algorithm is a pseudopolynomial time algorithm, since it runs in time O(n⁴), but it's not a polynomial-time algorithm because as a function of the number of bits x required to write out the input, the runtime is O(2^4x). The reason that the "PRIMES is in P" paper was so significant was that its runtime was (roughly) O(log¹² n), which as a function of the number of bits is O(x¹²).

So why does this matter? Well, we have many pseudopolynomial time algorithms for factoring integers. However, these algorithms are, technically speaking, exponential-time algorithms. This is very useful for cryptography: if you want to use RSA encryption, you need to be able to trust that we can't factor numbers easily. By increasing the number of bits in the numbers to a huge value (say, 1024 bits), you can make the amount of time that the pseudopolynomial-time factoring algorithm must take get so large that it would be completely and utterly infeasible to factor the numbers. If, on the other hand, we can find a polynomial-time factoring algorithm, this isn't necessarily the case. Adding in more bits may cause the work to grow by a lot, but the growth will only be polynomial growth, not exponential growth.

That said, in many cases pseudopolynomial time algorithms are perfectly fine because the size of the numbers won't be too large. For example, counting sort has runtime O(n + U), where U is the largest number in the array. This is pseudopolynomial time (because the numeric value of U requires O(log U) bits to write out, so the runtime is exponential in the input size). If we artificially constrain U so that U isn't too large (say, if we let U be 2), then the runtime is O(n), which actually is polynomial time. This is how radix sort works: by processing the numbers one bit at a time, the runtime of each round is O(n), so the overall runtime is O(n log U). This actually is polynomial time, because writing out n numbers to sort uses Ω(n) bits and the value of log U is directly proportional to the number of bits required to write out the maximum value in the array.

Hope this helps!

这篇关于什么是伪多项式时间?它与多项式时间有何不同?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！