시간 복잡도

계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, Pan Bubilek이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다.

예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n₀보다 크지 않은 모든 n에 대하여) 5n³ + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n³)이라고 할 수 있다.

시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다.

알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라고 했을 때, 이것은 크기 n의 모든 입력에 대해 걸리는 최대의 시간으로 정의할 수 있다.

그 다음으로 덜 흔하게 쓰이면서, 보통 명확하게 서술되는 측정방법은 평균 시간 복잡도이다.

시간 복잡도는 함수 T(n)의 특성에 의해 분류할 수 있다. 예를 들면, T(n)=O(n)인 알고리즘은 선형 시간 알고리즘이라고 부르며, 몇몇 M ≥ n >1에 대해 T(n)=O(Mⁿ)이고 Mⁿ=O(T(n)) 인 알고리즘은 지수 시간 알고리즘이라고 한다.

공통 시간 복잡도 표

이름	복잡도 종류	수행시간 (T(n))	수행 횟수 예시	알고리즘 예시
상수 시간		O(1)	10	정수(이진수로 표현되는)가 짝수이거나 홀수인지 결정
역 아커만 시간 (Inverse Ackermann time)		O(α(n))		서로소 집합을 사용한 연산 당 분할상환 시간
반복 로그 시간 (iterated logarithmic time)		O(log* n)
로그-로그 시간		O(log log n)		유계 우선순위 큐를 사용한 연산 당 분할상환 시간^[1]
로그 시간	DLOGTIME	O(log n)	log n, log(n²)	이진탐색
다항 로그 시간		poly(log n)	(log n)²
분수 지수		O(n^c) where 0 < c < 1	n^1/2, n^2/3	k차원 트리 탐색
선형 시간		O(n)	n	정렬되지 않은 배열에서 가장 작은 수 또는 가장 큰 수를 탐색
"n log^* n" 시간		O(n log* n)		자이델(Seidel)의 다각형 삼각화 알고리즘
선형 로그 시간		O(n log n)	n log n, log n!	가장 빠른 비교정렬: 고속 푸리에 변환
2차 시간		O(n²)	n²	버블 정렬, 삽입 정렬, 직접적 합성곱
3차 시간		O(n³)	n³	n×n 행렬 두 개의 무식한 곱셈, 편상관계 계산
다항 시간	P	2^O(log n) = poly(n)	n, n log n, n¹⁰	선형 계획법을 위한 카르마카(Karmarkar)의 알고리즘, AKS 소수판별법
준 다항 시간	QP	2^poly(log n)	n^log log n, n^log n	유향 슈타이너 트리 문제에 대해 잘 알려진 O(log² n)-근사 알고리즘
서브 지수함수 (1번째 정의)	SUBEXP	O(2^{n^ε}) for all ε > 0	O(2^{log n^{log log n}})	복잡도의 이론적 추측을 생각했을 때, BPP는 SUBEXP에 포함.
서브 지수함수 (2번째 정의)		2^o(n)	2^{n^1/3}	소인수분해와 그래프 동형에 대해 잘 알려진 알고리즘
지수 시간 (선형 지수)	E	2^O(n)	1.1ⁿ, 10ⁿ	동적 계획법을 사용한 외판원 문제 해결방법
지수 시간	EXPTIME	2^poly(n)	2ⁿ, 2^n²	브루트 포스 탐색을 통한 연쇄 행렬 곱셈의 해결방법
팩토리얼 시간		O(n!)	n!	브루트 포스 탐색을 통한 외판원 문제 해결방법
이중 지수 시간	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	프레스버거(Presburger) 산술 명제의 진위 여부 결정

상수 시간 (Constant time)

