shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
그러나 검색 트리에서 위로 이동하는 경우는 드물며, 주로 순위 쿼리를 수행하는 데 사용된다: 주어진 접두사 합이 어떤 인덱스에 나타나는가? 이는 검색 트리를 아래로 이동하여 수행된다. 이동 중에 세 가지 변수가 유지된다: 현재 노드의 인덱스, 현재 노드를 루트로 하는 서브트리에서 찾는 순위, 그리고 찾는 순위가 서브트리에서 찾을 수 있는 것보다 클 경우 반환될 "폴백 인덱스"이다.
초기에는 현재 노드가 루트이고, 찾는 순위가 원래 쿼리이며, 폴백 인덱스는 순위가 트리에 없음을 나타내는 특별한 "오버플로" 값이다. (응용 프로그램에 따라 formula_67 또는 formula_5이 이 목적으로 사용될 수 있다.)
각 단계에서 현재 노드가 가상의 노드(인덱스가 formula_6보다 큼)이거나, 찾는 위치가 현재 노드의 끝의 왼쪽 또는 오른쪽인지 결정해야 한다. 찾는 순위가 현재 노드에 대한 펜윅 배열 값 formula_47보다 작으면 왼쪽 서브트리를 검색해야 한다. 크면 오른쪽 서브트리를 검색한다. 같으면 선택된 방향은 두 노드 사이에 정확히 있는 합계를 검색하는 방법을 처리하는 방법에 따라 달라진다.
이 세 가지 가능성은 현재 노드가 리프인지 아닌지에 따라 추가로 나뉜다:
펜윅 트리의 두 가지 주요 연산(쿼리 및 업데이트)에 대한 간단한 의사코드 구현은 다음과 같다:
function query(tree, index) is
sum := 0
while index &gt; 0 do
sum += tree[index]
index -= lsb(index)
return sum
function update(tree, index, value) is
while index &lt; size(tree) do
tree[index] += value
index += lsb(index)
함수 formula_71은 주어진 formula_6의 최하위 비트를 계산하거나, 동일하게 formula_6의 약수이기도 한 가장 큰 2의 거듭제곱을 계산한다. 예를 들어, formula_74는 이진 표현에서 보듯이: formula_75이다. 이 함수는 2의 보수 부정을 가정할 때 비트 AND 연산을 통해 코드에서 간단히 구현될 수 있다: codice_2.
펜윅 트리를 구성하는 한 가지 비효율적인 알고리즘은 트리를 널 값으로 초기화하고 각 인덱스를 개별적으로 업데이트하는 것이다. 이 해결책은 formula_76 시간에 작동하지만, formula_1 구성도 가능하다:
function construct(values) is
tree := values
for index from 1 to size(tree) do
parentIndex := index + lsb(index)
if parentIndex &amp;leq; size(tree) then
tree[parentIndex] += tree[index]
계산 복잡도 이론에서 다항 위계(Polynomial hierarchy), 다항 시간 위계는 NP 및 Co-NP 클래스를 일반화하는 위계적인 복잡도 종류이다. 위계의 각 클래스는 PSPACE 내에 포함된다. 이 위계는 신탁 기계 또는 교대 튜링 기계를 사용하여 정의할 수 있다. 이는 수리 논리학의 산술적 위계 및 해석적 위계에 대한 자원 제약적 대응물이다. 위계 내 클래스의 합집합은 PH로 표기된다.
위계 내의 클래스는 수량자 순서에 대한 제한이 있는 공식에 대해 정량화 부울 공식이 참인지 묻는 완전한 문제(다항 시간 환원과 관련하여)를 가진다. 위계에서 동일한 수준 또는 연속적인 수준의 클래스 간의 등식은 해당 수준으로 위계가 "붕괴"함을 의미한다는 것이 알려져 있다.
다항 위계의 클래스에 대한 여러 동등한 정의가 있다.
신탁 정의.
다항 위계의 신탁 정의를 위해 다음을 정의한다.
여기서 P는 다항 시간 내에 해결 가능한 결정 문제들의 집합이다. 그런 다음 i ≥ 0에 대해 다음을 정의한다.
여기서 formula_5는 클래스 A의 어떤 완전 문제에 대한 신탁에 의해 다항 시간에 해결 가능한 결정 문제들의 집합이다. 클래스 formula_6 및 formula_7는 유사하게 정의된다. 예를 들어, formula_8 이고 formula_9는 어떤 NP-완전 문제에 대한 오라클을 가진 결정적 튜링 기계로 다항 시간 안에 해결 가능한 문제들의 클래스이다.
정량화 부울 공식 정의.
다항 위계의 존재/전체 정의를 위해, 을 형식 언어(즉, 결정 문제, {0,1}*의 부분집합)라고 하고, 를 다항식이라고 하자. 그리고 다음을 정의한다.
여기서 formula_11는 두 이진 문자열 x와 w를 하나의 이진 문자열로 인코딩하는 표준 방법이다. 언어 L은 문자열의 순서쌍 집합을 나타내며, 첫 번째 문자열 x는 formula_12의 멤버이고 두 번째 문자열 w는 x가 formula_12의 멤버임을 증명하는 "짧은" (formula_14) 증거이다. 다시 말해, formula_15인 경우에만 formula_16를 만족하는 짧은 증거 w가 존재한다. 비슷하게, 다음을 정의한다.
드 모르간의 법칙이 성립한다: formula_18 및 formula_19, 여기서 Lc는 L의 여집합이다.
가 언어의 클래스라고 하자. 이러한 연산자를 언어의 전체 클래스에 적용하도록 다음 정의를 통해 확장한다.
다시 말해, 드 모르간의 법칙이 성립한다: formula_22 및 formula_23, 여기서 formula_24이다.
클래스 NP와 Co-NP는 formula_25, 그리고 formula_26로 정의할 수 있으며, 여기서 P는 모든 실행 가능하게 (다항 시간) 결정 가능한 언어의 클래스이다. 다항 위계는 다음과 같이 재귀적으로 정의할 수 있다.
formula_30 및 formula_31임을 주목한다.
이 정의는 다항 위계와 산술적 위계 사이의 밀접한 관계를 반영하며, 여기서 R과 RE는 각각 P와 NP에 비유되는 역할을 한다. 해석적 위계 또한 유사한 방식으로 정의되어 실수의 부분 집합 위계를 제공한다.
교대 튜링 기계 정의.
교대 튜링 기계는 비최종 상태가 존재 상태와 전체 상태로 분할된 비결정적 튜링 기계이다. 다음 경우에 현재 구성에서 결국 수락한다: 존재 상태에 있고 결국 수락하는 구성으로 전환할 수 있는 경우; 또는, 전체 상태에 있고 모든 전환이 결국 수락하는 구성으로 이어지는 경우; 또는, 수락 상태에 있는 경우.
formula_32를 다항 시간 내에 교대 튜링 기계에 의해 수락되는 언어의 클래스라고 정의한다. 이 기계는 초기 상태가 존재 상태이고 기계가 취할 수 있는 모든 경로가 존재 상태와 전체 상태 사이를 최대 k – 1번 교환한다. 유사하게, formula_33를 초기 상태가 전체 상태인 경우로 정의한다.
존재 상태와 전체 상태 사이의 최대 k – 1회 교환 요구 사항을 생략하고 교대 튜링 기계가 다항 시간에 실행되기만 요구하는 경우, 클래스 AP의 정의를 가지며, 이는 PSPACE와 같다.
다항 위계 내 클래스 간의 관계.
다항 위계의 모든 클래스의 합집합은 복잡도 클래스 PH이다.
정의는 다음과 같은 관계를 암시한다.
포함 관계가 참임이 알려진 산술 및 해석적 위계와 달리, 이러한 포함 관계 중 어느 것이 참인지에 대한 질문은 미해결 문제이지만, 모두 참이라고 널리 믿어진다. 만약 어떤 formula_37이거나, 어떤 formula_38이면, 위계는 k 수준으로 붕괴된다: 모든 formula_39에 대해 formula_40이다. 특히, 미해결 문제와 관련된 다음 함의가 있다.
NP = PH인 경우를 PH가 두 번째 수준으로 붕괴되었다고도 한다. P = NP인 경우는 PH가 P로 붕괴된 것에 해당한다.
첫 번째 수준으로의 붕괴 문제는 일반적으로 매우 어렵다고 생각된다. 대부분의 연구자들은 두 번째 수준으로의 붕괴조차 믿지 않는다.
다른 클래스와의 관계.
다항 위계는 지수 위계와 산술적 위계의 아날로그(훨씬 낮은 복잡도에서)이다.
PH는 PSPACE 내에 포함되어 있지만, 두 클래스가 같은지는 알려져 있지 않다. 이 문제의 유용한 재정식화는 PH = PSPACE인 경우에만 유한 구조에 대한 2차 논리가 관계에 대한 관계(즉, 2차 변수에 대한) 전이 폐포 연산자의 추가로 추가적인 능력을 얻지 못한다는 것이다.
다항 위계에 완전 문제가 있다면, 그것은 유한하게 많은 고유한 수준만을 가진다. PSPACE-완전 문제가 존재하므로, PSPACE = PH라면 다항 위계는 붕괴해야 한다. 왜냐하면 PSPACE-완전 문제는 어떤 k에 대한 formula_42-완전 문제가 될 것이기 때문이다.
다항 위계의 각 클래스는 formula_43-완전 문제(다항 시간 다대일 환원에 대한 완전 문제)를 포함한다. 또한, 다항 위계의 각 클래스는 formula_43-환원에 대해 닫혀 있다: 즉, 위계 내의 클래스 와 언어 formula_45에 대해, 만약 formula_46이면 formula_47이다. 이 두 가지 사실은 formula_48가 formula_49에 대한 완전 문제라면, formula_50이고 formula_51임을 의미한다. 예를 들어, formula_52이다. 다시 말해, 어떤 언어가 의 어떤 오라클을 기반으로 정의된다면, 그것이 에 대한 완전 문제를 기반으로 정의된다고 가정할 수 있다. 따라서 완전 문제는 그것이 완전한 클래스의 "대표" 역할을 한다.
양자 컴퓨터에 의해 다항 시간 안에 해결 가능한 문제들의 클래스인 BQP가 PH에 포함되지 않는다는 일부 증거가 있다. 그러나 PH가 BQP에 포함되지 않는다고도 믿어진다.=
복잡도 이론에서 PP 또는 PPT는 모든 인스턴스에 대해 오차 확률이 1/2 미만으로 다항 시간에 확률적 튜링 기계로 해결 가능한 결정 문제의 종류이다. 약어 PP는 확률적 다항 시간을 의미한다. 이 복잡도 종류는 길(Gill)이 1977년에 정의했다.
결정 문제가 PP에 속한다면, 확률적 결정을 내릴 수 있는 다항 시간 실행 알고리즘이 존재하며, 이 알고리즘은 1/2보다 높은 확률로 올바른 답을 반환한다. 좀 더 실용적인 용어로 설명하면, 이 종류는 무작위 다항 시간 알고리즘을 충분한(그러나 유한한) 횟수만큼 실행함으로써 어떤 고정된 정확도까지 해결할 수 있는 문제들의 종류이다.
다항적으로 제한된 확률적 튜링 기계는 확률적 다항 시간 기계를 나타내는 PPT로 특징지어진다. 이 튜링 기계의 특징은 유한한 오차 확률을 요구하지 않는다. 따라서 PP는 오차 확률이 1/2 미만인 PPT 기계로 해결할 수 있는 모든 문제를 포함하는 복잡도 종류이다.
PP의 대안적인 특징은 다항 시간 내에 비결정론적 튜링 기계로 해결할 수 있는 문제들의 집합으로, 수용 조건은 계산 경로의 과반수(절반 이상)가 수용하는 것이다. 이 때문에 일부 저자들은 대체 이름으로 Majority-P를 제안했다.
언어 L이 PP에 속하는 경우는 다음과 같은 확률적 튜링 기계 M이 존재하는 경우에 한한다.
다른 방법으로, PP는 결정론적 튜링 기계만을 사용하여 정의할 수 있다. 언어 L이 PP에 속하는 경우는 다음과 같은 다항식 p와 결정론적 튜링 기계 M이 존재하는 경우에 한한다.
이 정의에서 문자열 y는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 결과에 해당한다.
두 정의 모두에서, "미만"은 "이하"로 변경될 수 있고(아래 참조), 임계값 1/2은 (0,1) 범위의 어떤 고정된 유리수로 대체될 수 있으며, 이는 종류를 변경하지 않는다.
PP 대 BPP.
BPP는 PP의 부분집합이다. 이는 효율적인 확률적 알고리즘이 존재하는 부분집합으로 볼 수 있다. 차이점은 허용되는 오차 확률에 있다. BPP에서는 알고리즘이 2/3 또는 1000분의 501과 같은 1/2보다 큰 고정 상수 c를 초과하는 확률로 올바른 답(예 또는 아니요)을 제공해야 한다. 이 경우, 체르노프 경계를 사용하여 알고리즘을 여러 번 실행하고 다수결을 통해 1 미만의 원하는 정확도 확률을 달성할 수 있다. 이 반복 횟수는 c가 1/2에 가까워질수록 증가하지만, 입력 크기 n에는 의존하지 않는다.
더 일반적으로, c가 입력 크기 formula_1에 다항적으로, 즉 formula_2와 같이 의존할 수 있다면, 알고리즘을 formula_3번 재실행하고 다수결을 취할 수 있다. 호프딩 부등식에 의해, 이는 우리에게 BPP 알고리즘을 제공한다.
중요한 점은 이 상수 c가 입력에 의존하도록 허용되지 않는다는 것이다. 반면에, PP 알고리즘은 다음과 같은 작업을 수행할 수 있다.
이 두 확률은 지수적으로 매우 가깝기 때문에, 다항 시간 동안 실행하더라도 우리가 YES 인스턴스에서 작동하고 있는지 NO 인스턴스에서 작동하고 있는지 구분하기가 매우 어렵다. 다수결과 체르노프 경계를 사용하여 고정된 원하는 확률 수준을 달성하려고 시도하면 n에 대해 지수적인 반복 횟수가 필요하다.
다른 복잡도 종류와 PP 비교.
PP는 BPP를 포함하는데, BPP의 정의에 기술된 확률적 알고리즘이 PP의 정의에 있는 알고리즘들의 부분집합을 형성하기 때문이다.
PP는 또한 NP를 포함한다. 이를 증명하기 위해, NP-완전인 충족 가능성 문제가 PP에 속함을 보인다. 공식 F(x1, x2, ..., xn)가 주어졌을 때, 할당 x1, x2, ..., xn을 균일하게 무작위로 선택하는 확률적 알고리즘을 고려해보자. 그런 다음, 이 알고리즘은 할당이 공식 F를 참으로 만드는지 확인한다. 만약 참이라면 YES를 출력한다. 그렇지 않으면 1/2 - 1/2n + 1의 확률로 YES를 출력하고 1/2 + 1/2n + 1의 확률로 NO를 출력한다.
만약 공식이 충족 불가능하다면, 알고리즘은 항상 1/2 - 1/2n + 1 &lt; 1/2의 확률로 YES를 출력한다. 만약 충족 가능한 할당이 존재한다면, 알고리즘은 적어도 다음 확률로 YES를 출력한다.
(불충족 할당을 선택한 경우 정확히 1/2이고, 충족 할당을 선택한 경우 1이며, 평균적으로 1/2보다 큰 어떤 숫자). 따라서 이 알고리즘은 충족 가능성을 PP에 포함시킨다. SAT는 NP-완전이므로, 우리는 어떤 결정론적 다항 시간 다대일 환산도 PP 알고리즘에 접두어로 붙일 수 있으므로, NP는 PP에 포함된다. PP는 여집합에 대해 닫혀 있으므로, co-NP도 포함한다.
또한 PP는 앞의 두 포함 관계를 포함하는 MA를 포함한다.
PP는 효율적인 다항 시간 양자 컴퓨터로 해결 가능한 결정 문제의 종류인 BQP도 포함한다. 사실 BQP는 PP에 대해 low인데, 이는 PP 기계가 BQP 문제를 즉시 해결할 수 있는 능력을 통해 어떤 이점도 얻지 못한다는 것을 의미한다. 후선택이 있는 양자 컴퓨터의 다항 시간 클래스인 PostBQP는 PP와 동일하다. (아래 #PostBQP 참조).
더 나아가, PP는 MA와 BQP의 포함을 포함하는 QMA를 포함한다.
PP 오라클을 가진 다항 시간 튜링 기계(PPP)는 전체 다항 계층인 PH의 모든 문제를 해결할 수 있다. 이 결과는 1989년 토다 세이노스케에 의해 증명되었으며, 토다 정리로 알려져 있다. 이는 PP의 문제를 해결하는 것이 얼마나 어려운지에 대한 증거이다. #P 클래스는 P#P = PPP 이고 따라서 P#P도 PH를 포함하므로, 어떤 의미에서는 그만큼 어렵다.
PP는 상수 깊이, 무제한 팬인 불 회로와 균일한(다항 시간 알고리즘으로 생성되는) 다수결 게이트를 가진 종류인 균일 TC0를 엄격하게 포함한다.
PP는 PSPACE에 포함된다. 이는 아래에 정의된 MAJSAT에 대한 다항 공간 알고리즘을 제시함으로써 쉽게 보일 수 있다. 단순히 모든 할당을 시도하고 만족하는 것들의 수를 세면 된다.
PP는 칸난 정리에 의해 어떤 k에 대해서도 SIZE(nk)에 포함되지 않는다.
완전 문제 및 기타 속성.
BPP와 달리, PP는 의미론적 종류가 아닌 구문론적 종류이다. 어떤 다항 시간 확률적 기계도 PP에 속하는 어떤 언어를 인식한다. 반대로, 다항 시간 확률적 기계의 설명이 주어졌을 때, 그것이 BPP에 속하는 언어를 인식하는지 여부를 결정하는 것은 일반적으로 결정 불가능하다.
PP에는 자연스러운 완전 문제들이 있는데, 예를 들어 MAJSAT이 있다. MAJSAT은 불리언 공식 F가 주어졌을 때, 모든 할당 x1, x2, ..., xn 중 절반 이상이 F를 참으로 만드는 경우 YES를, 그렇지 않은 경우 NO를 답해야 하는 결정 문제이다.
PP가 여집합에 대해 닫혀 있다는 증명.
L을 PP에 속하는 언어라고 하자. formula_5를 L의 여집합이라고 하자. PP의 정의에 의해 다음과 같은 속성을 가진 다항 시간 확률적 알고리즘 A가 존재한다.
우리는 일반성을 잃지 않고, 후자의 부등식이 항상 엄격하다고 주장한다. 정리는 이 주장으로부터 추론될 수 있다: A가 거부하는 경우 formula_7는 수용하고 그 반대인 기계인 formula_7를 정의하자. 그러면
이는 formula_5가 PP에 속함을 의미한다.
이제 일반성을 잃지 않고 가정을 정당화한다. formula_11를 입력 x에 대한 A의 실행 시간의 다항 상한이라고 하자. 따라서 A는 실행 중 최대 formula_11개의 무작위 동전 던지기를 수행한다. 특히 수용 확률은 formula_13의 정수배이며 다음과 같다.
기계 A′를 다음과 같이 정의한다. 입력 x에 대해 A′는 A를 서브루틴으로 실행하고, A가 거부하면 거부한다. 그렇지 않고 A가 수용하면 A′는 formula_15개의 동전을 던지고, 모두 앞면이면 거부하고, 그렇지 않으면 수용한다. 그러면
이는 가정을 정당화하고(A′는 여전히 다항 시간 확률적 알고리즘이므로) 증명을 완료한다.
데이비드 루소는 1985년 박사 학위 논문에서 PP가 대칭차에 대해 닫혀 있음을 증명했다. PP가 합집합과 교집합에 대해 닫혀 있는지 여부는 14년 동안 열린 문제였다. 이는 비겔(Beigel), 라인골드(Reingold), 스필먼(Spielman)에 의해 긍정적으로 해결되었다. 리(Li)와 애런슨(Aaronson)이 나중에 다른 증명을 제시했다(아래 #PostBQP 참조).
다른 동등한 복잡도 종류.
PostBQP.
양자 복잡도 종류 BQP는 양자 튜링 기계에서 다항 시간에 해결할 수 있는 문제의 종류이다. 후선택을 추가함으로써 더 큰 종류인 PostBQP를 얻을 수 있다. 비공식적으로, 후선택은 컴퓨터에 다음과 같은 능력을 부여한다: 어떤 사건(예: 특정 상태의 큐비트 측정)이 0이 아닌 확률을 가질 때마다, 그것이 발생했다고 가정할 수 있다. 스콧 애런슨은 2004년에 PostBQP가 PP와 동일하다는 것을 보였다. 이 PP의 재정의는 PP가 교집합(따라서 합집합)에 대해 닫혀 있다는 것, BQP가 PP에 대해 low라는 것, 그리고 QMA가 PP에 포함된다는 것과 같은 특정 결과를 더 쉽게 보여준다.
PQP.
PP는 또한 BQP의 무제한 오차 아날로그로 알려진 또 다른 양자 복잡도 종류인 PQP와 동일하다. 이는 모든 인스턴스에 대해 오차 확률이 1/2 미만으로, 다항 시간 내에 양자 컴퓨터로 해결할 수 있는 결정 문제의 종류를 나타낸다. PQP 계산에 사용되는 모든 진폭이 대수적 수에서 파생된 경우에도 PQP는 PP와 일치한다.
계산 복잡도 이론에서 복잡도 종류 NEXPTIME (가끔 NEXP로 불림)은 formula_1 시간 내에 비결정론적 튜링 기계로 풀 수 있는 결정 문제들의 집합이다.
NTIME 관점에서,
다른 방식으로, NEXPTIME은 검증자로 결정론적 튜링 기계를 사용하여 정의할 수 있다. 언어 L이 NEXPTIME에 속하는 것은 다항식 p와 q, 그리고 결정론적 튜링 기계 M이 존재하여 다음을 만족할 때이다.
우리는 다음을 알고 있다.
또한, 시간 위계 정리에 의해 다음을 알 수 있다.
만약 라면, (패딩 논증); 더 정확히는, E ≠ NE일 때에만 P에 속하지 않는 희소 언어가 NP에 존재한다.
다른 특성화.
서술 복잡도에서 NEXPTIME에서 인식될 수 있는 자연수의 집합은 정확히 어떤 논리 문장의 문장의 스펙트럼, 즉 유한 모델들의 크기 집합을 형성하는 것들이다.
NEXPTIME은 종종 대화형 증명 시스템의 맥락에서 발생하며, 여기에는 두 가지 주요 특징이 있다. 첫 번째는 MIP 증명 시스템인데, 여기에는 무한한 능력을 가진 두 명의 증명자(서로 통신하지 않음)가 무작위 다항 시간 검증자와 통신한다. 문자열이 언어에 있으면 높은 확률로 검증자를 확신시켜야 한다. 문자열이 언어에 없으면 낮은 확률을 제외하고는 검증자가 문자열을 수락하도록 공동으로 속일 수 없어야 한다. MIP 증명 시스템이 NEXPTIME의 모든 문제를 해결할 수 있다는 사실은 증명자가 한 명만 있을 때 PSPACE의 모든 문제를 인식할 수 있다는 점을 고려하면 상당히 인상적이다. 검증자가 두 증명자를 "교차 심문"하는 능력은 큰 힘을 부여한다. 자세한 내용은 대화형 증명 시스템#MIP을 참조하라.
NEXPTIME을 특징짓는 또 다른 대화형 증명 시스템은 특정 종류의 확률적으로 검사 가능한 증명이다. NP는 무한한 능력을 가진 증명자가 문자열이 언어에 있음을 증명하는 증거를 제시하고, 결정론적 다항 시간 기계가 그것이 유효한 증거임을 검증하는 문제들의 종류로 볼 수 있다. 이 설정에 두 가지 변화를 준다.
이 두 가지 확장은 함께 증명 시스템의 능력을 크게 확장하여 NEXPTIME의 모든 언어를 인식할 수 있게 한다. 이 클래스는 PCP(poly, poly)라고 불린다. 더 나아가, 이 특성화에서 검증자는 단지 상수 비트만 읽도록 제한될 수 있다. 즉, NEXPTIME = PCP(poly, 1)이다. 자세한 내용은 확률적으로 검사 가능한 증명을 참조하라.
NEXPTIME-완전.
결정 문제는 NEXPTIME에 속하고, NEXPTIME의 모든 문제는 그것에 대한 다항 시간 다대일 환산이 있으면 NEXPTIME-완전이다. 다시 말해, 한 인스턴스를 같은 답을 가진 다른 인스턴스로 변환하는 다항 시간 알고리즘이 존재한다. NEXPTIME-완전 문제는 NEXPTIME에서 가장 어려운 문제로 생각할 수 있다. 우리는 NEXPTIME-완전 문제가 NP에 속하지 않는다는 것을 알고 있다. 이 문제들은 시간 위계 정리에 의해 다항 시간 내에 검증될 수 없다는 것이 증명되었다.
NEXPTIME-완전 문제의 예.
간결한 문제.
NEXPTIME-완전 문제의 중요한 집합은 간결한 회로와 관련이 있다. 간결한 회로는 그래프를 기하급수적으로 적은 공간으로 기술하는 데 사용되는 간단한 기계이다. 이들은 두 개의 정점 번호를 입력으로 받아 그들 사이에 에지가 있는지 여부를 출력한다. 인접행렬과 같은 자연스러운 표현으로 그래프 문제를 해결하는 것이 NP-완전이라면, 간결한 회로 표현으로 같은 문제를 해결하는 것은 NEXPTIME-완전이다. 왜냐하면 입력이 기하급수적으로 작기 때문이다 (NP-완전성 환산이 "투영"에 의해 달성된다는 약간의 조건 하에). 한 가지 간단한 예로, 그렇게 인코딩된 그래프의 해밀턴 경로를 찾는 것은 NEXPTIME-완전이다.
두 변수를 가진 1차 논리의 만족성 문제는 NEXPTIME-완전이다. 계수와 두 변수를 가진 1차 논리의 만족성 문제는 NEXPTIME-완전이다.
의존성 한정 이진 공식(DQBF, QBF의 불완전 정보 버전)에서 공식이 참인지 결정하는 것은 NEXPTIME-완전이다. 팀을 가진 제약 논리의 불완전 정보도 NEXPTIME-완전이다.
계산 복잡도 이론에서 DTIME 또는 TIME은 결정론적 튜링 기계의 연산 시간 연산 자원이다. 이는 "일반적인" 물리 컴퓨터가 특정 알고리즘을 사용하여 특정 계산 문제를 해결하는 데 걸리는 시간(또는 계산 단계 수)을 나타낸다. 이는 중요한 실제 자원(컴퓨터가 문제를 해결하는 데 걸리는 시간)과 매우 밀접하게 관련되어 있기 때문에 가장 잘 연구된 복잡성 자원 중 하나이다.
DTIME 자원은 특정 양의 연산 시간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 입력 크기 n의 문제가 으로 해결될 수 있다면, 복잡도 종류 (또는 )를 가진다. 사용되는 메모리 공간의 양에는 제한이 없지만, 다른 복잡성 자원(예: 교대)에는 제한이 있을 수 있다.
DTIME의 복잡도 종류.
많은 중요한 복잡도 종류는 DTIME으로 정의되며, 특정 양의 결정론적 시간으로 해결할 수 있는 모든 문제를 포함한다. 모든 적절한 복잡도 함수를 사용하여 복잡도 종류를 정의할 수 있지만, 특정 종류만 연구하는 데 유용하다. 일반적으로, 우리는 복잡도 종류가 계산 모델의 변화에 대해 견고하고, 서브루틴의 구성에 대해 닫혀 있기를 원한다.
DTIME은 시간 계층 정리를 만족하며, 이는 점근적으로 더 많은 양의 시간이 항상 엄격하게 더 큰 문제 집합을 생성한다는 것을 의미한다.
잘 알려진 복잡도 종류 P는 다항식 시간 DTIME으로 해결할 수 있는 모든 문제를 포함한다. 이는 공식적으로 다음과 같이 정의할 수 있다.
P는 선형 시간 문제 formula_2를 포함하는 가장 작은 견고한 종류이다 (AMS 2004, Lecture 2.2, pg. 20). P는 "계산적으로 실현 가능한" 것으로 간주되는 가장 큰 복잡도 종류 중 하나이다.
결정론적 시간을 사용하는 훨씬 더 큰 종류는 EXPTIME이며, 이는 지수 시간에 결정론적 기계로 해결할 수 있는 모든 문제를 포함한다. 공식적으로, 우리는 다음을 얻는다.
더 큰 복잡도 종류도 비슷하게 정의할 수 있다. 시간 계층 정리 때문에, 이들 종류는 엄격한 계층 구조를 형성한다; 우리는 formula_4임을 알고 있으며, 그 이상도 마찬가지다.
기계 모델.
P와 같은 견고한 종류의 경우, DTIME을 정의하는 데 사용되는 정확한 기계 모델은 자원의 성능에 영향을 주지 않으면서 변경될 수 있다. 계산 복잡성 문헌은 특히 매우 작은 시간 종류를 논의할 때 다중 테이프 튜링 기계를 기반으로 DTIME을 정의하는 경우가 많다. 다중 테이프 결정론적 튜링 기계는 단일 테이프 기계보다 2차 시간 가속을 제공할 수 없다.
튜링 기계의 선형 속도 향상 정리 때문에, 시간 경계의 곱셈 상수는 DTIME 종류의 범위에 영향을 주지 않는다; 유한 상태 제어의 상태 수를 늘리고 테이프 알파벳의 크기를 늘림으로써 항상 상수 곱셈 속도 향상을 얻을 수 있다. 파파디미트리우의 진술에서, 언어 에 대해,
결정론적 튜링 기계 이외의 모델을 사용하면 DTIME의 다양한 일반화 및 제한이 있다. 예를 들어, 비결정론적 튜링 기계를 사용하면 NTIME 자원을 얻는다. DTIME과 다른 계산 자원의 표현력 간의 관계는 거의 이해되지 않고 있다. 몇 안 되는 알려진 결과 중 하나는 다음과 같다.
다중 테이프 기계의 경우. 이것은 Santhanam에 의해 다음으로 확장되었다. 여기서 formula_10은 반복 로그이다.
교대 튜링 기계를 사용하면 ATIME 자원을 얻는다.
계산 복잡도 이론에서, 복잡도 종류 NTIME("f"("n"))는 시간 O(f(n)) 안에 실행되는 비결정론적 튜링 기계에 의해 해결될 수 있는 결정 문제들의 집합이다. 여기서 O는 점근 표기법이고, f는 어떤 함수이며, n은 입력의 크기(문제를 결정해야 하는 대상)이다.
이것은 크기 n의 주어진 입력에 대해 시간 O(f(n)) 안에 실행될 (즉, n이 어떤 값보다 클 때 f(n)의 상수배 내에서 실행될) 비결정론적 기계가 존재하며, 결정 문제의 답이 해당 입력에 대해 "아니오"인 경우 항상 입력을 "거부"하고, 답이 "예"인 경우 기계는 적어도 하나의 계산 경로에 대해 해당 입력을 "수락"한다는 것을 의미한다. 동등하게, O(f(n)) 시간 안에 실행되고 입력에 대한 O(f(n)) 길이의 인증서를 확인할 수 있는 결정론적 튜링 기계 M이 존재한다. 입력이 "예" 사례인 경우 적어도 하나의 인증서가 수락되고, 입력이 "아니오" 사례인 경우 어떤 인증서도 기계를 수락하게 만들 수 없다.
기계에 사용 가능한 공간은 제한되지 않지만 O(f(n))을 초과할 수 없다. 왜냐하면 사용 가능한 시간이 테이프의 접근 가능량을 제한하기 때문이다.
잘 알려진 복잡도 종류인 NP는 NTIME을 사용하여 다음과 같이 정의할 수 있다:
마찬가지로, 종류 NEXP는 NTIME을 사용하여 다음과 같이 정의된다:
비결정론적 시간 위계 정리는 비결정론적 기계가 점근적으로 더 많은 시간에 더 많은 문제를 해결할 수 있다고 말한다.
NTIME은 다음 방식으로 DSPACE와도 관련이 있다. 모든 시간 구성 가능 함수 t(n)에 대해 다음이 성립한다:
NTIME의 일반화는 교대 튜링 기계로 정의되는 ATIME이다. 다음이 성립하는 것으로 밝혀졌다:
계산 복잡도 이론에서 비결정적 공간 또는 NSPACE는 비결정적 튜링 기계의 메모리 공간을 나타내는 연산 자원이다. 이것은 DSPACE의 비결정적 대응물이다.
NSPACE 측정은 비결정적 튜링 기계로 해답을 결정할 수 있는 복잡도 종류를 정의하는 데 사용된다. 복잡도 종류 NSPACE(f(n))는 비결정적 튜링 기계 M이 O(f(n)) 공간을 사용하여 풀 수 있는 결정 문제의 집합이며, 여기서 n은 입력의 길이이다.
몇 가지 중요한 복잡도 종류는 NSPACE로 정의할 수 있다. 다음이 포함된다.
이머만–셀렙체니 정리는 모든 함수 에 대해 NSPACE(s(n))가 여집합에 대해 닫혀 있음을 명시한다.
더 나아가 일반화된 것은 교대 튜링 기계로 정의되는 ASPACE이다.
DSPACE.
NSPACE는 결정적 튜링 기계의 메모리 공간 종류인 DSPACE의 비결정적 대응물이다. 정의에 따라, 그리고 새비치 정리에 따라, 우리는 다음을 가진다.
NSPACE는 다음 정리를 통해 결정적 튜링 기계의 시간 복잡도를 결정하는 데에도 사용될 수 있다.
언어 L이 비결정적 TM에 의해 공간 S(n) (여기서 S(n) ≥ log n)에서 결정된다면, L이 결정적 TM에 의해 시간 O(CS(n))에서 결정되도록 하는 상수 C가 존재한다.
DSPACE 측면에서 공간 복잡도를 측정하는 것은 주어진 알고리즘으로 주어진 계산 문제를 해결하는 데 실제 컴퓨터가 필요로 하는 총 메모리 양을 나타내므로 유용하다. 그 이유는 DSPACE가 실제 컴퓨터를 나타낼 수 있는 결정적 튜링 기계가 사용하는 공간 복잡도를 설명하기 때문이다. 반면에 NSPACE는 실제 컴퓨터를 나타내려고 할 때 유용하지 않은 비결정적 튜링 기계의 공간 복잡도를 설명한다. 이러한 이유로 NSPACE는 실제 응용 프로그램에서의 유용성이 제한적이다.
계산 복잡도 이론에서 대화형 증명 시스템(Interactive proof system)은 증명자와 검증자라는 두 주체 간의 메시지 교환으로 컴퓨테이션을 모델링하는 추상 기계이다. 이들은 주어진 문자열이 형식 언어에 속하는지 여부를 확인하기 위해 메시지를 교환한다. 증명자는 무제한의 계산 자원을 가지고 있지만 신뢰할 수 없는 반면, 검증자는 제한된 계산 능력을 가지고 있지만 항상 정직하다고 가정한다. 검증자가 문제에 대한 답을 얻고 그것이 정확하다고 "확신"할 때까지 검증자와 증명자 사이에 메시지가 전송된다.
모든 대화형 증명 시스템에는 두 가지 요구 사항이 있다.
시스템의 특정 특성과 그에 따라 인식할 수 있는 언어의 복잡도 종류는 검증자에 부과되는 제약 조건과 부여되는 능력에 따라 달라진다. 예를 들어, 대부분의 대화형 증명 시스템은 검증자의 임의 선택 능력에 결정적으로 의존한다. 또한 교환되는 메시지의 특성(개수 및 내용)에도 의존한다. 대화형 증명 시스템은 하나의 기계만을 사용하여 정의된 전통적인 복잡도 종류에 중요한 영향을 미치는 것으로 밝혀졌다. 대화형 증명 시스템을 설명하는 주요 복잡도 종류는 AM 및 IP이다.
모든 대화형 증명 시스템은 문자열 formula_1의 형식 언어를 정의한다. 증명 시스템의 건전성은 증명자가 작은 확률을 제외하고는 잘못된 명제 formula_2에 대해 검증자를 승인하게 할 수 없다는 속성을 나타낸다. 이 확률의 상한은 증명 시스템의 건전성 오류라고 한다. 더 공식적으로는, 모든 증명자 formula_3와 모든 formula_2에 대해 다음이 성립한다.
건전성 오류가 검증자의 잠재적 실행 시간의 다항식 분수(즉, formula_7)로 제한되는 한, 검증자의 실행 시간에 비해 건전성 오류가 미미한 함수가 될 때까지 건전성을 증폭시키는 것은 항상 가능하다. 이는 증명을 반복하고 모든 증명이 검증될 때만 수용함으로써 달성된다. formula_8번 반복 후, 건전성 오류 formula_9는 formula_10로 감소할 것이다.
대화형 증명의 종류.
NP 복잡도 종류는 매우 간단한 증명 시스템으로 볼 수 있다. 이 시스템에서 검증자는 결정적, 다항 시간 기계(P 기계)이다. 프로토콜은 다음과 같다.
유효한 증명 인증서가 존재하는 경우, 증명자는 항상 해당 인증서를 제공하여 검증자를 승인하게 할 수 있다. 그러나 유효한 증명 인증서가 없는 경우, 입력은 해당 언어에 없으며, 아무리 악의적인 증명자라도 검증자를 달리 설득할 수 없다. 왜냐하면 어떤 증명 인증서도 거부될 것이기 때문이다.
아서-멀린 및 멀린-아서 프로토콜.
NP가 상호작용을 사용하는 것으로 볼 수 있지만, 1985년이 되어서야 두 독립적인 연구 그룹에 의해 (복잡도 이론의 맥락에서) 상호작용을 통한 컴퓨테이션 개념이 고안되었다. 라슬로 바바이의 "Trading group theory for randomness"가 발표된 한 접근 방식은 아서-멀린(AM) 클래스 계층을 정의했다. 이 발표에서 아서(검증자)는 확률적, 다항 시간 기계인 반면, 멀린(증명자)은 무제한 자원을 가지고 있다.
특히 MA 클래스는 위에서 언급한 NP 상호작용의 간단한 일반화이며, 검증자는 결정론적 대신 확률적이다. 또한, 검증자가 항상 유효한 인증서를 수락하고 유효하지 않은 인증서를 거부하도록 요구하는 대신, 더 관대하다.
이 기계는 일반적인 NP 상호작용 프로토콜보다 잠재적으로 더 강력하며, 인증서는 검증하기에 덜 실용적이지 않다. 왜냐하면 BPP 알고리즘은 실용적인 컴퓨테이션을 추상화하는 것으로 간주되기 때문이다(BPP 참조).
공개 코인 프로토콜 대 비공개 코인 프로토콜.
공개 코인 프로토콜에서는 검증자가 수행한 임의 선택이 공개된다. 비공개 코인 프로토콜에서는 비공개로 유지된다.
바바이가 MA에 대한 자신의 증명 시스템을 정의한 같은 회의에서, 샤피 골드와서, 실비오 미칼리 및 찰스 래코프는 대화형 증명 시스템 IP[f(n)]을 정의하는 논문을 발표했다. 이것은 MA 프로토콜과 동일한 기계를 사용하지만, 입력 크기 n에 대해 f(n) 라운드가 허용된다. 각 라운드에서 검증자는 계산을 수행하고 증명자에게 메시지를 전달하며, 증명자는 계산을 수행하고 검증자에게 정보를 다시 전달한다. 마지막에 검증자는 결정을 내려야 한다. 예를 들어, IP[3] 프로토콜에서 시퀀스는 VPVPVPV이며, V는 검증자 턴이고 P는 증명자 턴이다.
아서-멀린 프로토콜에서 바바이는 f(n) 라운드를 허용하는 유사한 클래스 AM[f(n)]을 정의했지만, 그는 기계에 한 가지 추가 조건을 부여했다. 즉, 검증자는 계산에 사용하는 모든 임의 비트를 증명자에게 보여주어야 한다. 그 결과, 증명자가 사용한 임의 비트를 알면 증명자가 검증자가 하는 모든 것을 시뮬레이션할 수 있을 만큼 강력하기 때문에 검증자는 증명자로부터 아무것도 "숨길" 수 없다. 이것을 공개 코인 프로토콜이라고 하는데, 임의 비트("코인 던지기")가 두 기계 모두에게 보이기 때문이다. IP 접근 방식은 대조적으로 비공개 코인 프로토콜이라고 한다.
공개 코인의 본질적인 문제는 증명자가 언어에 없는 문자열을 검증자가 수락하도록 악의적으로 설득하려 할 때, 검증자가 내부 상태를 숨길 수 있다면 증명자의 계획을 좌절시킬 수 있을 것처럼 보인다는 것이다. 이것이 IP 증명 시스템을 정의하는 주요 동기였다.
1986년, 골드와서와 시프서는 아마도 놀랍게도, 검증자가 코인 던지기를 증명자로부터 숨기는 능력이 두 라운드만 더 추가된 아서-멀린 공개 코인 프로토콜이 모든 동일한 언어를 인식할 수 있다는 점에서 결국 거의 도움이 되지 않는다는 것을 보여주었다. 그 결과 공개 코인 프로토콜과 비공개 코인 프로토콜은 거의 동등하다. 사실, 바바이가 1988년에 보여주듯이, 모든 상수 k에 대해 AM[k] = AM이므로, IP[k]는 AM에 비해 이점이 없다.
이러한 클래스의 위력을 보여주기 위해, 하나의 그래프의 정점을 재배열하여 다른 그래프와 동일하게 만들 수 있는지 여부를 결정하는 문제인 그래프 동형 문제를 고려해보자. 이 문제는 NP에 속하는데, 증명 인증서가 그래프를 동일하게 만드는 순열이기 때문이다. 그래프 동형 문제의 여집합, 즉 NP에 속하는 것으로 알려지지 않은 co-NP 문제는 AM 알고리즘을 가지고 있으며, 이를 이해하는 가장 좋은 방법은 비공개 코인 알고리즘을 통하는 것이다.
비공개 코인은 유용하지 않을 수 있지만, 더 많은 라운드 상호 작용은 유용하다. 확률적 검증 기계와 전능한 증명자가 다항식 개수의 라운드 동안 상호 작용하도록 허용하면, IP라고 불리는 문제 클래스를 얻는다.
1992년, 아디 샤미르는 복잡도 이론의 핵심 결과 중 하나에서 IP가 다항 공간에서 일반적인 결정론적 튜링 기계로 풀 수 있는 문제 클래스인 PSPACE와 같음을 밝혀냈다.
QIP.
시스템의 요소가 양자 컴퓨팅을 사용할 수 있도록 허용하면, 해당 시스템은 양자 대화형 증명 시스템이라고 불리며, 해당 복잡도 종류는 QIP라고 불린다. 일련의 결과들은 2010년 QIP = PSPACE라는 획기적인 발견으로 이어졌다.
영지식.
대화형 증명 시스템은 NP에 속하지 않는다고 여겨지는 문제들을 해결할 수 있을 뿐만 아니라, 일방향함수의 존재에 대한 가정 하에, 증명자는 검증자에게 해에 대한 정보를 전혀 주지 않고도 해를 확신시킬 수 있다. 이는 검증자가 전체 해를 신뢰할 수 없을 때 중요하다. 처음에는 검증자가 인증서를 보지 못했는데도 해가 있다고 확신할 수 있다는 것이 불가능해 보이지만, 영지식 증명이라고 알려진 이러한 증명은 실제로 NP의 모든 문제에 대해 존재한다고 여겨지며 암호학에서 가치가 있다. 영지식 증명은 골드와서, 미칼리, 래코프가 IP에 관한 1985년 원본 논문에서 특정 수론 언어에 대해 처음 언급했다. 그러나 그들의 위력은 오데드 골드라이히, 실비오 미칼리, 아비 위그더슨에 의해 NP 전체에 대해 시연되었고, 이는 러셀 임파글리아초와 모티 융에 의해 IP 전체로 처음 확장되었다.
MIP.
IP 설계자들의 한 가지 목표는 가능한 가장 강력한 대화형 증명 시스템을 만드는 것이었으며, 처음에는 검증자를 더 강력하게 만들지 않고는(그렇게 하면 비실용적이게 됨) 더 강력하게 만들 수 없을 것처럼 보였다. 골드와서 등은 1988년 "Multi prover interactive proofs: How to remove intractability assumptions"에서 이를 극복했다. 이 논문은 두 명의 독립적인 증명자가 있는 MIP라는 IP 변형을 정의한다. 두 증명자는 검증자가 메시지를 보내기 시작한 후에는 통신할 수 없다. 범인과 그의 공범이 따로 심문받을 때 거짓말을 하는지 알아내기 더 쉬운 것처럼, 다른 증명자와 다시 확인할 수 있다면 악의적인 증명자가 검증자를 언어에 없는 문자열을 수락하도록 속이려 하는 것을 감지하는 것이 훨씬 쉽다.
실제로, 이것은 매우 유용하여 바바이, 포트노우, 룬드는 MIP가 비결정론적 기계가 지수 시간 내에 해결할 수 있는 모든 문제의 클래스인 NEXPTIME과 같다는 것을 보여줄 수 있었다. 이는 매우 큰 클래스이다. NEXPTIME은 PSPACE를 포함하며, PSPACE를 엄격하게 포함하는 것으로 여겨진다. 두 명 이상의 상수를 추가해도 더 많은 언어를 인식할 수 있게 되지는 않는다. 이 결과는 이 정리의 "축소판"으로 볼 수 있는 유명한 PCP 정리의 길을 열었다.
MIP는 또한 IP가 가정해야 하는 일방향 함수 가정 없이도 NP의 모든 언어에 대한 영지식 증명을 설명할 수 있는 유용한 속성을 가지고 있다. 이것은 증명 가능한 깨지지 않는 암호화 알고리즘 설계에 영향을 미친다. 더욱이, MIP 프로토콜은 IP의 모든 언어를 상수 라운드 내에서 인식할 수 있으며, 세 번째 증명자가 추가되면 상수 라운드 내에서 NEXPTIME의 모든 언어를 인식할 수 있어 IP보다 그 위력을 다시 보여준다.
어떤 상수 k에 대해서도 k명의 증명자와 다항식 개수의 라운드를 가진 MIP 시스템이 단 두 명의 증명자와 상수 개수의 라운드를 가진 동등한 시스템으로 변환될 수 있다는 것이 알려져 있다.
PCP.
IP의 설계자들이 바바이의 대화형 증명 시스템의 일반화를 고려한 반면, 다른 이들은 제약을 고려했다. 매우 유용한 대화형 증명 시스템은 PCP(f(n), g(n))이며, 이는 아서가 f(n)개의 임의 비트만 사용하고 멀린이 보낸 증명 인증서의 g(n)개의 비트만 검사할 수 있는 (본질적으로 임의 접근을 사용하는) MA의 제약이다.
다양한 PCP 클래스에 대한 여러 가지 쉽게 증명할 수 있는 결과들이 있다. 랜덤성이 없지만 인증서에 접근할 수 있는 다항 시간 기계의 클래스인 는 단순히 NP이다. 다항식 개수의 랜덤 비트에 접근할 수 있는 다항 시간 기계의 클래스인 는 co-RP이다. 아로라와 사프라의 첫 번째 주요 결과는 라는 것이었다. 다시 말해, NP 프로토콜에서 검증자가 증명 인증서의 비트만 선택하여 볼 수 있도록 제약되어도, 사용할 수 있는 개의 랜덤 비트가 있는 한 아무런 차이가 없다.
더욱이, PCP 정리는 증명 접근 횟수를 상수까지 줄일 수 있다고 주장한다. 즉, 이다. 이들은 NP의 이러한 유용한 특성화를 사용하여 P = NP가 아닌 한 특정 NP-완전 문제의 최적화 버전에 대한 근사 알고리즘이 존재하지 않음을 증명했다. 이러한 문제들은 현재 근사 난해라고 알려진 분야에서 연구되고 있다.
계산 복잡도 이론에서 DSPACE 또는 SPACE는 결정론적 튜링 기계의 메모리 공간 자원을 설명하는 연산 자원이다. 이는 주어진 알고리즘으로 주어진 계산 문제를 해결하는 데 "일반적인" 물리적 컴퓨터가 필요로 하는 총 메모리 공간의 양을 나타낸다.
DSPACE 측정은 특정 양의 메모리 공간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 각 함수 f(n)에 대해 SPACE(f(n))라는 복잡도 종류가 있으며, 이는 O(f(n)) 공간을 사용하는 결정론적 튜링 기계에 의해 해결될 수 있는 결정 문제의 집합이다. 사용될 수 있는 계산 시간의 양에는 제한이 없지만, 다른 복잡도 측정(예: 교대)에는 제한이 있을 수 있다.
몇 가지 중요한 복잡도 종류는 DSPACE로 정의된다. 여기에는 다음이 포함된다.
만약 s(n) = o(log log n)에 대해 비정규 언어 L ∈ DSPACE(s(n))가 존재한다고 가정하자. M을 공간 s(n)에서 L을 결정하는 튜링 기계라고 하자. 가정에 의해 L ∉ DSPACE(O(1))이므로, 임의의 formula_1에 대해 M의 입력 중 k보다 더 많은 공간을 요구하는 것이 존재한다.
k보다 더 많은 공간을 요구하는 가장 작은 크기(n으로 표시)의 입력 x를 잡고, formula_2를 입력 x에 대한 M의 모든 구성의 집합이라고 하자. M ∈ DSPACE(s(n))이므로, formula_3이며, 여기서 c는 M에 의존하는 상수이다.
S를 x에 대한 M의 모든 가능한 교차열의 집합이라고 하자. x에 대한 M의 교차열 길이는 최대 formula_4임을 주목하자: 만약 이보다 길다면, 일부 구성이 반복되어 M은 무한 루프에 빠질 것이다. 교차열의 모든 요소에 대해 가능한 경우도 최대 formula_4이므로, x에 대한 M의 서로 다른 교차열의 수는 다음과 같다.
비둘기집 원리에 따르면, formula_7인 i &lt; j인 인덱스가 존재하며, 여기서 formula_8와 formula_9는 각각 경계 i와 j에서의 교차열이다.
를 i + 1부터 j까지의 모든 셀을 제거하여 에서 얻은 문자열이라고 하자. 기계 은 입력 에서도 입력 에서와 똑같이 동작하므로, 를 계산하는 데 를 계산하는 데와 같은 공간이 필요하다. 그러나 , 이는 의 정의와 모순된다. 따라서 가정한 언어 은 존재하지 않는다. □
위 정리는 공간 위계 정리에서 공간 구성 가능 함수 가정의 필요성을 시사한다.
DSPACE는 전통적으로 결정론적 튜링 기계에서 측정된다. 몇 가지 중요한 공간 복잡도 종류는 준선형이다. 즉, 입력 크기보다 작다. 따라서 입력 크기 또는 출력 크기에 대해 알고리즘에 "비용을 부과"하는 것은 사용된 메모리 공간을 진정으로 포착하지 못할 것이다. 이는 입력 및 출력 테이프가 있는 다중 테이프 튜링 기계를 정의함으로써 해결되는데, 이는 표준 다중 테이프 튜링 기계와 동일하지만 입력 테이프에는 절대 쓰지 않고 출력 테이프에서는 절대 읽지 않는다는 점이 다르다. 이를 통해 L (로그 공간)과 같은 더 작은 공간 종류를 모든 작업 테이프(특수 입력 및 출력 테이프 제외)가 사용한 공간의 양으로 정의할 수 있다.
알파벳의 적절한 거듭제곱을 취하여 많은 기호를 하나로 묶을 수 있으므로, 모든 c ≥ 1 및 f(n) ≥ 1인 f에 대해 c f(n) 공간에서 인식 가능한 언어의 종류는 f(n) 공간에서 인식 가능한 언어의 종류와 동일하다. 이는 정의에서 점근 표기법의 사용을 정당화한다.
위계 정리.
공간 위계 정리는 모든 공간 구성 가능 함수 formula_12에 대해 공간 formula_13에서 결정 가능하지만 공간 formula_14에서는 결정 불가능한 어떤 언어 L이 존재함을 보여준다.
DSPACE는 비결정론적 튜링 기계의 메모리 공간 종류인 NSPACE의 결정론적 대응물이다. 사비치 정리에 따르면, 다음과 같다.
NTIME은 다음과 같은 방식으로 DSPACE와 관련이 있다. 모든 시간 구성 가능 함수 t(n)에 대해,
결정론적 시간에 대한 훨씬 더 나은 시뮬레이션이 알려져 있다: 만약 formula_17이라면,
이는 윌리엄스의 결과로, 홉크로프트, 폴, 밸리언트의 이전 formula_19 한계를 개선한 것이다.
반면에, formula_20인 모든 함수에 대해,
계산 가능성과 복잡도 이론에서 ALL은 모든 결정 문제의 집합이다.
다른 종류와의 관계.
ALL은 RE와 Co-RE를 포함하는 모든 결정 문제의 복잡도 종류를 포함하며, RE도 Co-RE도 아닌 셀 수 없이 많은 언어를 포함한다. 이것은 모든 다른 복잡도 종류를 포함하는 가장 큰 복잡도 종류이다.
유니버설 씬 디스크립션(Universal Scene Description, USD)은 3차원 컴퓨터 그래픽스 데이터 교환을 위한 프레임워크이다. 이 프레임워크는 협업, 비파괴 편집, 그리고 그래픽스 데이터에 대한 다양한 관점과 의견을 가능하게 하는 데 중점을 둔다. USD는 시각 효과, 건축, 디자인, 로봇공학, CAD, 렌더링을 포함한 많은 산업에서 사용된다.
이것은 픽사에 의해 개발되었으며 2016년 수정된 아파치 라이선스에 따라 오픈 소스 소프트웨어로 처음 공개되었다. 픽사, 어도비, 애플, 오토데스크, 엔비디아는 리눅스 재단의 JDF(Joint Development Foundation)와 함께 2023년 8월 1일 AOUSD(Alliance for OpenUSD)를 발표하며 "픽사의 유니버설 씬 디스크립션 기술의 표준화, 개발, 진화 및 성장을 촉진"할 것이라고 밝혔다.
사양에 사용되는 파일 형식은 다음과 같다.
컴퓨팅에서 ACE는 마르셀 렘케가 개발하고 나중에 e-merge GmbH가 인수한 독점적인 데이터 압축 아카이브 파일 형식이다. 인기가 절정에 달했던 시기는 1999년부터 2001년까지였는데, 당시에는 RAR보다 압축률이 약간 더 좋았으나 이후 RAR이 더 인기를 얻게 되었다.
WinAce.
e-merge GmbH가 유지 관리하는 WinAce는 마이크로소프트 윈도우에서 ACE 파일을 압축하고 압축을 해제하는 데 사용된다. 설치 시 사용자에게 등록비를 지불하거나 WhenU SaveNow 애드웨어를 설치할지 선택할 수 있다. e-merge GmbH는 또한 DOS용 명령줄 ACE를 제작하며, 리눅스 (i386) 및 MacOS용 프리웨어 명령줄 인터페이스 압축 해제 도구인 "Unace"를 제공한다. e-merge GmbH는 또한 개발자를 위한 여러 라이브러리를 제공하는데, 여기에는 "unace.dll"이라는 프리웨어 압축 해제 동적 링크 라이브러리도 포함된다. 일부 타사 아카이버는 이 DLL을 사용하여 형식을 읽을 수 있다. 위에 언급된 것 중 어떤 것도 오픈 소스 자유 소프트웨어가 아니다.
2007년 11월 23일, WinACE 버전 2.69가 출시되었으며, WhenU를 대체하는 덜 침해적인 애드웨어 응용 프로그램인 MeMedia AdVantage가 포함되었다. 이 릴리스에는 다른 주요 변경 사항은 없다.
다른 구현체.
Unace 1.2b의 이전 버전은 자유 소프트웨어이며 저자 마르셀 렘케에 의해 GPL 라이선스 하에 배포되지만, 버전 2.0 이상 ACE 아카이브는 추출할 수 없다.
ACE 2.0 아카이브를 지원하는 Unace 2.5의 최신 버전은 마르셀 렘케에 의해 제한적인 source available 라이선스로 제공된다.
오래된 독립적인 C 구현체는 디르크 스퇴커의 XAD-Master libxad의 일부이다. ACE 1.0 아카이브 압축 해제에만 제한적으로 사용된다.
2017년 이후로, 다니엘 로에틀리스버거가 만든 BSD 라이선스 파이썬 모듈 및 CLI 유틸리티가 있으며, ACE 2.0 형식 아카이브의 압축 해제를 지원한다.
ACE 파일 압축은 독점 정보로 라이선스되어 WinACE를 통해서만 가능하며, ACE 파일 압축 해제는 여러 타사 압축 프로그램에서 지원된다. 그러나 거의 모든 프로그램(ACE 2.x 형식을 지원하는 프로그램)은 e-merge GmbH의 독점 "unace.dll"을 사용하여 이를 수행한다.
악성 소프트웨어 배포에 사용.