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

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

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

즉, 많은 경우 의사 다항식 시간 알고리즘은 숫자의 크기가 너무 크지 않기 때문에 완벽합니다. 예를 들어, 계수 정렬 에는 런타임 O (n + U)가 있습니다. 여기서 U는 배열에서 가장 큰 숫자입니다. 이것은 의사 다항식 시간입니다 (U의 숫자 값을 쓰려면 O (log U) 비트가 필요하므로 런타임은 입력 크기에서 지수 적입니다). U가 너무 크지 않도록 인위적으로 U를 제한하면 (예 : U를 2로두면) 런타임은 실제로 다항식 시간 인 O (n)입니다. 이것이 기수 정렬이 작동 하는 방식입니다. 한 번에 한 비트 씩 숫자를 처리하면 각 라운드의 실행 시간이 O (n)이므로 전체 실행 시간은 O (n log U)입니다. 이것은 실제로 입니다 정렬을 위해 n 개의 숫자를 쓰는 것은 Ω (n) 비트를 사용하고 log U의 값은 배열의 최대 값을 쓰는 데 필요한 비트 수에 정비례하기 때문에 다항식 시간입니다.

도움이 되었기를 바랍니다!

답변

// 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

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)