만약 어떤 알고리즘의 T(n) 값이 입력 크기에 구애받지 않는 값에 의해서 한정된다면, 이 알고리즘은 상수 시간(O(1) 시간이라고 쓰기도 함) 이라고 말할 수 있다. 예를 들면, 단 하나의 연산이 어떤 배열에서의 요소 위치를 알아내는 것을 수행한다고 할 때, 이 요소에 접근하는 것은 상수 시간이 걸린다. 그러나 순서가 정해져있지 않은 배열에서의 최소 값을 찾는 것은, 가장 작은 값을 결정하기 위해 어떤 배열에서의 각 요소를 훑는 것이 필요하기 때문에 상수 시간이 아니다. 이것은 그렇기 때문에 선형 시간 연산이며, O(n)시간이 소요된다. 그러나 만약 요소들의 개수를 미리 알고있고 변화가 없다면, 이러한 알고리즘은 상수 시간에 이루어질 수 있다고 말할 수 있다.

"상수 시간"이라는 이름에도 불구하고, 수행시간은 문제의 크기에 독립적일 필요가 없지만 수행시간의 상한은 문제의 크기에 독립적으로 제한된다. 예를 들면, "필요하다면 a와 b를 바꿔서 a≤b가 되도록 하시오"와 같은 것은, 시간이 이미 a≤b조건 만족여부에 종속적이라고 한다고 해도, 상수 시간을 갖는다고 할 수 있다. 그러나 요구되는 시간이 항상 최대 t인 상수 t가 존재하기도 한다.

아래는 상수 시간 동안 수행되는 코드의 예제이다.

int index = 5;
int item = list[index];

if(조건이 참일 때) then
    상수 시간 동안 수행되는 어떤 연산을 실행
else
    상수 시간 동안 수행되는 어떤 연산을 실행
for i = 1 to 100
    for j = 1 to 200
        상수 시간 동안 수행되는 어떤 연산을 실행

만약 T(n)이 O(어떤 상수값)이라면, 'T(n)은 O(1)이다'라는 것과 동등하며, 이것을 표준 표기법으로 사용한다.

로그 시간 (Logarithmic time)

만약 T(n) = O(log n) 이라면, 이 알고리즘은 로그 시간이 걸린다고 말할 수 있다. 컴퓨터가 이진수 시스템을 사용하기 때문에, 로그는 밑을 대부분 2로 사용한다. (즉, log₂n, 때때로는 log n 이라고 쓰임.) 그러나, 로그의 밑이 변할 때, log_an와 log_bn는 오로지 상수 승수에 따라서만 달라지며 이것은 빅-오 표기법에서는 버림한다; 그러므로 O(log n)은 로그의 밑과 상관없이 로그 시간 알고리즘에 대한 표준 표기법이 된다.

로그시간이 걸리는 알고리즘은 이진트리에서의 연산에서나 또는 이진 탐색에서 찾아볼 수 있다.

O(log n)알고리즘은 인스턴스당 연산이 각 인스턴스에 대해서 최대한 줄어드는 것이 필요하기 때문에, 높은 효율을 갖고 있다고 여긴다.

이런 타입의 가장 쉬운 예제 알고리즘은, 문자열을 절반으로 쪼개어 그 오른쪽의 문자열을 다시 또 절반으로 쪼개고, 이를 반복하는 알고리즘으로 생각할 수 있다. 이 알고리즘은 우리가 각각의 출력 이전에 문자열을 절반으로 나누기 때문에, O(log n)시간 (n은 문자열의 길이) 이 소요된다. 이것은 출력 횟수를 증가시키기 위해서는 문자열의 길이를 두배로 늘려야 함을 의미한다.

// 문자열의 오른쪽 절반을 재귀적으로 출력하는 함수.
var right = function(str){
    var length = str.length;

    // Helper function
    var help = function(index){

        //재귀호출 부분: 오른쪽 절반을 출력
        if(index < length){

            //인덱스로 배열 끝까지 문자 출력
            console.log(str.substring(index, length));

            //재귀 호출 부분: 오른쪽 절반에 대해서 help를 호출
            help(Math.ceil((length + index)/2));
        }

        // Base Case: Do Nothing
    }
    help(0);
}

다항 로그 시간 (Polylogarithmic time)

