hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
쿼드트리 쿼드트리를 이용한 이미지 처리
이 알고리즘은 두 입력 쿼드트리( 및 )를 순회하면서 출력 쿼드트리 를 구축하는 방식으로 작동한다. 비공식적으로 알고리즘은 다음과 같다. 이미지의 동일한 영역에 해당하는 노드  및 를 고려한다.
이 알고리즘은 작동하지만, 그 자체로 최소 크기의 쿼드트리를 보장하지는 않는다. 예를 들어,  크기의 바둑판(모든 타일이 픽셀인)과 그 보수를 합집합하는 결과를 고려해 보자. 결과는 루트 노드(검은색으로 칠해진)만 있는 쿼드트리로 표현되어야 할 거대한 검은색 사각형이지만, 대신 알고리즘은 깊이 의 완전 4진 트리를 생성한다. 이를 해결하기 위해, 결과 쿼드트리의 상향식 순회를 수행하여 네 자식 노드가 동일한 색상인지 확인하고, 이 경우 부모 노드를 동일한 색상의 리프로 대체한다.
두 이미지의 교집합은 거의 동일한 알고리즘이다. 두 이미지의 교집합을 생각하는 한 가지 방법은 흰색 픽셀에 대한 합집합을 수행하는 것이다. 따라서 교집합을 수행하려면 합집합 알고리즘에서 검은색과 흰색의 언급을 바꾼다.
쿼드트리 쿼드트리를 이용한 이미지 처리
이진 이미지에서 인접한 두 검은색 픽셀을 고려해 보자. 이들은 경계 수평 또는 수직 가장자리를 공유하면 인접한다. 일반적으로 두 검은색 픽셀은 인접한 픽셀로만 이동하여 다른 픽셀에서 도달할 수 있으면 연결된다(즉, 각 연속 쌍이 인접한 검은색 픽셀 경로가 존재한다). 연결된 검은색 픽셀의 각 최대 집합은 연결 성분이다. 이미지의 쿼드트리 표현을 사용하여 사메트는 쿼드트리 크기에 비례하는 시간으로 이러한 연결 성분을 찾고 레이블을 지정하는 방법을 보여주었다. 이 알고리즘은 다각형 색칠에도 사용될 수 있다.
알고리즘은 세 단계로 작동한다.
논의를 단순화하기 위해 쿼드트리 노드의 자식이 Z-차순 (SW, NW, SE, NE)을 따른다고 가정하자. 이 구조를 믿을 수 있기 때문에, 어떤 셀에 대해서도 계층 구조의 다른 수준에서 인접한 셀을 찾기 위해 쿼드트리를 탐색하는 방법을 안다.
쿼드트리 쿼드트리를 이용한 이미지 처리
1단계는 쿼드트리의 후위 순회로 수행된다. 각 검은색 리프 에 대해 북쪽 이웃 및 동쪽 이웃(즉, 의 셀과 가장자리를 공유하는 북쪽 및 동쪽 셀)을 나타내는 노드를 살펴본다. 트리가 Z-순서로 구성되어 있으므로 남쪽 및 서쪽 이웃은 이미 처리되고 고려되었다는 불변성을 가진다. 현재 고려 중인 북쪽 또는 동쪽 이웃을 라고 하자. 만약 가 검은색 픽셀을 나타내면:
2단계는 합집합-찾기 자료 구조를 사용하여 수행할 수 있다. 각 고유 레이블을 별도의 집합으로 시작한다. 첫 번째 단계에서 기록된 모든 동등 관계에 대해 해당 집합을 합집합한다. 그 후, 남아있는 각 고유 집합은 이미지의 고유한 연결 성분과 연결된다.
3단계는 또 다른 후위 순회를 수행한다. 이번에는 각 검은색 노드 에 대해 합집합-찾기의 find 연산( 의 이전 레이블과 함께)을 사용하여 의 새 레이블을 찾고 할당한다( 가 속한 연결 성분과 연결된).
쿼드트리 쿼드트리를 이용한 메시 생성
이 섹션은 하르-펠레드와 데 베르그 등의 책에서 발췌한 장을 요약한 것이다.
메시 생성은 본질적으로 추가 처리가 수행될 수 있는 점 집합의 삼각측량이다. 따라서 결과 삼각측량이 특정 속성(예: 비균일성, "너무 가늘지 않은" 삼각형, 희소 영역의 큰 삼각형, 밀집 영역의 작은 삼각형 등)을 갖는 것이 바람직하며, 이는 추가 처리를 더 빠르고 오류가 적게 만든다. 점 집합에 구축된 쿼드트리는 이러한 원하는 속성을 가진 메시를 생성하는 데 사용될 수 있다.
쿼드트리의 리프와 해당 셀 를 고려해 보자. 셀의 각 변이 인접 셀의 모서리 점에 의해 각 변에서 최대 한 번만 교차되면 는 (메시 생성을 위해) 균형 잡혔다고 말한다. 이는 에 인접한 리프의 쿼드트리 수준이 의 수준과 최대 1만큼 차이 난다는 것을 의미한다. 모든 리프에 대해 이것이 참이면 전체 쿼드트리가 (메시 생성을 위해) 균형 잡혔다고 말한다.
쿼드트리 쿼드트리를 이용한 메시 생성
셀 와 를 중심으로 하는 동일한 크기의 셀로 구성된  이웃을 고려해 보자. 이 이웃을 확장 클러스터라고 부른다. 쿼드트리가 균형 잡혀 있고, 점 집합의 점을 포함하는 모든 리프 에 대해 해당 확장 클러스터도 쿼드트리에 있으며 확장 클러스터에 점 집합의 다른 점이 포함되어 있지 않으면 쿼드트리는 잘 균형 잡혔다고 말한다.
메시 생성은 다음과 같이 수행된다.
트리 셀의 모서리 점을 삼각측량의 정점으로 간주한다. 변환 단계 전에 우리는 일부에 점이 있는 상자들을 가지고 있다. 변환 단계는 다음 방식으로 수행된다. 각 점에 대해 셀의 가장 가까운 모서리를 점에 맞게 변형하고, 결과로 생성되는 네 개의 사각형을 "좋은" 삼각형으로 삼각측량한다(관심 있는 독자는 "좋은" 삼각형을 만드는 것에 대한 자세한 내용은 Har-Peled의 12장을 참조한다.).
쿼드트리 쿼드트리를 이용한 메시 생성
남은 정사각형은 몇 가지 간단한 규칙에 따라 삼각측량된다. 각 정규 정사각형(내부에 점이 없고 변에 모서리 점이 없는)에 대해 대각선을 도입한다. 우리가 점들을 잘 균형 잡는 속성으로 분리하는 방식 때문에, 변을 교차하는 모서리를 가진 정사각형은 변형된 정사각형이 아니다. 따라서 교차하는 모서리를 가진 정사각형은 다음과 같이 삼각측량할 수 있다. 교차하는 변이 하나인 경우, 사각형은 교차점과 반대쪽 모서리를 연결하는 긴 대각선을 추가하여 세 개의 삼각형이 된다. 교차하는 변이 네 개인 경우, 네 교차점 중 두 개 사이에 모서리를 추가하여 사각형을 절반으로 분할한 다음, 이 두 끝점을 나머지 두 교차점에 연결한다. 다른 정사각형의 경우, 중앙에 점을 도입하고 사각형의 네 모서리와 각 교차점에 연결한다.
결국, 쿼드트리에서 구축된 점 집합의 잘 삼각측량된 메시를 얻게 된다.
쿼드트리 의사 코드
다음 의사 코드는 점만 처리하는 쿼드트리를 구현하는 한 가지 방법을 보여준다. 다른 접근 방식도 사용할 수 있다.
이러한 구조가 사용된다고 가정한다.
이 클래스는 하나의 쿼드트리와 그것이 뿌리내린 노드를 모두 나타낸다.
다음 메서드는 필요에 따라 분할하여 점을 쿼드트리의 적절한 쿼드에 삽입한다.
다음 메서드는 범위 내에 포함된 모든 점을 찾는다.
펜윅 트리
펜윅 트리(Fenwick tree) 또는 이진 인덱스 트리(binary indexed tree, BIT)는 값의 배열을 저장하고 값의 누적 합을 효율적으로 계산하며 값을 업데이트할 수 있는 자료 구조이다. 또한 지정된 값 이하의 합계를 가진 가장 긴 접두사를 찾기 위한 효율적인 순위 검색 연산도 지원한다. 주로 자주 업데이트되는 통계 빈도 테이블의 누적 분포 함수에 대해 작동하는 데 사용된다.
이 구조는 1989년 보리스 랴프코가 제안했으며 1992년에 추가 수정이 발표되었다. 이후 피터 펜윅이 1994년 논문에서 이 구조를 설명한 후 펜윅 트리라는 이름으로 알려지게 되었다.
값의 단순 배열은 업데이트하기 쉽지만(상수 시간) 누적 합을 계산하거나 접두사 길이를 검색하는 데는  시간이 필요하다.
펜윅 트리
누적 합 배열은 상수 시간에 누적 합을 반환하고,  시간에 접두사 길이를 검색할 수 있지만, 값 중 하나를 업데이트하는 데는  시간이 필요하다.
펜윅 트리는 세 가지 작업을 모두  시간에 수행할 수 있다. 이는 값을 개의 노드를 가진 트리로 표현하여 각 트리의 노드가 해당 부모 노드의 인덱스(배타적)부터 해당 노드의 인덱스(포괄적)까지의 값의 합을 저장함으로써 달성된다. 트리는 그 자체가 암시적 자료 구조이며 개의 값 배열로 저장될 수 있으며, 암시적 루트 노드는 배열에서 생략된다. 트리 구조는 값 검색, 값 업데이트, 누적 합 및 범위 합 작업을  노드 액세스만을 사용하여 수행할 수 있도록 한다.
펜윅 트리 동기
값의 배열이 주어졌을 때, 때로는 특정 결합적이항 연산 (정수의 덧셈이 가장 흔함)에 따라 각 인덱스까지의 값의 누적 합을 계산하는 것이 바람직하다. 펜윅 트리는 기본 값 배열의 변경을 허용하고 모든 후속 쿼리가 이러한 변경을 반영하도록 하면서, 어떤 인덱스에서든 누적 합 또는 접두사 합을 쿼리하는 방법을 제공한다.
펜윅 트리는 적응형 산술 부호화를 구현하는 데 특별히 고안되었는데, 이는 생성된 각 심볼의 수를 유지하고 이를 주어진 심볼보다 작은 심볼의 누적 확률로 변환해야 한다. 지원하는 연산의 개발은 주로 이 경우의 사용에 동기가 부여되었다.
펜윅 트리 설명
펜윅 트리는 노드가 연속적으로 번호가 매겨지고, 부모-자식 관계가 노드 인덱스에 대한 산술 연산으로 결정되는 암시적 자료 구조이다.
이 인덱스 산술에서 중요한 함수는 최하위 비트이다. 이는 인덱스 를 나누는 가장 큰 2의 거듭제곱이다. 이는 지수(0, 1, 2, 3, ...)가 아닌 2의 거듭제곱(1, 2, 4, 8, ...)이다. 2의 보수 산술에서  (여기서 &는 비트 AND를 나타냄)로 효율적으로 계산할 수 있다.
펜윅 트리는 1-기반 배열 에 개의 값을 사용하여 가장 쉽게 이해된다. 반개방 구간 표기법을 사용하여 는 (배타적)부터 (포괄적)까지의 범위를 나타낸다. 해당 펜윅 배열 은 범위 합 를 저장한다. 즉, 를 포함하여 끝나는 개 값의 합이다.
일부 설명에서는 가상의 노드 0이 사용되지만, 실제로는 액세스되지 않으며 명시적으로 저장할 필요가 없다. 이지만 이 값은 실제로는 필요하지 않다. 은 값 0을 가진 빈 범위 의 합을 포함하는 것으로 간주될 수 있다.
펜윅 트리 설명
"펜윅 트리"는 실제로는 동일한 배열에 대한 세 가지 암시적 트리를 의미한다: 인덱스를 접두사 합으로 변환하는 데 사용되는 쿼리 트리, 요소를 업데이트하는 데 사용되는 업데이트 트리, 그리고 접두사 합을 인덱스로 변환하는 데 사용되는 검색 트리(순위 쿼리). 처음 두 트리는 일반적으로 위로 이동하며, 세 번째 트리는 일반적으로 아래로 이동한다.
쿼리 트리는 노드 의 부모가 가 되도록 정의된다. 예를 들어, 6 = 1102의 부모는 4 = 1002이다. 암시적 노드 0은 루트이다.
트리의 각 레벨 는 개의 고유한 2의 거듭제곱 합에 해당하는 인덱스를 가진 노드를 포함한다(은 빈 합 0을 나타냄). 예를 들어, 레벨 은 노드 를 포함하고 레벨 는 노드 를 포함한다.
노드 는 개의 자식()을 가지며, 총 개의 자손을 가진다. (이 숫자에는 보다 큰 노드가 포함되며, 이 노드들은 생략되고 액세스되지 않는다.)
아래 다이어그램은 16개 노드 펜윅 트리의 쿼리 트리의 구조를 보여주며, 루트를 포함하므로 15개 요소 배열 A에 해당한다:
펜윅 트리 설명
누적 합 를 찾으려면, 와 그 부모, 부모의 부모 등 루트(포함하지 않음)까지의 값을 더한다. 범위 합 를 계산하려면, 과 에 대한 누적 합을 뺀다.
이는 첫 번째 공통 조상에서 멈춤으로써 최적화될 수 있다. 극단적인 예는 단일 엔트리 를 요청하는 것이다. 이 경우, 와 의 공통 조상은 이므로, 에서 시작하고 인 동안 를 빼고 i := i - lsb(i)로 업데이트한다.
업데이트 트리는 쿼리 트리의 거울상이다. 노드 의 부모는 이다 (여기서 |는 비트 OR을 나타냄). 예를 들어, 6 = 1102의 부모는 8 = 10002이다.
이 개념적인 트리는 무한하지만, 까지의 인덱스를 가진 부분만 저장되거나 사용된다. 보다 큰 인덱스를 가진 가상의 노드를 제외하면, 의 이진 표현에서 설정된 각 비트에 대해 하나의 분리된 트리의 숲이 된다.
여기서 노드의 조상은 자신의 범위 합을 포함하는 모든 노드이다. 예를 들어, 은 의 합을 포함하고, 은 의 합을 포함한다.
의 값 중 하나를 수정하려면, 에 변경 사항을 더한 다음, 의 부모, 그 다음 조부모 등으로 인덱스가 을 초과할 때까지 계속한다.
펜윅 트리 설명
다른 두 트리와 달리, 검색 트리는 이진 트리이며 커누스가 "옆으로 된 힙"이라고 부르는 순서로 배열된다. 각 노드에는 인덱스의 이진 표현에서 후행 0의 수와 동일한 높이가 할당되며, 부모와 자식은 인접 높이의 수치적으로 가장 가까운 인덱스이다. 홀수 인덱스()를 가진 노드는 리프이다. 짝수 인덱스를 가진 노드는 다음 최저 인덱스의 가장 가까운 두 노드를 자식으로 가지며, 이다. 검색 트리에서 노드 의 부모는 이다.
예를 들어, 6 = 1102의 자식은 5 = 1012와 7 = 1112이며, 부모는 4 = 1002이다.
이 트리는 잠재적으로 무한하지만, 우리는 그 루트를 보다 작거나 같은 2의 가장 큰 거듭제곱인 가장 높은 기존 노드로 정의할 수 있다.
노드가 보다 큰 인덱스를 가진 가상의 부모를 가질 수 있지만 여전히 기존의 조부모를 가질 수 있다. 위 예제가 5개 노드 트리에 적용된다면, 노드 5는 가상의 부모 6을 가지지만, 기존의 조부모 4를 가진다.
펜윅 트리 설명
검색 트리는 이전 두 트리의 조합으로 간주될 수 있다. 노드의 왼쪽 서브트리는 업데이트 트리의 모든 자손을 포함하고, 오른쪽 서브트리는 쿼리 트리의 모든 자손을 포함한다. 검색 트리에서 노드의 부모는 쿼리 또는 업데이트 부모(노드가 각각 오른쪽 또는 왼쪽 자식인지에 따라 다름)이며, 다른 유형의 부모는 검색 트리에서 여러 번 위로 이동하여 찾을 수 있다.
그러나 검색 트리에서 위로 이동하는 경우는 드물며, 주로 순위 쿼리를 수행하는 데 사용된다: 주어진 접두사 합이 어떤 인덱스에 나타나는가? 이는 검색 트리를 아래로 이동하여 수행된다. 이동 중에 세 가지 변수가 유지된다: 현재 노드의 인덱스, 현재 노드를 루트로 하는 서브트리에서 찾는 순위, 그리고 찾는 순위가 서브트리에서 찾을 수 있는 것보다 클 경우 반환될 "폴백 인덱스"이다.
초기에는 현재 노드가 루트이고, 찾는 순위가 원래 쿼리이며, 폴백 인덱스는 순위가 트리에 없음을 나타내는 특별한 "오버플로" 값이다. (응용 프로그램에 따라  또는 이 이 목적으로 사용될 수 있다.)
각 단계에서 현재 노드가 가상의 노드(인덱스가 보다 큼)이거나, 찾는 위치가 현재 노드의 끝의 왼쪽 또는 오른쪽인지 결정해야 한다. 찾는 순위가 현재 노드에 대한 펜윅 배열 값 보다 작으면 왼쪽 서브트리를 검색해야 한다. 크면 오른쪽 서브트리를 검색한다. 같으면 선택된 방향은 두 노드 사이에 정확히 있는 합계를 검색하는 방법을 처리하는 방법에 따라 달라진다.
이 세 가지 가능성은 현재 노드가 리프인지 아닌지에 따라 추가로 나뉜다:
현재 노드가 리프가 아니고:
가상이면 변경되지 않은 폴백 인덱스로 왼쪽 서브트리에서 동일한 순위를 검색한다.
대상이 왼쪽 서브트리에 있으면 현재 인덱스를 폴백 인덱스로 사용하여 왼쪽 서브트리에서 동일한 순위를 검색한다.
대상이 오른쪽 서브트리에 있으면 변경되지 않은 폴백 인덱스로 오른쪽 서브트리에서 현재 노드의 값을 뺀 대상 순위를 검색한다.
펜윅 트리 의사코드
펜윅 트리의 두 가지 주요 연산(쿼리 및 업데이트)에 대한 간단한 의사코드 구현은 다음과 같다:
함수 은 주어진 의 최하위 비트를 계산하거나, 동일하게 의 약수이기도 한 가장 큰 2의 거듭제곱을 계산한다. 예를 들어, 는 이진 표현에서 보듯이: 이다. 이 함수는 2의 보수 부정을 가정할 때 비트 AND 연산을 통해 코드에서 간단히 구현될 수 있다: lsb(n) = n & (-n).
펜윅 트리를 구성하는 한 가지 비효율적인 알고리즘은 트리를 널 값으로 초기화하고 각 인덱스를 개별적으로 업데이트하는 것이다. 이 해결책은  시간에 작동하지만,  구성도 가능하다:
다항 위계
계산 복잡도 이론에서 다항 위계(Polynomial hierarchy), 다항 시간 위계는 NP 및 Co-NP 클래스를 일반화하는 위계적인 복잡도 종류이다. 위계의 각 클래스는 PSPACE 내에 포함된다. 이 위계는 신탁 기계 또는 교대 튜링 기계를 사용하여 정의할 수 있다. 이는 수리 논리학의 산술적 위계 및 해석적 위계에 대한 자원 제약적 대응물이다. 위계 내 클래스의 합집합은 PH로 표기된다.
위계 내의 클래스는 수량자 순서에 대한 제한이 있는 공식에 대해 정량화 부울 공식이 참인지 묻는 완전한 문제(다항 시간 환원과 관련하여)를 가진다. 위계에서 동일한 수준 또는 연속적인 수준의 클래스 간의 등식은 해당 수준으로 위계가 "붕괴"함을 의미한다는 것이 알려져 있다.
다항 위계 정의
다항 위계의 클래스에 대한 여러 동등한 정의가 있다.
다항 위계의 신탁 정의를 위해 다음을 정의한다.
여기서 P는 다항 시간 내에 해결 가능한 결정 문제들의 집합이다. 그런 다음 i ≥ 0에 대해 다음을 정의한다.
여기서 는 클래스 A의 어떤 완전 문제에 대한 신탁에 의해 다항 시간에 해결 가능한 결정 문제들의 집합이다. 클래스  및 는 유사하게 정의된다. 예를 들어,  이고 는 어떤 NP-완전 문제에 대한 오라클을 가진 결정적 튜링 기계로 다항 시간 안에 해결 가능한 문제들의 클래스이다.
다항 위계의 존재/전체 정의를 위해, L을 형식 언어(즉, 결정 문제, {0,1}*의 부분집합)라고 하고, p를 다항식이라고 하자. 그리고 다음을 정의한다.
여기서 는 두 이진 문자열 x와 w를 하나의 이진 문자열로 인코딩하는 표준 방법이다. 언어 L은 문자열의 순서쌍 집합을 나타내며, 첫 번째 문자열 x는 의 멤버이고 두 번째 문자열 w는 x가 의 멤버임을 증명하는 "짧은" () 증거이다. 다시 말해, 인 경우에만 를 만족하는 짧은 증거 w가 존재한다. 비슷하게, 다음을 정의한다.
다항 위계 정의
드 모르간의 법칙이 성립한다:  및 , 여기서 Lc는 L의 여집합이다.
C가 언어의 클래스라고 하자. 이러한 연산자를 언어의 전체 클래스에 적용하도록 다음 정의를 통해 확장한다.
다시 말해, 드 모르간의 법칙이 성립한다:  및 , 여기서 이다.
클래스 NP와 Co-NP는 , 그리고 로 정의할 수 있으며, 여기서 P는 모든 실행 가능하게 (다항 시간) 결정 가능한 언어의 클래스이다. 다항 위계는 다음과 같이 재귀적으로 정의할 수 있다.
및 임을 주목한다.
이 정의는 다항 위계와 산술적 위계 사이의 밀접한 관계를 반영하며, 여기서 R과 RE는 각각 P와 NP에 비유되는 역할을 한다. 해석적 위계 또한 유사한 방식으로 정의되어 실수의 부분 집합 위계를 제공한다.
교대 튜링 기계는 비최종 상태가 존재 상태와 전체 상태로 분할된 비결정적 튜링 기계이다. 다음 경우에 현재 구성에서 결국 수락한다: 존재 상태에 있고 결국 수락하는 구성으로 전환할 수 있는 경우; 또는, 전체 상태에 있고 모든 전환이 결국 수락하는 구성으로 이어지는 경우; 또는, 수락 상태에 있는 경우.
다항 위계 정의
를 다항 시간 내에 교대 튜링 기계에 의해 수락되는 언어의 클래스라고 정의한다. 이 기계는 초기 상태가 존재 상태이고 기계가 취할 수 있는 모든 경로가 존재 상태와 전체 상태 사이를 최대 k – 1번 교환한다. 유사하게, 를 초기 상태가 전체 상태인 경우로 정의한다.
존재 상태와 전체 상태 사이의 최대 k – 1회 교환 요구 사항을 생략하고 교대 튜링 기계가 다항 시간에 실행되기만 요구하는 경우, 클래스 AP의 정의를 가지며, 이는 PSPACE와 같다.
다항 위계 다항 위계 내 클래스 간의 관계
다항 위계의 모든 클래스의 합집합은 복잡도 클래스 PH이다.
정의는 다음과 같은 관계를 암시한다.
포함 관계가 참임이 알려진 산술 및 해석적 위계와 달리, 이러한 포함 관계 중 어느 것이 참인지에 대한 질문은 미해결 문제이지만, 모두 참이라고 널리 믿어진다. 만약 어떤 이거나, 어떤 이면, 위계는 k 수준으로 붕괴된다: 모든 에 대해 이다. 특히, 미해결 문제와 관련된 다음 함의가 있다.
NP = PH인 경우를 PH가 두 번째 수준으로 붕괴되었다고도 한다. P = NP인 경우는 PH가 P로 붕괴된 것에 해당한다.
첫 번째 수준으로의 붕괴 문제는 일반적으로 매우 어렵다고 생각된다. 대부분의 연구자들은 두 번째 수준으로의 붕괴조차 믿지 않는다.
다항 위계 다른 클래스와의 관계
다항 위계는 지수 위계와 산술적 위계의 아날로그(훨씬 낮은 복잡도에서)이다.
PH는 PSPACE 내에 포함되어 있지만, 두 클래스가 같은지는 알려져 있지 않다. 이 문제의 유용한 재정식화는 PH = PSPACE인 경우에만 유한 구조에 대한 2차 논리가 관계에 대한 관계(즉, 2차 변수에 대한) 전이 폐포 연산자의 추가로 추가적인 능력을 얻지 못한다는 것이다.
다항 위계에 완전 문제가 있다면, 그것은 유한하게 많은 고유한 수준만을 가진다. PSPACE-완전 문제가 존재하므로, PSPACE = PH라면 다항 위계는 붕괴해야 한다. 왜냐하면 PSPACE-완전 문제는 어떤 k에 대한 -완전 문제가 될 것이기 때문이다.
다항 위계 다른 클래스와의 관계
다항 위계의 각 클래스는 -완전 문제(다항 시간 다대일 환원에 대한 완전 문제)를 포함한다. 또한, 다항 위계의 각 클래스는 -환원에 대해 닫혀 있다: 즉, 위계 내의 클래스 C와 언어 에 대해, 만약 이면 이다. 이 두 가지 사실은 가 에 대한 완전 문제라면, 이고 임을 의미한다. 예를 들어, 이다. 다시 말해, 어떤 언어가 C의 어떤 오라클을 기반으로 정의된다면, 그것이 C에 대한 완전 문제를 기반으로 정의된다고 가정할 수 있다. 따라서 완전 문제는 그것이 완전한 클래스의 "대표" 역할을 한다.
양자 컴퓨터에 의해 다항 시간 안에 해결 가능한 문제들의 클래스인 BQP가 PH에 포함되지 않는다는 일부 증거가 있다. 그러나 PH가 BQP에 포함되지 않는다고도 믿어진다.=
PP (복잡도)
복잡도 이론에서 PP 또는 PPT는 모든 인스턴스에 대해 오차 확률이 1/2 미만으로 다항 시간에 확률적 튜링 기계로 해결 가능한 결정 문제의 종류이다. 약어 PP는 확률적 다항 시간을 의미한다. 이 복잡도 종류는 길(Gill)이 1977년에 정의했다.
결정 문제가 PP에 속한다면, 확률적 결정을 내릴 수 있는 다항 시간 실행 알고리즘이 존재하며, 이 알고리즘은 1/2보다 높은 확률로 올바른 답을 반환한다. 좀 더 실용적인 용어로 설명하면, 이 종류는 무작위 다항 시간 알고리즘을 충분한(그러나 유한한) 횟수만큼 실행함으로써 어떤 고정된 정확도까지 해결할 수 있는 문제들의 종류이다.
PP (복잡도)
다항적으로 제한된 확률적 튜링 기계는 확률적 다항 시간 기계를 나타내는 PPT로 특징지어진다. 이 튜링 기계의 특징은 유한한 오차 확률을 요구하지 않는다. 따라서 PP는 오차 확률이 1/2 미만인 PPT 기계로 해결할 수 있는 모든 문제를 포함하는 복잡도 종류이다.
PP의 대안적인 특징은 다항 시간 내에 비결정론적 튜링 기계로 해결할 수 있는 문제들의 집합으로, 수용 조건은 계산 경로의 과반수(절반 이상)가 수용하는 것이다. 이 때문에 일부 저자들은 대체 이름으로 Majority-P를 제안했다.
PP (복잡도) 정의
언어 L이 PP에 속하는 경우는 다음과 같은 확률적 튜링 기계 M이 존재하는 경우에 한한다.
다른 방법으로, PP는 결정론적 튜링 기계만을 사용하여 정의할 수 있다. 언어 L이 PP에 속하는 경우는 다음과 같은 다항식 p와 결정론적 튜링 기계 M이 존재하는 경우에 한한다.
이 정의에서 문자열 y는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 결과에 해당한다.
두 정의 모두에서, "미만"은 "이하"로 변경될 수 있고(아래 참조), 임계값 1/2은 (0,1) 범위의 어떤 고정된 유리수로 대체될 수 있으며, 이는 종류를 변경하지 않는다.
PP (복잡도) PP 대 BPP
BPP는 PP의 부분집합이다. 이는 효율적인 확률적 알고리즘이 존재하는 부분집합으로 볼 수 있다. 차이점은 허용되는 오차 확률에 있다. BPP에서는 알고리즘이 2/3 또는 1000분의 501과 같은 1/2보다 큰 고정 상수 c를 초과하는 확률로 올바른 답(예 또는 아니요)을 제공해야 한다. 이 경우, 체르노프 경계를 사용하여 알고리즘을 여러 번 실행하고 다수결을 통해 1 미만의 원하는 정확도 확률을 달성할 수 있다. 이 반복 횟수는 c가 1/2에 가까워질수록 증가하지만, 입력 크기 n에는 의존하지 않는다.
더 일반적으로, c가 입력 크기 에 다항적으로, 즉 와 같이 의존할 수 있다면, 알고리즘을 번 재실행하고 다수결을 취할 수 있다. 호프딩 부등식에 의해, 이는 우리에게 BPP 알고리즘을 제공한다.
PP (복잡도) PP 대 BPP
중요한 점은 이 상수 c가 입력에 의존하도록 허용되지 않는다는 것이다. 반면에, PP 알고리즘은 다음과 같은 작업을 수행할 수 있다.
이 두 확률은 지수적으로 매우 가깝기 때문에, 다항 시간 동안 실행하더라도 우리가 YES 인스턴스에서 작동하고 있는지 NO 인스턴스에서 작동하고 있는지 구분하기가 매우 어렵다. 다수결과 체르노프 경계를 사용하여 고정된 원하는 확률 수준을 달성하려고 시도하면 n에 대해 지수적인 반복 횟수가 필요하다.
PP (복잡도) 다른 복잡도 종류와 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를 출력한다.
PP (복잡도) 다른 복잡도 종류와 PP 비교
만약 공식이 충족 불가능하다면, 알고리즘은 항상 1/2 - 1/2n + 1 < 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 (복잡도) 다른 복잡도 종류와 PP 비교
더 나아가, 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)에 포함되지 않는다.
PP (복잡도) 완전 문제 및 기타 속성
BPP와 달리, PP는 의미론적 종류가 아닌 구문론적 종류이다. 어떤 다항 시간 확률적 기계도 PP에 속하는 어떤 언어를 인식한다. 반대로, 다항 시간 확률적 기계의 설명이 주어졌을 때, 그것이 BPP에 속하는 언어를 인식하는지 여부를 결정하는 것은 일반적으로 결정 불가능하다.
PP에는 자연스러운 완전 문제들이 있는데, 예를 들어 MAJSAT이 있다. MAJSAT은 불리언 공식 F가 주어졌을 때, 모든 할당 x1, x2, ..., xn 중 절반 이상이 F를 참으로 만드는 경우 YES를, 그렇지 않은 경우 NO를 답해야 하는 결정 문제이다.
L을 PP에 속하는 언어라고 하자. 를 L의 여집합이라고 하자. PP의 정의에 의해 다음과 같은 속성을 가진 다항 시간 확률적 알고리즘 A가 존재한다.
우리는 일반성을 잃지 않고, 후자의 부등식이 항상 엄격하다고 주장한다. 정리는 이 주장으로부터 추론될 수 있다: A가 거부하는 경우 는 수용하고 그 반대인 기계인 를 정의하자. 그러면
이는 가 PP에 속함을 의미한다.
PP (복잡도) 완전 문제 및 기타 속성
이제 일반성을 잃지 않고 가정을 정당화한다. 를 입력 x에 대한 A의 실행 시간의 다항 상한이라고 하자. 따라서 A는 실행 중 최대 개의 무작위 동전 던지기를 수행한다. 특히 수용 확률은 의 정수배이며 다음과 같다.
기계 A′를 다음과 같이 정의한다. 입력 x에 대해 A′는 A를 서브루틴으로 실행하고, A가 거부하면 거부한다. 그렇지 않고 A가 수용하면 A′는 개의 동전을 던지고, 모두 앞면이면 거부하고, 그렇지 않으면 수용한다. 그러면
이고
이는 가정을 정당화하고(A′는 여전히 다항 시간 확률적 알고리즘이므로) 증명을 완료한다.
데이비드 루소는 1985년 박사 학위 논문에서 PP가 대칭차에 대해 닫혀 있음을 증명했다. PP가 합집합과 교집합에 대해 닫혀 있는지 여부는 14년 동안 열린 문제였다. 이는 비겔(Beigel), 라인골드(Reingold), 스필먼(Spielman)에 의해 긍정적으로 해결되었다. 리(Li)와 애런슨(Aaronson)이 나중에 다른 증명을 제시했다(아래 #PostBQP 참조).
PP (복잡도) 다른 동등한 복잡도 종류
양자 복잡도 종류 BQP는 양자 튜링 기계에서 다항 시간에 해결할 수 있는 문제의 종류이다. 후선택을 추가함으로써 더 큰 종류인 PostBQP를 얻을 수 있다. 비공식적으로, 후선택은 컴퓨터에 다음과 같은 능력을 부여한다: 어떤 사건(예: 특정 상태의 큐비트 측정)이 0이 아닌 확률을 가질 때마다, 그것이 발생했다고 가정할 수 있다. 스콧 애런슨은 2004년에 PostBQP가 PP와 동일하다는 것을 보였다. 이 PP의 재정의는 PP가 교집합(따라서 합집합)에 대해 닫혀 있다는 것, BQP가 PP에 대해 low라는 것, 그리고 QMA가 PP에 포함된다는 것과 같은 특정 결과를 더 쉽게 보여준다.
PP는 또한 BQP의 무제한 오차 아날로그로 알려진 또 다른 양자 복잡도 종류인 PQP와 동일하다. 이는 모든 인스턴스에 대해 오차 확률이 1/2 미만으로, 다항 시간 내에 양자 컴퓨터로 해결할 수 있는 결정 문제의 종류를 나타낸다. PQP 계산에 사용되는 모든 진폭이 대수적 수에서 파생된 경우에도 PQP는 PP와 일치한다.
PP (복잡도) 각주
Allender, E. (1996). 〈A note on uniform circuit lower bounds for the counting hierarchy〉. 《Proceedings 2nd International Computing and Combinatorics Conference (COCOON)》. Lecture Notes in Computer Science 1090. Springer-Verlag. 127–135쪽. .
Burtschick, Hans-Jörg; Vollmer, Heribert (1998). 《Lindström quantifiers and leaf language definability》. 《Int. J. Found. Comput. Sci.》 9. 277–294쪽. doi:10.1142/S0129054198000180. 틀:ECCC.
NEXPTIME
계산 복잡도 이론에서 복잡도 종류 NEXPTIME (가끔 NEXP로 불림)은  시간 내에 비결정론적 튜링 기계로 풀 수 있는 결정 문제들의 집합이다.
NTIME 관점에서,
다른 방식으로, NEXPTIME은 검증자로 결정론적 튜링 기계를 사용하여 정의할 수 있다. 언어 L이 NEXPTIME에 속하는 것은 다항식 p와 q, 그리고 결정론적 튜링 기계 M이 존재하여 다음을 만족할 때이다.
우리는 다음을 알고 있다.
P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME
또한, 시간 위계 정리에 의해 다음을 알 수 있다.
NP ⊊ NEXPTIME
만약 P = NP라면, NEXPTIME = EXPTIME (패딩 논증); 더 정확히는, E ≠ NE일 때에만 P에 속하지 않는 희소 언어가 NP에 존재한다.
NEXPTIME 다른 특성화
서술 복잡도에서 NEXPTIME에서 인식될 수 있는 자연수의 집합은 정확히 어떤 논리 문장의 문장의 스펙트럼, 즉 유한 모델들의 크기 집합을 형성하는 것들이다.
NEXPTIME은 종종 대화형 증명 시스템의 맥락에서 발생하며, 여기에는 두 가지 주요 특징이 있다. 첫 번째는 MIP 증명 시스템인데, 여기에는 무한한 능력을 가진 두 명의 증명자(서로 통신하지 않음)가 무작위 다항 시간 검증자와 통신한다. 문자열이 언어에 있으면 높은 확률로 검증자를 확신시켜야 한다. 문자열이 언어에 없으면 낮은 확률을 제외하고는 검증자가 문자열을 수락하도록 공동으로 속일 수 없어야 한다. MIP 증명 시스템이 NEXPTIME의 모든 문제를 해결할 수 있다는 사실은 증명자가 한 명만 있을 때 PSPACE의 모든 문제를 인식할 수 있다는 점을 고려하면 상당히 인상적이다. 검증자가 두 증명자를 "교차 심문"하는 능력은 큰 힘을 부여한다. 자세한 내용은 대화형 증명 시스템#MIP을 참조하라.
NEXPTIME 다른 특성화
NEXPTIME을 특징짓는 또 다른 대화형 증명 시스템은 특정 종류의 확률적으로 검사 가능한 증명이다. NP는 무한한 능력을 가진 증명자가 문자열이 언어에 있음을 증명하는 증거를 제시하고, 결정론적 다항 시간 기계가 그것이 유효한 증거임을 검증하는 문제들의 종류로 볼 수 있다. 이 설정에 두 가지 변화를 준다.
이 두 가지 확장은 함께 증명 시스템의 능력을 크게 확장하여 NEXPTIME의 모든 언어를 인식할 수 있게 한다. 이 클래스는 PCP(poly, poly)라고 불린다. 더 나아가, 이 특성화에서 검증자는 단지 상수 비트만 읽도록 제한될 수 있다. 즉, NEXPTIME = PCP(poly, 1)이다. 자세한 내용은 확률적으로 검사 가능한 증명을 참조하라.
NEXPTIME NEXPTIME-완전
결정 문제는 NEXPTIME에 속하고, NEXPTIME의 모든 문제는 그것에 대한 다항 시간 다대일 환산이 있으면 NEXPTIME-완전이다. 다시 말해, 한 인스턴스를 같은 답을 가진 다른 인스턴스로 변환하는 다항 시간 알고리즘이 존재한다. NEXPTIME-완전 문제는 NEXPTIME에서 가장 어려운 문제로 생각할 수 있다. 우리는 NEXPTIME-완전 문제가 NP에 속하지 않는다는 것을 알고 있다. 이 문제들은 시간 위계 정리에 의해 다항 시간 내에 검증될 수 없다는 것이 증명되었다.
NEXPTIME NEXPTIME-완전 문제의 예
NEXPTIME-완전 문제의 중요한 집합은 간결한 회로와 관련이 있다. 간결한 회로는 그래프를 기하급수적으로 적은 공간으로 기술하는 데 사용되는 간단한 기계이다. 이들은 두 개의 정점 번호를 입력으로 받아 그들 사이에 에지가 있는지 여부를 출력한다. 인접행렬과 같은 자연스러운 표현으로 그래프 문제를 해결하는 것이 NP-완전이라면, 간결한 회로 표현으로 같은 문제를 해결하는 것은 NEXPTIME-완전이다. 왜냐하면 입력이 기하급수적으로 작기 때문이다 (NP-완전성 환산이 "투영"에 의해 달성된다는 약간의 조건 하에). 한 가지 간단한 예로, 그렇게 인코딩된 그래프의 해밀턴 경로를 찾는 것은 NEXPTIME-완전이다.
두 변수를 가진 1차 논리의 만족성 문제는 NEXPTIME-완전이다. 계수와 두 변수를 가진 1차 논리의 만족성 문제는 NEXPTIME-완전이다.
의존성 한정 이진 공식(DQBF, QBF의 불완전 정보 버전)에서 공식이 참인지 결정하는 것은 NEXPTIME-완전이다. 팀을 가진 제약 논리의 불완전 정보도 NEXPTIME-완전이다.
DTIME
계산 복잡도 이론에서 DTIME 또는 TIME은 결정론적 튜링 기계의 연산 시간 연산 자원이다. 이는 "일반적인" 물리 컴퓨터가 특정 알고리즘을 사용하여 특정 계산 문제를 해결하는 데 걸리는 시간(또는 계산 단계 수)을 나타낸다. 이는 중요한 실제 자원(컴퓨터가 문제를 해결하는 데 걸리는 시간)과 매우 밀접하게 관련되어 있기 때문에 가장 잘 연구된 복잡성 자원 중 하나이다.
DTIME 자원은 특정 양의 연산 시간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 입력 크기 n의 문제가 으로 해결될 수 있다면, 복잡도 종류  (또는 )를 가진다. 사용되는 메모리 공간의 양에는 제한이 없지만, 다른 복잡성 자원(예: 교대)에는 제한이 있을 수 있다.
DTIME DTIME의 복잡도 종류
많은 중요한 복잡도 종류는 DTIME으로 정의되며, 특정 양의 결정론적 시간으로 해결할 수 있는 모든 문제를 포함한다. 모든 적절한 복잡도 함수를 사용하여 복잡도 종류를 정의할 수 있지만, 특정 종류만 연구하는 데 유용하다. 일반적으로, 우리는 복잡도 종류가 계산 모델의 변화에 대해 견고하고, 서브루틴의 구성에 대해 닫혀 있기를 원한다.
DTIME은 시간 계층 정리를 만족하며, 이는 점근적으로 더 많은 양의 시간이 항상 엄격하게 더 큰 문제 집합을 생성한다는 것을 의미한다.
잘 알려진 복잡도 종류 P는 다항식 시간 DTIME으로 해결할 수 있는 모든 문제를 포함한다. 이는 공식적으로 다음과 같이 정의할 수 있다.
DTIME DTIME의 복잡도 종류
P는 선형 시간 문제 를 포함하는 가장 작은 견고한 종류이다 (AMS 2004, Lecture 2.2, pg. 20). P는 "계산적으로 실현 가능한" 것으로 간주되는 가장 큰 복잡도 종류 중 하나이다.
결정론적 시간을 사용하는 훨씬 더 큰 종류는 EXPTIME이며, 이는 지수 시간에 결정론적 기계로 해결할 수 있는 모든 문제를 포함한다. 공식적으로, 우리는 다음을 얻는다.
더 큰 복잡도 종류도 비슷하게 정의할 수 있다. 시간 계층 정리 때문에, 이들 종류는 엄격한 계층 구조를 형성한다; 우리는 임을 알고 있으며, 그 이상도 마찬가지다.
DTIME 기계 모델
P와 같은 견고한 종류의 경우, DTIME을 정의하는 데 사용되는 정확한 기계 모델은 자원의 성능에 영향을 주지 않으면서 변경될 수 있다. 계산 복잡성 문헌은 특히 매우 작은 시간 종류를 논의할 때 다중 테이프 튜링 기계를 기반으로 DTIME을 정의하는 경우가 많다. 다중 테이프 결정론적 튜링 기계는 단일 테이프 기계보다 2차 시간 가속을 제공할 수 없다.
튜링 기계의 선형 속도 향상 정리 때문에, 시간 경계의 곱셈 상수는 DTIME 종류의 범위에 영향을 주지 않는다; 유한 상태 제어의 상태 수를 늘리고 테이프 알파벳의 크기를 늘림으로써 항상 상수 곱셈 속도 향상을 얻을 수 있다. 파파디미트리우의 진술에서, 언어 L에 대해,
Let . Then, for any , , where .
DTIME 일반화
결정론적 튜링 기계 이외의 모델을 사용하면 DTIME의 다양한 일반화 및 제한이 있다. 예를 들어, 비결정론적 튜링 기계를 사용하면 NTIME 자원을 얻는다. DTIME과 다른 계산 자원의 표현력 간의 관계는 거의 이해되지 않고 있다. 몇 안 되는 알려진 결과 중 하나는 다음과 같다.
다중 테이프 기계의 경우. 이것은 Santhanam에 의해 다음으로 확장되었다. 여기서 은 반복 로그이다.
교대 튜링 기계를 사용하면 ATIME 자원을 얻는다.
DTIME 각주
[[American Mathematical Society|미국 수학회]] (2004).  스티븐 루디치 and 아비 위그더슨, 편집. 《Computational Complexity Theory》. 미국 수학회 and 프린스턴 고등연구소. ISBN 0-8218-2872-X.  |author-last1= 값 확인 필요 (도움말)
NTIME
계산 복잡도 이론에서, 복잡도 종류 NTIME(f(n))는 시간 O(f(n)) 안에 실행되는 비결정론적 튜링 기계에 의해 해결될 수 있는 결정 문제들의 집합이다. 여기서 O는 점근 표기법이고, f는 어떤 함수이며, n은 입력의 크기(문제를 결정해야 하는 대상)이다.
NTIME 의미
이것은 크기 n의 주어진 입력에 대해 시간 O(f(n)) 안에 실행될 (즉, n이 어떤 값보다 클 때 f(n)의 상수배 내에서 실행될) 비결정론적 기계가 존재하며, 결정 문제의 답이 해당 입력에 대해 "아니오"인 경우 항상 입력을 "거부"하고, 답이 "예"인 경우 기계는 적어도 하나의 계산 경로에 대해 해당 입력을 "수락"한다는 것을 의미한다. 동등하게, O(f(n)) 시간 안에 실행되고 입력에 대한 O(f(n)) 길이의 인증서를 확인할 수 있는 결정론적 튜링 기계 M이 존재한다. 입력이 "예" 사례인 경우 적어도 하나의 인증서가 수락되고, 입력이 "아니오" 사례인 경우 어떤 인증서도 기계를 수락하게 만들 수 없다.
NTIME 공간 제약
기계에 사용 가능한 공간은 제한되지 않지만 O(f(n))을 초과할 수 없다. 왜냐하면 사용 가능한 시간이 테이프의 접근 가능량을 제한하기 때문이다.
NTIME 다른 복잡도 종류와의 관계
잘 알려진 복잡도 종류인 NP는 NTIME을 사용하여 다음과 같이 정의할 수 있다:
마찬가지로, 종류 NEXP는 NTIME을 사용하여 다음과 같이 정의된다:
비결정론적 시간 위계 정리는 비결정론적 기계가 점근적으로 더 많은 시간에 더 많은 문제를 해결할 수 있다고 말한다.
NTIME은 다음 방식으로 DSPACE와도 관련이 있다. 모든 시간 구성 가능 함수 t(n)에 대해 다음이 성립한다:
.
NTIME의 일반화는 교대 튜링 기계로 정의되는 ATIME이다. 다음이 성립하는 것으로 밝혀졌다:
.
NSPACE
계산 복잡도 이론에서 비결정적 공간 또는 NSPACE는 비결정적 튜링 기계의 메모리 공간을 나타내는 연산 자원이다. 이것은 DSPACE의 비결정적 대응물이다.
NSPACE 복잡도 종류
NSPACE 측정은 비결정적 튜링 기계로 해답을 결정할 수 있는 복잡도 종류를 정의하는 데 사용된다. 복잡도 종류 NSPACE(f(n))는 비결정적 튜링 기계 M이 O(f(n)) 공간을 사용하여 풀 수 있는 결정 문제의 집합이며, 여기서 n은 입력의 길이이다.
몇 가지 중요한 복잡도 종류는 NSPACE로 정의할 수 있다. 다음이 포함된다.
이머만–셀렙체니 정리는 모든 함수 s(n) ≥ log n에 대해 NSPACE(s(n))가 여집합에 대해 닫혀 있음을 명시한다.
더 나아가 일반화된 것은 교대 튜링 기계로 정의되는 ASPACE이다.
NSPACE 다른 복잡도 종류와의 관계
NSPACE는 결정적 튜링 기계의 메모리 공간 종류인 DSPACE의 비결정적 대응물이다. 정의에 따라, 그리고 새비치 정리에 따라, 우리는 다음을 가진다.
NSPACE는 다음 정리를 통해 결정적 튜링 기계의 시간 복잡도를 결정하는 데에도 사용될 수 있다.
언어 L이 비결정적 TM에 의해 공간 S(n) (여기서 S(n) ≥ log n)에서 결정된다면, L이 결정적 TM에 의해 시간 O(CS(n))에서 결정되도록 하는 상수 C가 존재한다.
NSPACE 한계
DSPACE 측면에서 공간 복잡도를 측정하는 것은 주어진 알고리즘으로 주어진 계산 문제를 해결하는 데 실제 컴퓨터가 필요로 하는 총 메모리 양을 나타내므로 유용하다. 그 이유는 DSPACE가 실제 컴퓨터를 나타낼 수 있는 결정적 튜링 기계가 사용하는 공간 복잡도를 설명하기 때문이다. 반면에 NSPACE는 실제 컴퓨터를 나타내려고 할 때 유용하지 않은 비결정적 튜링 기계의 공간 복잡도를 설명한다. 이러한 이유로 NSPACE는 실제 응용 프로그램에서의 유용성이 제한적이다.
대화형 증명 시스템
계산 복잡도 이론에서 대화형 증명 시스템(Interactive proof system)은 증명자와 검증자라는 두 주체 간의 메시지 교환으로 컴퓨테이션을 모델링하는 추상 기계이다. 이들은 주어진 문자열이 형식 언어에 속하는지 여부를 확인하기 위해 메시지를 교환한다. 증명자는 무제한의 계산 자원을 가지고 있지만 신뢰할 수 없는 반면, 검증자는 제한된 계산 능력을 가지고 있지만 항상 정직하다고 가정한다. 검증자가 문제에 대한 답을 얻고 그것이 정확하다고 "확신"할 때까지 검증자와 증명자 사이에 메시지가 전송된다.
모든 대화형 증명 시스템에는 두 가지 요구 사항이 있다.
시스템의 특정 특성과 그에 따라 인식할 수 있는 언어의 복잡도 종류는 검증자에 부과되는 제약 조건과 부여되는 능력에 따라 달라진다. 예를 들어, 대부분의 대화형 증명 시스템은 검증자의 임의 선택 능력에 결정적으로 의존한다. 또한 교환되는 메시지의 특성(개수 및 내용)에도 의존한다. 대화형 증명 시스템은 하나의 기계만을 사용하여 정의된 전통적인 복잡도 종류에 중요한 영향을 미치는 것으로 밝혀졌다. 대화형 증명 시스템을 설명하는 주요 복잡도 종류는 AM 및 IP이다.
대화형 증명 시스템 배경
모든 대화형 증명 시스템은 문자열 의 형식 언어를 정의한다. 증명 시스템의 건전성은 증명자가 작은 확률을 제외하고는 잘못된 명제 에 대해 검증자를 승인하게 할 수 없다는 속성을 나타낸다. 이 확률의 상한은 증명 시스템의 건전성 오류라고 한다. 더 공식적으로는, 모든 증명자 와 모든 에 대해 다음이 성립한다.
여기서 이다.
건전성 오류가 검증자의 잠재적 실행 시간의 다항식 분수(즉, )로 제한되는 한, 검증자의 실행 시간에 비해 건전성 오류가 미미한 함수가 될 때까지 건전성을 증폭시키는 것은 항상 가능하다. 이는 증명을 반복하고 모든 증명이 검증될 때만 수용함으로써 달성된다. 번 반복 후, 건전성 오류 는 로 감소할 것이다.
대화형 증명 시스템 대화형 증명의 종류
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 증명 시스템을 정의하는 주요 동기였다.