의사 다항식 시간이란 무엇입니까?

의사 다항식 시간이란 무엇입니까? 다항식 시간과 어떻게 다른가요?

---

의사 다항식 시간 이란 무엇입니까 ? 다항식 시간과 어떻게 다른가요? 의사 다항식 시간으로 실행되는 일부 알고리즘에는 O (nW) ( 0/1 Knapsack 문제의 경우 ) 또는 O (√n) ( 시험 분할의 경우 ) 와 같은 런타임이 있습니다 . 다항식 시간으로 계산되지 않는 이유는 무엇입니까?

---

다항식 시간과 의사 다항식 시간의 차이를 이해하려면 먼저 "다항식 시간"이 의미하는 바를 공식화해야합니다.

다항식 시간에 대한 일반적인 직관은 " 일부 k에 대한 시간 O (n ^k )"입니다. 예를 들어 선택 정렬 은 다항식 시간 인 O (n ² ) 시간에 실행되는 반면 무차별 대입 해결 TSP 는 다항식 시간이 아닌 시간 O (n · n!)가 걸립니다.

이러한 런타임은 모두 입력 크기를 추적하는 일부 변수 n을 참조합니다. 예를 들어, 선택 정렬에서 n은 배열의 요소 수를 나타내고 TSP에서 n은 그래프의 노드 수를 나타냅니다. 이 맥락에서 "n"이 실제로 의미하는 바의 정의를 표준화하기 위해 시간 복잡도의 공식적인 정의는 다음과 같이 문제의 "크기"를 정의합니다.

문제에 대한 입력 크기는 해당 입력을 작성하는 데 필요한 비트 수입니다.

예를 들어, 정렬 알고리즘에 대한 입력이 32 비트 정수 배열이면 입력 크기는 32n이됩니다. 여기서 n은 배열의 항목 수입니다. n 개의 노드와 m 개의 에지가있는 그래프에서 입력은 Ω (n + m) 비트가 필요한 모든 에지의 목록이 뒤 따르는 모든 노드 목록으로 지정 될 수 있습니다.

이 정의가 주어지면 다항식 시간의 공식적인 정의는 다음과 같습니다.

알고리즘은 런타임이 일부 상수 k에 대해 O (x ^k ) 이면 다항식 시간에 실행됩니다 . 여기서 x는 알고리즘에 제공된 입력 비트 수를 나타냅니다.

그래프, 목록, 트리 등을 처리하는 알고리즘으로 작업 할 때이 정의는 기존 정의와 어느 정도 일치합니다. 예를 들어 32 비트 정수 배열을 정렬하는 정렬 알고리즘이 있다고 가정합니다. 이를 위해 선택 정렬과 같은 것을 사용하면 배열의 입력 요소 수에 따른 런타임은 O (n ² )가됩니다. 그러나 입력 배열의 요소 수인 n은 입력 비트 수와 어떻게 일치합니까? 앞서 언급했듯이 입력 비트 수는 x = 32n입니다. 따라서 알고리즘의 런타임을 n이 아닌 x로 표현하면 런타임이 O (x ² )이므로 알고리즘이 다항식 시간에 실행됩니다.

마찬가지로 그래프에서 깊이 우선 검색 을 수행한다고 가정합니다. 이 경우 시간 O (m + n)이 걸립니다. 여기서 m은 그래프의 간선 수이고 n은 노드 수입니다. 이것은 주어진 입력 비트 수와 어떤 관련이 있습니까? 입력이 인접 목록 (모든 노드 및 에지 목록)으로 지정되었다고 가정하면 앞에서 언급했듯이 입력 비트 수는 x = Ω (m + n)이됩니다. 따라서 런타임은 O (x)이므로 알고리즘은 다항식 시간에 실행됩니다.

그러나 숫자로 작동하는 알고리즘에 대해 이야기하기 시작하면 상황이 무너집니다. 숫자가 소수인지 아닌지 테스트하는 문제를 생각해 봅시다. 숫자 n이 주어지면 다음 알고리즘을 사용하여 n이 소수인지 테스트 할 수 있습니다.

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

그렇다면이 코드의 시간 복잡성은 무엇입니까? 글쎄, 그 내부 루프는 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 비트)으로 늘림으로써 의사 다항식 시간 분해 알고리즘이 가져야하는 시간이 너무 커져서 인수를 완전하고 완전히 불가능하게 만들 수 있습니다. 번호. 반면에 다항식 시간 분해 알고리즘을 찾을 수 있다면 반드시 그런 것은 아닙니다. 더 많은 비트를 추가하면 작업이 많이 증가 할 수 있지만 성장은 기하 급수적 인 성장이 아닌 다항식 성장 일뿐입니다.

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!

---

Pseudo-polynomial time complexity means polynomial in the value/magnitude of input but exponential in the size of input.

By size we mean the number of bits required to write the input.

From the pseudo-code of knapsack, we can find the time complexity to be O(nW).

// Input:
// Values (stored in array v) 
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W) 
for w from 0 to W 
    do   m[0, w] := 0 
end for  
for i from 1 to n do  
        for j from 0 to W do
               if j >= w[i] then 
                      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 
              else 
                      m[i, j] := m[i-1, j]
              end if
       end for 
end for

Here, W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial.

Let s be number of bits required to represent W

i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W  (because  2^(log(x)) = x)

Now, running time of knapsack= O(nW) = O(n * 2^s) which is not polynomial.

참고URL : https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time