만약 T(n) = O((log n)^k) 이라면, 이 알고리즘은 어떤 상수k에 대해 다항 로그 시간 동안 수행된다고 말할 수 있다. 예를 들면, 행렬 체인 곱은 병렬 랜덤 접근 기계 (Parallel Random Access Machine: PRAM)에서 다항 로그 시간에 해결할 수 있다.

서브-선형 시간 (Sub-linear time)

만약 T(n) = o(n) 이면, 이 알고리즘은 서브-선형시간 동안 작동된다고 말할 수 있다. 특히 이 알고리즘은 위에서 정의된 시간 복잡도들을 가진 것들을 포함하며, O(n^1/2) 인 Grover 탐색 알고리즘을 포함한다.

서브-선형 시간 동안 작동하는 전형적인 알고리즘들은 병렬 프로세싱, 비표준 프로세싱을 사용하거나, 입력 구조에 대한 보장된 가정을 갖는다. 그러나 문자열의 처음부터 log(n)번째 비트 위치에서의 한 개의 비트를 갖는 모든 문자열의 집합과 같은 형식 언어는 입력의 모든 비트에 종속적일 수 있고, 서브-선형 시간에 가깝게 계산될 것이다.

서브-선형 시간 알고리즘이라는 특정 용어는 알고리즘들이 전형적인 일렬 기계 모델에서 작동하며 입력에 대해 우선 가정을 허용하지 않는다는 점에서, 위와는 다른 알고리즘을 말한다. 그러나 이 알고리즘들은 랜덤화 될 수 있고, 거의 가장 사소한 정도의 태스크들에 대해서는 반드시 랜덤화되어야만 한다.

이러한 알고리즘은 반드시 전체 입력을 읽지 않고 결과를 제공해야 하기 때문에, 이것의 특별함은 상세 명세는 입력에 허용되는 접근에 굉장히 종속적이다. 보통 b₁,..., b_k 로 표현되는 이진 문자열에 대해서, 알고리즘이 어떤 i에 대해 b_i의 값을 요청하거나 얻는데 O(1) 시간이 걸린다고 가정할 수 있다.

서브-선형 시간 알고리즘은 보통 랜덤화되며, 오로지 대략적인 해결책만을 제공해준다. 사실, 0만 가지는 이진 문자열의 특성은 (비근사적인) 서브-선형 시간 알고리즘에 의해서 결정될 수 없다는 것을 쉽게 증명할 수 있다. 서브-선형 시간 알고리즘은 특성 테스팅 (Property testing) 조사에서 자연스럽게 나타난다.

선형 시간 (Linear time)

만약 시간복잡도가 O(n)이면, 이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다. 약식으로 충분히 큰 입력 크기에 대해서 수행시간이 입력 크기에 따라 선형적으로 증가함을 의미한다. 예를 들어, 리스트의 모든 요소를 더하는 프로시저는 리스트의 길이에 비례하는 시간을 요구한다. 이러한 설명은 수행시간이 특히 작은 n의 값에 대해, 정확한 선형적인 비례형태로부터 상당히 편차를 가질 수 있기 때문에 다소 부정확하다.

종종 선형 시간은 알고리즘의 이상적인 특성으로 여겨진다. 많은 연구자들은 선형 시간이나 그보다 더 좋은 알고리즘을 만드는 것을 연구해왔다. 이러한 연구는 소프트웨어와 하드웨어적인 방법 모두를 포함한다. 수학적으로, 표준 계산 모델을 사용해 선형 시간을 절대 얻을 수 없는 알고리즘들은 하드웨어적인 관점에서 선형 시간 동안 실행될 수 있다. 이것을 제공하는 병렬식 방법을 이용하는 하드웨어 기술이 존재하며, 예로 content-addressable 메모리와 같은 것이 있다. 이러한 선형시간 개념은 Boyer-Moore 알고리즘과 Ukkonen 알고리즘과 같은 문자열 매칭 알고리즘에서 사용된다.

유사 선형 시간 (Quasilinear time)

