의사-폴리놈 시간

계산 복잡성 이론에서 숫자 알고리즘은 실행 시간이 입력의 숫자 값(입력에서 가장 큰 정수)에 있는 다항식이지만, 반드시 입력 길이(입력을 나타내기 위해 필요한 비트 수)에 있는 것은 아닌 경우 다항식 시간 알고리즘의 경우에 해당된다.^[1]

일반적으로 입력의 숫자 값은 입력 길이에 지수적이므로, 유사 다항 시간 알고리즘이 입력 길이에 대해 반드시 다항 시간 내에 실행되지는 않는다.

알려진 의사-폴리놈 시간 알고리즘의 NP-완전 문제를 약하게 NP-완전이라고 한다.P = NP가 아닌 한 사이비-폴리놈 시간 알고리즘으로 해결할 수 없다는 것이 입증되면 NP-완전성 문제를 강하게 NP-완전성은 강력한 NP-완전성이라고 불린다.강한/약한 종류의 NP-강도는 유사하게 정의된다.

예

프라이머리티 테스트

$\{{\displaystyle 2,}$ ${\displaystyle 3}$,${\displaystyle \dots ,}$ n ${\displaystyle \}}$ ${\displaystyle \{2,3,\dots,{\sqrt{n$$}\}}$에 숫자가 없는지$$ 순진하게 확인하여 $n$이 $원시$인지 여부를 테스트하는 문제를 고려하십시오$.$이 접근방식은 $최대{\displaystyle \sqrt{}\mathrm{n}}$ - 1 ${\displaystyle {\sqrt{n1}개의$눈금을$$ 취할 수 있으며, 이는 n 값은 하위 선형이지만 n의 길이에서는 지수적이다(log${\displaystyle \log }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaysty \log(n)}$에 대한 것이다).$$예를 들어, n의 길이가 11자리 숫자임에도 불구하고 n의 숫자가 1,000,000,000,000보다 약간 작으면 최대 100,000개의 눈금이 필요하다.게다가 이 알고리즘이 비실용적인 입력(예: 300자리 숫자)을 쉽게 기록할 수 있다.계산 복잡성은 (인코딩된) 입력의 길이에 관해서 난이도를 측정하기 때문에, 이 순진한 알고리즘은 사실 기하급수적이다.그러나 사이비-폴리네마 시간이다.

이 알고리즘을 실제 다항식 숫자 알고리즘과 비교하십시오. 예를 들어, 추가하기 위한 간단한 알고리즘:9자리 숫자 두 개를 추가하면 약 9개의 간단한 단계가 필요하며, 일반적으로 알고리즘은 입력 길이에서 정말로 선형이다.(수십억에서) 추가되는 실제 숫자와 비교했을 때, 그러한 용어는 표준이 아니지만, 알고리즘은 "의사-로고시"라고 불릴 수 있다.따라서 300자리 숫자를 추가하는 것은 비현실적이지 않다.마찬가지로, 긴 분할은 2차분법이다. m자리 숫자는 O (${\displaystyle m}$ ${\displaystyle n}$ $){\displaystyle O(mn)}$단계에서$$ n자리 숫자로 나눌 수 있다(Big O 표기법 참조).

primality의 경우, $시간{\displaystyle }$ O${\displaystyle }$( ( ( ${\displaystyle log}$ ${\displaystyle {}^{}}$n )${\displaystyle {}^{}{6\mathrm{}}^{}}$ $){\displaystyle O(\log {n}^{6})$로 실행되는 n이 primary인지 (2002년에 발견됨) 테스트하기 위한 알고리즘이 다른 것으로 밝혀졌다$.$

배낭문제

배낭 문제에서$,$ 우리는 $배낭{\displaystyle }$ W ${\displaystyle$ $w_{i$$}$의 최대 중량 용량과 $함께{\displaystyle {}_{}}$ $무게{\displaystyle }$ ${\displaystyle w_{}}$ ${\displaystyle i_{}}$ ${\$}의$$ n ${\displaystyle$ $v_${i$}$을 부여받는다$.$ 목표는 다음과 같은 최적화 문제를 해결하는 것이다. 비공식적으로, 무엇이 가장 적합한가?가치를 극대화하기 위해 배낭에 아이템을 넣는 것은?

$\sum {\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle i_{}}$ ${\$

대상 ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ w ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle i_{}}$≤ ${\displaystyle W}$ ${\displaystyle \sum$ \sum $_{i=1}^{n_{n}x_{i}\leq$ W$} 및$ $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}${$1$ ${\displaystyle x_{i}\in \{0,1\}$.

이 문제를 해결하는 것은 NP-hard이기 때문에 P = NP가 아니면 다항 시간 알고리즘이 불가능하다.그러나 동적 프로그래밍을 사용하여 $O{\displaystyle (n}$ ${\displaystyle W}$) ${\displaystyle O(nW)}$ 시간$$ 알고리즘을 사용할 수 $있다{\displaystyle }$. 숫자$$W {\$displaystyle$ W$}$은(는)${\displaystyle \mathrm{로그}}$W {\$displaystyle \log$ W$$$}$ 비트만$$ 설명하면 되기 때문에 이 알고리즘은 유사-폴리놈 시간에서 실행된다.

숫자가 아닌 문제로 일반화

사이비-폴리놈 시간의 개념은 거의 전적으로 숫자 문제에 사용되지만, 그 개념은 다음과 같이 일반화될 수 있다.m(n)이 문제 크기 n의 다항식 함수와 입력의 추가 속성 k(n)보다 크지 않을 경우 m 함수는 의사-폴리놈이다. (대개 k는 문제와 관련된 것으로 선택된다.)이것은 k를 입력의 숫자값으로 삼음으로써 숫자 다항식 문제를 특별한 경우로 만든다.

숫자의 값과 그 길이의 구별은 인코딩의 하나인데, 숫자 입력이 항상 단수로 인코딩된다면 사이비-폴리노멀은 다항식과 일치할 것이다.

강하고 약한 NP-강성 vs 강하고 약한 다항식 시간 알고리즘

P != NP라고 가정할 때, 정수의 계산 문제에 대해서는 다음과 같은 사항이 적용된다.^[2]

• 문제가 약하게 NP-hard인 경우 약하게 다항 시간 알고리즘(정수 개수의 폴리놈과 가장 큰 정수의 비트수)을 가지지 않지만 유사 다항 시간 알고리즘(정수 개수의 폴리놈과 가장 큰 정수의 크기)을 가질 수 있다.예를 들어 파티션 문제가 있다.약한 NP-강도와 약한 다항식 시간 모두 이진 코딩에서 입력제를 인코딩하는 것에 해당한다.

• 문제가 강하게 NP-hard이면 사이비-폴리놈 시간 알고리즘도 없다.그것은 또한 완전한 다항식 시간 근사 체계를 가지고 있지 않다.그 예가 3파티션 문제다.강한 NP-강도와 의사-폴리놈 시간 모두 입력 에이전트를 단항 코딩으로 인코딩하는 것에 해당한다.

참고 항목

• 강한 NP-완료
• 준폴리네멀 타임

참조