어떤 양의 상수 k 에 대해서 T(n) = O(n log^kn) 이면, 이 알고리즘은 유사 선형 시간 동안 실행된다고 말할 수 있다; 선형로그 시간은 k=1인 경우이다. 소프트-오 표기법을 사용하면, 이 알고리즘은 Õ(n)이다. 유사 선형 시간 알고리즘은 모든 ɛ < 0 에 대해서 O(n^1+ɛ)이고, 그러므로 1보다 엄격하게 큰 지수를 가진 n에서의 모든 다항식 보다 빠르다.

유사 선형시간에서 실행되는 알고리즘들은, 선형 로그 알고리즘에 덧붙여 다음을 포함한다.

In-place 합병 정렬, O(n log²n)
퀵 정렬, O(n log n), 랜덤화된 버전에서는 최악의 경우 입력에 대한 평균에서의 선형로그 시간을 수행시간으로 갖는다.
힙 정렬, O(n log n), 합병 정렬, intro정렬, 이진 트리 정렬, smooth정렬, patience 정렬 등에서의 최악의 경우.
고속 퓨리에 변환, O(n log n)
Monge 배열 계산, O(n log n)

선형 로그 시간 (Linearithmic time)

선형 로그 시간은 지수 k가 로그 항의 하나와 동일한 유사 선형 시간의 특이한 경우이다. 선형 로그 함수는 n log n 형태의 함수 즉, 선형과 로그항의 곱이다. 만약 T(n) = O(n log n) 이라면, 알고리즘은 선형로그 시간 동안 실행된다고 말할 수 있다. 그러므로 선형로그 항은 선형 항 보다는 빠르게 증가하지만, 1보다 큰 지수를 가진 n의 다항식보다는 느리다.

많은 경우에, n log n 수행시간은 간단히 Θ(log n) 연산의 n 배 수행시간의 결과를 가진다. 예를 들면, 이진 트리 정렬은 n 크기의 배열 각 요소를 하나하나 삽입하여 이진 트리를 만든다. 자가 균형 이진 탐색 트리의 삽입 연산은 O(log n)시간이 걸리기 때문에, 전체 알고리즘은 선형 로그 시간이 걸린다.

비교 정렬은 Stirling 근사에 의해 log(n!) = Θ(n log n)이기 때문에, 최악의 경우 비교 횟수가 최소 선형 로그가 필요하다. 그리고 또한 T(n) = 2T(n/2) + O(n) 재귀 관계에서 빈번히 나타난다.

서브-이차 시간 (Sub-quadratic time)

만약 T(n) = o(n²)이면, 서브-이차 시간의 알고리즘이라고 말할 수 있다.

예를 들면, 간단히 비교 기반 정렬 알고리즘은 이차 (예를 들면, 삽입 정렬)이지만 더 심화된 알고리즘은 서브-이차 (예를 들면, 쉘 정렬)인 것을 찾을 수 있다. 어떤 범용 정렬도 선형시간에 수행될 수 없지만, 이차에서 서브 이차로의 변경은 대단히 현실적으로 중요하다.

다항 시간 (Polynomial time)

만약 어떤 상수 k에 대해 T(n) = O(n^k)와 같이, 입력 크기에 어떤 다항 표현의 상한을 가지고 수행이 되는 알고리즘이 있다면, 그 알고리즘은 다항 시간을 가진다고 말할 수 있다. 결정론적 다항시간 알고리즘 (deterministic polynomical time algorithm) 이 존재하는지에 대한 문제들은 복잡도 클래스 P에 속하며, 이 복잡도 클래스 P는 계산 복잡도 이론 분야에서 핵심을 차지한다. Cobham 논제는 다항 시간이 "추적 가능한", "실현 가능한", "효율적인" 또는 "빠른" 과 같은 동의어를 갖는다고 언급한다.

몇 가지 다항 시간 알고리즘의 예를 들면,

정수 n에 대한 선택 정렬 알고리즘이 상수 A에 대해서 $An^{2}$ 개의 연산을 수행한다. 그렇다면 이것은 $O(n^{2})$ 의 시간 동안 수행되며, 다항시간 알고리즘이라고 할 수 있다.
모든 기본 산술 연산 (덧셈, 뺄셈, 곱셈, 나눗셈 그리고 비교)는 다항시간 동안 이루어진다.
그래프에서의 최대 매칭은 다항 시간 동안 찾을 수 있다.

강력한 다항 시간과 약한 다항시간

일부 문맥에서는, 특히 최적화의 경우, 강력한 다항 시간과 약한 다항 시간 알고리즘 사이에 차별점이 존재한다. 이 두 개념은 만약 알고리즘의 입력이 정수로 구성되어 있을 때만 관련이 있다.

강력한 다항시간은 계산의 산술 모델에서 정의된다. 이 산술 모델에서 기본 산술 연산은 피연산자의 크기에 상관없이 수행하는데 단위 시간 단계가 소요된다. 알고리즘은 아래와 같은 경우, 강력한 다항 시간에 수행된다고 할 수 있다.

계산의 산술 모델에서 연산의 횟수는 입력 인스턴스의 정수 개수를 가지고 다항식으로 경계값을 갖는다.
알고리즘의 공간은 입력 크기가 다항식으로 경계값을 가진다.

위와 같은 특성을 가진 모든 알고리즘들은 튜링 머신에서 산술 연산을 수행하는 적합한 알고리즘을 사용해 산술 연산을 교체하는 것으로 다항시간 알고리즘화 할 수 있다. 만약 두 번째의 요구사항이 충족되지 않으면, 다항시간 알고리즘화의 가능성은 더 이상 만족하지 않는다. 튜링 머신에서 n에 비례하는 공간을 차지하는 정수 $2^{n}$ 이 주어졌을 때, 반복 제곱을 사용해서 n회 곱한 $2^{2^{n}}$ 을 계산하는 것이 가능하다. 그러나 $2^{2^{n}}$ 을 표현하는 데 쓰이는 공간은 $2^{n}$ 에 비례하므로, 입력을 표현하는데 쓰이는 공간은 다항 공간이기 보다는 지수 공간이다. 그러므로 튜링 머신에서 다항시간에 이 계산의 결과값을 도출해내는 것은 불가능하지만, 다항 시간을 갖는 많은 산술 연산을 가지고 이것을 계산하는 것은 가능하다.

뒤집어 생각해보면, 2진 인코딩된 입력 길이로 다항식 경계가 지어진 많은 튜링 머신 단계에서 작동하는 알고리즘들이 있다. 그러나, 입력 수의 개수로 다항식 경계가 지어진 많은 산술 연산들은 채택하지 않는다. 두 정수의 최대 공약수를 계산하기 위한 유클리디안 알고리즘은 그 하나의 예이다. 알고리즘의 수행시간이 주어진 두 개의 정수 a와 b에 대해서 $O((\log a+\log b)^{2})$ 튜링 머신 단계로 경계를 갖는다. 표현의 크기가 대략적으로 $\log a+\log b$ 일 때, a와 b의 이진 표현의 크기가 다항 크기를 갖는다. 동시에, 산술 연산 개수는 입력에서의 정수 개수로 제한될 수 없다. (이 때의 입력값은 상수이고, 입력에서의 정수는 항상 2개이다.) 후자의 관측으로 인해, 강력한 다항 시간에서 이 알고리즘은 작동할 수 없다. 이것의 실제 실행 시간은 a와 b의 크기에 의존하며, 입력값에서 정수 개수에도 의존한다.

다항 시간에 작동하지만 강력한 다항 시간은 아닌 알고리즘은 약한 다항 시간 동안에 작동한다고 말할 수 있다. 약한 다항 시간 알고리즘으로 알려져있는 문제중에 가장 유명한, 하지만 강력한 다항 시간 알고리즘은 아닌 예제는 선형 계획법이다. 약한 다항시간은 유사 다항 시간과 헷갈려서는 안된다.

복잡도 클래스

다항 시간의 개념은 계산 복잡도 이론에서 여러 가지 복잡도 클래스로 연결된다. 몇 가지 중요한 다항 시간이 사용되어 정의된 클래스들은 다음과 같다.

P: 다항 시간 동안 결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
NP: 다항 시간 동안 비결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
ZPP: 다항 시간 동안 확률적 튜링 머신에서 0의 에러확률로 해결할 수 있는 결정 문제의 복잡도 클래스
RP: 다항 시간 동안 확률적 튜링 머신에서 단방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
BPP: 다항 시간 동안 확률적 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
BQP: 다항 시간 동안 양자 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스

P는 머신 모델 변화의 측면에서 강건한 결정적 머신에 대해 가장 작은 시간 복잡도 클래스를 나타낸다. 모든 주어진 추상 머신은 해당 머신에 대해 다항 시간 동안 해결할 수 있는 문제에 해당하는 복잡도 클래스를 갖는다.

초다항 시간 (Superpolynomial time)

만약 T(n)이 모든 다항식 위에서 경계를 갖지 않는다면, 이것을 초다항 시간이 걸리는 알고리즘이라고 말할 수 있다. 이것은 모든 상수 c에 대해서 n이 입력 파라미터 일 때, ω(n^c)시간을 갖는다. (일반적으로, 이 n은 입력값에서의 비트 개수를 뜻한다.)

예를 들면, 크기 n 의 입력값에 대해 2ⁿ단계 실행되는 알고리즘은 초다항 시간을 요구한다. (좀 더 정확히 말하자면, 지수 시간이다.)

지수 자원을 사용하는 알고리즘은 분명하게 초다항이지만, 어떤 알고리즘들은 매우 약한 초다항일 뿐이다. 예를 들면, Adelman-Pomerance-Rumely 소수성 테스트가 n비트의 입력에 대해서 n^{O(log log n)}의 시간 동안 실행된다; 이것은 충분히 큰 n에 대해서 모든 다항 시간보다 빠르다. 하지만 입력 크기는 반드시 이것이 작은 지수의 다항식에 의해 지배될 수 없기 전에 비현실적인 크기가 되어야만 한다.

초다항 시간을 필요로하는 알고리즘은 복잡도 클래스 P밖에 놓인다. Cobham 논제는 이런 알고리즘이 비현실적임을 받아들인다. P vs. NP문제가 해결되지 않았기 때문에, 어떤 NP완비 문제도 다항 시간 동안 실행될 수 있다고 알려진 것이 없다.

준-다항 시간 (Quasi-polynomial time)

준-다항 시간 알고리즘은 다항 시간보다 느리지만 지수 시간보다는 느리지 않은 알고리즘이다. 준-다항 시간 알고리즘의 최악의 경우 시간은, 어떤 고정된 $c>0$ 에 대해 $2^{O((\log n)^{c})}$ 값을 갖는다. 정수 인수분해에 대해 $2^{{\tilde {O}}(n^{1/3})}$ 시간이 소요되는 가장 잘 알려진 고전 알고리즘인 대표 숫자 영역 거르기 (general number field sieve)는 실행 시간이 고정된 c에 대해서 $2^{O((\log n)^{c})}$ 로 나타낼 수 없기 때문에 준-다항시간 알고리즘이 아니다. 만약 준-다항 시간 알고리즘 정의에서의 상수 c가 1과 같다면, 우리는 다항시간 알고리즘을 얻을 수 있고, 1보다 작다면, 서브 선형 시간 알고리즘을 얻을 수 있다.

준-다항 시간 알고리즘은 전형적으로 NP-난제 문제에서 다른 문제로의 환원에서 생길 수 있다. 예를 들면, NP-난제 문제 하나가 3SAT이고, 이것을 다른 문제 B로 바꾸지만 이 문제의 크기는 $2^{O((\log n)^{c})}$ 이다. 이런 경우, 이 환원은 문제 B가 NP-난제임을 증명할 수 없다; 이 환원은 만약 3SAT에 대한 준-다항 시간 알고리즘이 없다면, 단지 B에 부합하는 다항시간 알고리즘이 없다는 것만을 보여줄 수 있다.

비슷하게, 우리가 알고있는 준-다항 시간 알고리즘은 몇가지 있지만, 다항 시간 알고리즘은 없다. 이런 문제는 근사 알고리즘에서 발생한다; 가장 유명한 예제는 방향성 Steiner 트리 문제이고, 이 문제는 정점 개수가 n인 트리에서 $O(\log ^{3}n)$ 의 근사 인자를 달성하는 준-다항 시간 근사 알고리즘이다. 그러나, 다항 시간 알고리즘의 존재를 보여주는 것은 열린 문제이다.

다항시간은 아니지만, 준-다항 시간인 다른 해결 계산 문제들은 László Babai에 의한 그래프 동형 문제와 클릭의 합집합과 랜덤 그래프에서 가장 큰 클릭을 찾는 목표를 가지고 있는 planted clique 문제가 있다.

준-다항 알고리즘이 해결가능하긴 하지만, planted clique 문제는 다항 시간 해결방법이 없다고 추측된다; 이 planted clique의 경우는 계산 게임이론, 특성 테스팅, 기계학습에서의 다른 여러 문제들의 어려운 정도를 증명하기 위한 계산 난제 가정 (computational hardness assumption) 으로서 사용된다.

QP 복잡도 클래스는 모두 준-다항 시간 알고리즘으로 이루어져있다. 이것은 다음의 DTIME으로 정의된다.

${\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})$

NP-완비문제와의 연관

복잡도 이론에서, 미해결 문제인 P vs. NP문제는 NP문제 모두가 다항 시간 알고리즘인지의 여부를 묻는다. 3SAT문제 등과 같은, 모든 알려진 NP-완비문제 알고리즘들은 지수 시간이 걸린다. 실제로, 서브-지수 시간 알고리즘을 가지지 않는 많은 자연 NP-완비 문제들에 대해 추측이 되어왔다. 여기서 "서브-지수 시간"은 아래 두번째 정의에 표시되어 있다. (반면, 인접 행렬 방법을 사용한 많은 그래프 문제들은 입력 크기가 정점 개수의 제곱이기 때문에, 서브 지수 시간에 해결이 가능하다.)

이러한 k-SAT문제에 대한 가정은 지수 시간 가정으로 알려져있다. NP-완비 문제가 준-다항 시간 알고리즘을 갖고있지 않다고 생각되기 때문에, 근사 알고리즘 영역에서 근사적이지 않은 결과는 NP-완비 문제가 준-다항 시간 알고리즘을 갖지 않는다는 가정을 만든다. 예를 들면, 집합 덮개 문제의 비근사적 결과와 같은 것이다.

서브-지수 시간 (Sub-exponential time)

서브-지수 시간이라는 용어는 어떤 알고리즘의 수행시간이 다항시간보다 빠르지만 현저히 지수시간 보다는 작게 증가하는 것을 표현하는데 사용한다. 이러한 점에서, 서브-지수 시간 알고리즘은 오로지 지수 알고리즘보다는 다소 더 추적이 가능한 문제들이다. "서브-지수 시간"의 정확한 정의는 동의가 되어있지 않고, 아래의 두 정의가 폭넓게 사용되고 있다.

첫 번째 정의

만약 어떤 알고리즘이 주어진 다항식보다 작게 증가하는 수행시간 안에 해결될 수 있다면, 그 문제는 서브-지수 시간이 걸린다고 말한다. 더 정확하게는, 모든 ε > 0에 대해서 O(2^{n^ε}) 시간에 문제를 해결하는 알고리즘이 존재한다면, 서브-지수 시간 문제이다. 이러한 문제들은 다음과 같이 DTIME으로 정의되는 SUBEXP 복잡도 클래스를 갖는다.

{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)

서브-지수 표기법은, 입력 값의 부분이 아니라는 점과 각 ε이 해당 문제만의 알고리즘을 갖고있다는 점에서 ε에 대해 비균일하다.

두 번째 정의

어떤 사람들은 2^o(n) 로 서브-지수 시간을 정의한다. 이 정의는 서브-지수 시간의 첫번째 정의보다는 더 큰 실행 시간이 허용된다. 예제로는, 정수 인수분해하는 가장 잘 알려진 고전 알고리즘인 대표 숫자 영역 거르기 (general number field sieve) 가 있으며, 이것의 실행 시간은 입력 크기가 n의 길이를 가질 때, $2^{{\tilde {O}}(n^{1/3})}$ 를 갖는다. 또 다른 예제는 그래프 동형 문제로 $2^{O({\sqrt {n\log n}})}$ 시간이 소요된다.

이것은 알고리즘이 인스턴스의 크기, 정점의 개수 또는 간선의 개수에서 서브-지수가 되는 것을 허용하는 알고리즘인지의 여부에 따라 다르다는 것을 명심하자. 매개변수화 복잡도에서는, 이러한 차이점이 결정 문제의 $(L,k)$ 페어와 인자 k를 고려하는 것으로서 분명해진다. SUBEPT는, 입력 크기 n일 때 다항이며 k에 대해 서브-지수시간 수행되는 모든 매개변수화 문제의 복잡도 클래스이다.

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).

더 정확하게 SUBEPT는 계산 가능한 함수 $f:\mathbb {N} \to \mathbb {N}$ with $f\in o(k)$ 에 대해서 모든 매개변수화 문제 $(L,k)$ 의 복잡도 클래스이며, 알고리즘은 $2^{f(k)}\cdot {\text{poly}}(n)$ 시간 동안 L을 결정한다.

지수 시간 (Exponential time)

poly(n)이 n에서의 어떤 다항식이라고 할 때, 만약 T(n)이 2^poly(n)로 상한이 정해진다면, 이 알고리즘은 지수 시간을 갖는다고 말할 수 있다. 더 형식적으로, 만약 T(n)이 어떤 상수 k에 대해서 $O(2^{n{^{k}}})$ 를 갖는다면, 지수 시간을 갖는다. 결정적 튜링 머신에 대해 지수 시간 알고리즘인 문제들은 EXP로 알려져있는 복잡도 클래스를 만든다.

$EXP=\bigcup _{c\in \mathbb {N} }DTIME({2^{n{^{c}}}})$

가끔 지수 시간은 지수가 최대 n의 선형 함수일 때, T(n) = 2^O(n)을 갖는 알고리즘으로 사용되기도 하며, 복잡도 클래스 E를 표현한다.

$E=\bigcup _{c\in \mathbb {N} }{DTIME}(2^{cn})$

이중지수 시간 (Double exponential time)

poly(n)이 n에서의 어떤 다항식이라고 할 때, 만약 T(n)이 2^2poly(n)로 상한이 정해진다면, 이 알고리즘은 이중지수 시간을 갖는다고 말할 수 있다. 이러한 알고리즘들은 2-EXPTIME 복잡도 클래스에 속한다.

${\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)$

잘 알려진 이중지수 시간 알고리즘은 다음을 포함한다:

Presburger 연산을 위한 결정 과정
(최악의 경우에서) Grõbner basis 계산
닫힌 실수 영역에 대한 한정 기호 제거 (Quantifier elimination)는 최소 이중지수 시간이 걸린다.

같이 보기

각주

↑ Mehlhorn, Kurt; Naher, Stefan (1990). “Bounded ordered dictionaries in O(log log N) time and O(n) space”. 《Information Processing Letters》 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.

[1] Mehlhorn, Kurt; Naher, Stefan (1990). “Bounded ordered dictionaries in O(log log N) time and O(n) space”. 《Information Processing Letters》 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.

[1]