hotchpotch/wikipedia-multilingual-ir-related-paragraph-pairs huggingface dataset:
2000 (동음이의)
Section: 2001~2999

2010
마이크로소프트 오피스 2010
《Twenty Ten》: 가이 서배스천의 컴필레이션 음반. (2010년 11월 19일 출시)

2011
《2011》: 더 스미더린스의 정규 음반. (2011년 4월 5일 출시)
〈2011〉: 파이브 세컨즈 오브 서머의 노래. (2021년 12월 3일 출시)

2012: 메타 문서 참고.

2013
마이크로소프트 오피스 2013
〈2013〉: 악틱 몽키즈의 음반 《AM》의 디럭스 LP 에디션 수록곡. (2013년 9월 9일 출시)

2015
2015: 미국의 비디오 게임 기업.
2000 (동음이의)
Section: 2000

NGC 2000: 테이블산자리 방향에 있는 산개 성단.

CDMA2000

윈도우 2000: 마이크로소프트 윈도우 계열 운영 체제.

마이크로소프트 오피스 2000

항공
사브 2000

철도
서울교통공사 2000호대 전동차
부산교통공사 2000호대 전동차
대구교통공사 2000호대 전동차

대한민국의 보물 제2000호: 김홍도 필 삼공불환도

연도: 2000년, 기원전 2000년
2000년 문제
기오르기 사르달라슈빌리
Section: 경력

사르달라슈빌리는 2003년 트빌리시에서 태어났다.

2020년 2월 사르달라슈빌리는 튀르키예 안탈리아에서 열린 유소년 유러피언컵 대회 50kg급에서 우승을 차지했다. 이듬해인 2021년 7월  그는 체코 프라하에서 열린 청소년 유러피언컵 60kg급에서 금메달을 차지했다. 같은 해 9월에는 룩셈부르크에서 열린 유럽 주니어 선수권 대회(60kg)에서 준우승을 차지했으며 10월에는 이탈리아 올비아에서 열린 세계 주니어 선수권 대회(60kg)에서 1위를 차지했다.

2023년 5월 사르달라슈빌리는 카타르 도하에서 열린 2023년 세계 선수권 대회 남자 60kg급에서 대한민국의 이하림과 함께 동메달을 획득했다.

이듬해인 2024년 5월 사르달라슈빌리는 아랍에미리트 아부다비에서 열린 2024년 세계 선수권 대회에 출전했고 남자 60kg급에서 중화 타이베이의 양융웨이를 꺾으며 금메달을 획득했다. 같은 해 7월에는 프랑스 파리에서 열린 2024년 하계 올림픽에 참가했으며 튀르키예의 살리흐 이을드즈와 함께 5위에 올랐다.
1987년 워싱턴 정상회담
Section: 배경

전년도 레이캬비크 정상회담의 거의 돌파구에 가까운 성과에 이어, 양측 지도자의 많은 지지자들의 실망에도 불구하고, 레이건과 고르바초프는 INF 조약 협상에 자원을 투입하기 시작했다. 이는 양국 내외의 다양한 문제들과 함께 워싱턴 정상회담 이전에 긴장된 시기를 초래했다.

레이건에게는 주식 시장 문제, 대법원 지명자 로버트 보크의 승인 실패, 그리고 이란-콘트라 스캔들이 모두 정치적 압력을 가하고 있었다. 또한, 전 대통령 리처드 닉슨, 전 국무장관 헨리 키신저, 평론가 윌리엄 버클리를 포함한 이례적으로 많은 보수주의자들뿐만 아니라 그의 행정부 구성원들로부터의 비판은 INF 조약을 둘러싸고 논쟁적인 정치적 분위기를 조성했다.
1988년 모스크바 정상회담

레이건과 고르바초프는 결국 공동 성명을 발표했는데, 그 발췌본은 다음과 같다.

대통령과 서기장은 모스크바 정상회담을 미국-소련 관계를 보다 생산적이고 지속 가능한 기반 위에 올려놓는 과정의 중요한 단계로 본다.

정상회담의 아이러니한 사례 중 하나는 레이건이 고르바초프에게 영화 우정있는 설복의 복사본을 선물했는데, 이 영화의 시나리오 작가인 마이클 윌슨은 1950년대에 공산주의 동조자로 의심받아 블랙리스트에 올랐던 인물이었다.
다케노군 (교토부)
Section: 역사

1904년 1월 1일 - 아미노정·아사모가와촌이 합병하여, 새로이 아미노정이 발족.(1정 14촌)

1921년 1월 1일 - 다이자촌이 정제 시행으로 다이자정(間人町)이 됨.(2정 13촌)

1899년
7월 1일 - 군제 시행.
7월 28일 - 야기촌이 요사군 노마촌의 일부를 편입.

1900년 5월 1일 - 아미노촌이 정제 시행으로 아미노정(網野町)이 됨.(1정 15촌)
조지 H. W. 부시의 대통령직 인수
Section: 공식 인수

11월 중순, 부시는 워싱턴 D.C.의 듀폰트서클에 자신의 인수 사무실을 열었다. 인수팀은 연방 조달청이 연방 정부 건물에서 사무실 공간을 무료로 제공하는 대신, 비용을 들여 민간 건물을 사용하기로 결정했다.

1988년 11월 22일, 두버스타인은 내각 구성원과 기관장들에게 조직 문제, 목표와 기능, 자원 설명, 의회 감독 위원회, 규제 프로그램 및 각 기관과 관련된 기타 중요한 사항에 대한 정보를 인수팀에 제공해 줄 것을 요청했다.
조지 H. W. 부시의 대통령직 인수
Section: 인수 분석

1989년 3월 초, 많은 전문가들이 부시의 인수와 그의 대통령직 초기 2주가 모두 미흡했다고 주장했다고 보도되었다.

일부는 인수를 다소 울퉁불퉁했다고 회고적으로 평가했다. 2001년 3월, 브루킹스 연구소의 스티븐 헤스는 인수가 "불편했다"고 썼다.

일부는 인수에 대해 큰 칭찬을 했다. 2020년, 학자 바버라 A. 페리는 이를 "좋은" 대통령직 인수의 예로 들었다. 2000년, 볼티모어 선의 기자 조나단 와이즈먼은 이를 "최고의 인수팀 중 하나"라고 불렀다.
조지 H. W. 부시의 대통령직 인수
Section: 선거 전 전개

대통령 인수 효율성 법안은 1988년에 성공적으로 통과되었다. 이 법안은 부분적으로 대통령 인수팀에 지급되는 금액을 대통령 당선인 팀에게는 350만 달러로, 퇴임하는 대통령 행정부에게는 150만 달러로 인상한다. 또한, 인수에 대한 민간 기부와 인수 인력의 이름이 공개되어야 한다고 요구했다. 연방 서비스 및 자금을 받는 대가로, 인수팀은 취임식 후 30일 이내에 모든 민간 기부 자금의 날짜, 출처 및 금액을 공식적으로 공개해야 한다고 요구했다. 이 법안은 또한 한 사람 또는 조직으로부터 인수팀에 대한 민간 기부금에 5,000달러의 상한선을 두었다. 이 법안은 또한 연방 부서 또는 기관과의 초기 접촉 전에 인수팀 구성원에 대한 정보를 공개하도록 요구했다.

1988년 선거를 앞두고, 대통령직 인수를 더 쉽게 만들기 위해 변경이 필요하다는 초당적 합의가 있었다. 이러한 당사자 간의 합의는 아마도 레이건 대통령이 연임 제한을 받았기 때문에 1988년에 대통령직 인수가 있을 것이라는 사실 때문이었을 것이다. 의회에서 추진되던 변경 사항 중 하나는 정부가 인수에 제공하는 자금의 양을 늘리는 것이었다. 1976년 이후, 정부는 대통령 당선인 팀에 200만 달러를, 퇴임하는 대통령 행정부에 100만 달러를 인수에 자금을 지원해 왔다.
백악관 로즈 가든
Section: 설계 및 원예

백악관 로즈 가든은 1913년에 우드로 윌슨의 부인인 엘렌 악손 윌슨이 조성했으며, 조경가 조지 버냅이 설계했다. 1935년 프랭클린 D. 루스벨트 미국 대통령은 프레데릭 로 옴스테드 주니어에게 정원 재설계를 의뢰했고, 그는 주철 가구를 설치했다.

1902년 이전에는 현재의 오벌 오피스, 캐비닛룸, 로즈 가든 구역에 말과 마차를 수용하는 광대한 마구간이 있었다. 이 지역에는 또한 온실 장미관도 있었다. 1902년 시어도어 루스벨트의 백악관 개보수 기간 동안, 영부인 이디스 루스벨트는 온실 대신 "적절한 식민지 정원"을 조성했다.
밥 레이놀즈
Section: 선수 경력

1969년 9월 19일 필라델피아 필리스와의 경기에서 메이저 리그 데뷔전을 치렀는데, 선발투수로 나서 1+1⁄3이닝 동안 3피안타 3볼넷 6실점(3자책)을 기록한 뒤 강판되었다. 이 경기가 몬트리올 엑스포스 소속으로 치른 유일한 경기였으며, 이후 세인트루이스 카디널스, 밀워키 브루어스, 볼티모어 오리올스, 디트로이트 타이거스, 클리블랜드 인디언스를 거쳤다.

볼티모어 시절이던 1973년 시즌에 42경기에 출전해 111이닝 동안 7승 5패, 9세이브, 평균자책점 1.95, 77탈삼진 등을 기록하며 가장 준수한 성적을 거뒀다. 이듬해인 1974년에도 54경기에 출전해 69+1⁄3이닝을 소화하며 7승 5패, 7세이브, 평균자책점 2.73, 43탈삼진을 기록했다. 또한 두 해 모두 아메리칸 리그 챔피언십 시리즈에도 출전했다.
체포 마실렐라
Section: 구단 경력

2011년 8월 20일, 마실렐라는 마카비 하이파와 한 시즌 동안의 임대 계약을 맺고 스페인 라리가 클럽 헤타페에 합류했다. 그는 헤타페와의 임대 계약이 만료된 후 마카비 하이파로 돌아갔다.

마실렐라는 해외에서 5년을 보낸 후 2012년 중반에 남아프리카 공화국으로 돌아와 카이저 치프스와 계약했다. 그는 2012년 11월, 모로카 스월로스와의 경기에서 3-2로 승리하며 데뷔했다.
다르다니아 왕국

켈트족의 침략으로 마케도니아의 세력이 약화된 이후 다르다니아는 이 지역에서 강성해졌다. 기원전 230년 다르다니아의 일리리아인 왕이던 롱가루스는 파이오니아의 빌라조라를 함락시켰고, 기원전 230~229년 이들은 안티고노스 왕조 마케도니아의 국왕 데메트리오스 2세 아에톨리코스를 격파하였다.

기원전 28년, 마케도니아 속주의 지방총독(proconsul)이던 마르쿠스 리키니우스 크라수스(삼두정치의 수장이던 마르쿠스 리키니우스 크라수스의 손자)는 다키아인과 바스타르나이에 대한 원정 중에 왕국을 공식적으로 합병하였다. 이후 이 지역은 기원전 15년 모이시아 속주로 편입되었다가 기원후 293년에는 다시 다르다니아 속주(Dardania)로 편성되었다.
네스팅 (컴퓨팅)
Section: 프로그래밍에서

중첩된 자료 구조 또한 프로그래밍에서 흔히 볼 수 있다.

함수형 프로그래밍 언어인 리스프에서는 목록 자료 구조와 더 간단한 원자 자료 구조가 존재한다.

단순 목록은 원자만 포함한다.

구조적 프로그래밍 언어에서 네스팅은 제어 구조를 서로 감싸는 것과 관련이 있으며, 일반적으로 소스 코드 내에서 다른 들여쓰기 수준을 통해 표시된다. 이 간단한 베이직 함수에서 볼 수 있다:
네스팅 (컴퓨팅)
Section: 스프레드시트에서

단 하나의 코드 줄에 괄호가 잠재적으로 축적될 수 있기 때문에 편집 및 오류 감지(또는 디버그)가 다소 불편해질 수 있다. 이것이 현대 프로그래밍 환경과 스프레드시트 프로그램이 현재 편집 위치에 해당하는 괄호 쌍을 굵은 글씨로 강조하는 이유이다. 여는 괄호와 닫는 괄호의 (자동) 균형 제어는 괄호 짝 맞추기 검사로 알려져 있다.

당연히 이러한 연결된(또는 더 정확히 말하면: 중첩된) 수식의 수학적 해법을 허용하려면 내부 표현식이 먼저 평가되어야 하며, 내부 함수가 반환하는 결과가 외부 함수의 입력 데이터로 임시로 사용되기 때문에 이 바깥쪽 방향이 필수적이다.
VCDIFF
Section: 구현

Miscellaneous Utility Library 보관됨 2013-02-04 - 웨이백 머신 - C# 구현, 디코딩 전용

CyanDelta - Xdelta3 패치를 사용하여 시아노젠모드 롬을 업데이트한다.

diffable - 자바 구현, 그러나 VCDIFF의 일종의 원본 수정

jvcdiff - VCDIFF의 전체 디코더/인코더 자바 구현

vcdiff-java - 또 다른 VCDIFF 자바 구현
스타일시트 언어

스타일시트 언어(Style sheet language) 또는 스타일 언어는 구조적 문서의 표현을 나타내는 컴퓨터 언어이다. 구조적 문서의 매력적인 특징 중 하나는 콘텐츠를 여러 상황에서 재사용하고 다양한 방식으로 표현할 수 있다는 것이다. 다른 스타일시트를 논리적 구조에 첨부하여 다른 표현을 생성할 수 있다.

구조적 문서의 콘텐츠를 표현하려면 색상, 글꼴 및 레이아웃과 같은 스타일 규칙 세트가 적용되어야 한다. 스타일 규칙 모음을 스타일시트라고 한다. 서면 문서 형태의 스타일시트는 편집자와 인쇄인이 표현, 철자 및 구두점의 일관성을 보장하기 위해 오랫동안 사용해 왔다. 전자 출판에서는 스타일시트 언어가 주로 철자 및 구두점보다는 시각적 표현의 맥락에서 사용된다.
스타일시트 언어
Section: 구성 요소

서식 모델

모든 스타일시트 언어는 어떤 종류의 서식 모델을 지원한다. 대부분의 스타일시트 언어는 최종 표현에서 텍스트 및 기타 콘텐츠가 어떻게 배치되는지 자세히 설명하는 시각적 서식 모델을 가지고 있다. 예를 들어, CSS 서식 모델은 블록 수준 요소(그 중 "h1"이 예이다)가 부모 요소의 너비를 채우도록 확장됨을 지정한다. 일부 스타일시트 언어에는 청각 서식 모델도 있다.

값 전파 메커니즘

모든 요소의 모든 속성에 대한 모든 값을 명시적으로 지정하는 것을 피하기 위해 스타일시트 언어에는 값을 자동으로 전파하는 메커니즘이 있다. 값 전파의 주요 이점은 스타일시트가 덜 장황하다는 것이다. 위 예에서는 글꼴 크기만 지정된다. 다른 값은 값 전파 메커니즘을 통해 찾아진다. 상속, 초기값 및 캐스케이딩은 값 전파 메커니즘의 예이다.
변환 언어

매크로 언어는 메타 언어를 자바, C++, 포트란과 같은 특정 고급 프로그래밍 언어나 저수준 어셈블리어로 변환하는 변환 언어의 일종이다.

모델 기반 개발 기술 공간에는 주어진 메타모델을 따르는 모델을 입력으로 받아 다른 메타모델을 따르는 모델을 출력으로 생성하는 모델 변환 언어 (MTL)가 있다. 이러한 언어의 한 예는 OMG 표준인 QVT이다.

스트라테고/XT, TXL, 톰, DMS, ASF+SDF와 같은 프로그램 변환 시스템은 모두 변환 언어를 주요 구성 요소로 포함한다. 이러한 시스템의 변환 언어는 입력 텍스트의 구조(일반적으로 문법)에 대한 선언적 설명에 따라 작동하며, 다양한 형식 언어와 문서에 적용할 수 있게 한다.
LR 파서
Section: 개요

대부분의 LR 파서는 테이블 기반이다. 파서의 프로그램 코드는 모든 문법과 언어에 대해 동일한 간단한 일반 루프이다. 문법과 그 구문적 함의에 대한 지식은 파스 테이블(또는 파싱 테이블)이라고 불리는 불변 데이터 테이블에 인코딩된다. 테이블의 항목은 파서 상태와 미리보기 심볼의 모든 유효한 조합에 대해 시프트할지 또는 리듀스할지(그리고 어떤 문법 규칙에 의해)를 보여준다. 파스 테이블은 또한 현재 상태와 다음 심볼이 주어졌을 때 다음 상태를 계산하는 방법도 알려준다.

파스 테이블은 문법보다 훨씬 크다. LR 테이블은 큰 문법에 대해 손으로 정확하게 계산하기 어렵다. 그래서 비손과 같은 파서 생성기 도구에 의해 문법에서 기계적으로 파생된다.

상태 및 파싱 테이블이 생성되는 방법에 따라 결과 파서는 SLR(Simple LR) 파서, LALR(Look-Ahead LR) 파서 또는 정규 LR 파서라고 불린다. LALR 파서는 SLR 파서보다 더 많은 문법을 처리한다. 정규 LR 파서는 훨씬 더 많은 문법을 처리하지만, 더 많은 상태와 훨씬 더 큰 테이블을 사용한다. 예제 문법은 SLR이다.
LR 파서

LR 파서는 결정론적이다. 즉, 추측이나 퇴각검색 없이 선형 시간 내에 단일의 올바른 파싱 결과를 생성한다. 이는 컴퓨터 언어에 이상적이지만, LR 파서는 더 유연하지만 필연적으로 느린 방법을 필요로 하는 인간 언어에는 적합하지 않다. 임의의 문맥 자유 언어를 파싱할 수 있는 일부 방법(예: 콕-영거-카사미, 얼리, GLR)은 최악의 경우 O(n3) 시간 성능을 보인다. 잘못 추측하면 퇴각검색을 하거나 여러 파싱 결과를 산출하는 다른 방법은 지수 시간을 소요할 수도 있다.

위의 L, R, k 속성은 우선순위 파서를 포함한 모든 시프트-리듀스 파서가 공유한다. 그러나 관례적으로 LR이라는 이름은 도널드 커누스가 발명한 파싱 방식을 의미하며, 초기에는 덜 강력했던 우선순위 방식(예: 연산자 우선순위 파서)은 제외한다.
LR 파서는 우선순위 파서나 하향식 LL 파싱보다 더 넓은 범위의 언어와 문법을 처리할 수 있다. 이는 LR 파서가 발견한 내용을 확정하기 전에 어떤 문법 패턴의 전체 인스턴스를 볼 때까지 기다리기 때문이다. LL 파서는 그 패턴의 가장 왼쪽 입력 심볼만 보았을 때 훨씬 더 일찍 자신이 무엇을 보고 있는지 결정하거나 추측해야 한다.
LR 파서
Section: LR 생성기 분석

LR 이론과 LR 파서가 문법에서 어떻게 파생되는지에 대한 자세한 내용은 "Parsing, Translation, and Compiling, Volume 1 (Aho and Ullman)"을 참조하라.

커누스가 기술한 정규 LR 파서는 너무 많은 상태와 방대한 파스 테이블을 가지고 있어 그 시대의 제한된 컴퓨터 메모리로는 비실용적으로 컸다. LR 파싱은 프랭크 디리머가 훨씬 적은 상태를 가진 SLR 및 LALR 파서를 발명하면서 실용적이 되었다.
파싱 표현 문법
Section: 정의

파싱 표현식 문법은 명명된 파싱 표현식들의 모음으로, 서로를 참조할 수 있다. 파싱 표현식에서 그러한 참조의 효과는 마치 참조된 전체 파싱 표현식이 참조 위치에 주어진 것과 같다. 파싱 표현식 문법은 또한 지정된 시작 표현식을 가진다. 문자열이 시작 표현식과 일치하면 문법과 일치한다.

일치하는 문자열의 요소는 말단 기호 또는 줄여서 단말이라고 한다. 마찬가지로 파싱 표현식에 할당된 이름은 비말단 기호 또는 줄여서 비단말이라고 한다. 이러한 용어는 생성 문법에 설명적이지만, 파싱 표현식 문법의 경우 단순히 파싱 알고리즘에 대한 논의에서 거의 보편적으로 사용되기 때문에 유지되는 용어일 뿐이다.
파싱 표현 문법

CFG와 달리 PEG는 모호할 수 없다. 문자열은 정확히 하나의 유효한 파스 트리를 갖거나 아예 갖지 않는다. PEG로 인식할 수 없는 문맥 자유 언어가 존재한다고 추측되지만, 아직 입증되지 않았다. PEG는 여러 해석 대안을 로컬에서 모호하지 않게 할 수 있는 컴퓨터 언어(및 로지반과 같은 인공 인간 언어)를 구문 분석하는 데 적합하지만, 모호성 해소가 전역적이어야 하는 자연어를 구문 분석하는 데는 덜 유용할 수 있다.

컴퓨터 과학에서 파싱 표현 문법(parsing expression grammar, PEG)은 분석적 형식 문법의 일종으로, 언어 내의 문자열을 인식하기 위한 규칙 집합으로 형식 언어를 설명한다. 이 형식론은 브라이언 포드(Bryan Ford)가 2004년에 도입했으며 1970년대 초에 도입된 하향식 파싱 언어 계열과 밀접한 관련이 있다.
구문적으로 PEG는 문맥 자유 문법(CFG)과도 유사하지만 해석이 다르다. PEG에서는 선택 연산자가 첫 번째 일치 항목을 선택하는 반면, CFG에서는 모호할 수 있다. 이는 재귀 하향 파서와 같이 문자열 인식이 실제에서 수행되는 방식에 더 가깝다.
파싱 표현 문법
Section: 파싱 표현식 문법으로 파서 구현하기

피카 파서(pika parser)는 동적 계획법을 사용하여 PEG 규칙을 상향식 및 오른쪽에서 왼쪽으로 적용한다. 이는 일반적인 재귀 하향식 및 왼쪽에서 오른쪽 파싱 순서의 역이다. 역순으로 파싱하면 좌측 재귀 문제를 해결하여 좌측 재귀 규칙을 문법에 직접 사용할 수 있도록 하며, 구문 분석기에 최적의 오류 복구 기능을 부여한다. 이는 역사적으로 재귀 하향 파서에게 달성하기 어려웠던 것이다.

LL 파서 및 LR 파서도 파싱 표현식 문법에서 구축할 수 있으며, 메모이제이션 없는 재귀 하향 파서보다 최악의 경우 성능이 더 좋다. 그러나 문법 형식론의 무제한 미리보기 기능은 이때 손실된다. 따라서 파싱 표현식 문법을 사용하여 표현할 수 있는 모든 언어가 LL 또는 LR 파서로 파싱될 수 있는 것은 아니다.
온 더 플라이
Section: 컴퓨터 용법

컴퓨터는 온 더 플라이로 결과를 계산하거나 이전에 저장된 결과를 검색할 수 있다.

이는 이동식 미디어(CD-ROM, DVD 등)를 중간 매체(하드 디스크)에 먼저 저장하지 않고 직접 복사하는 것을 의미할 수 있다. 예를 들어, CD-ROM 드라이브에서 CD-라이터 드라이브로 CD-ROM을 복사하는 것이다. 복사 프로세스는 각 데이터 블록을 검색하고 즉시 대상으로 기록하여 작업 메모리에 다음 데이터 블록을 검색할 공간을 확보해야 한다.

멀티태스킹 컴퓨팅에서 운영 체제는 여러 프로그램을 처리할 수 있다. 네이티브 애플리케이션이든 에뮬레이트된 소프트웨어든 모두 같은 장치에서 동시에 독립적으로, 병렬로 실행되며, 분리되거나 공유된 리소스 및 데이터를 사용하여 작업을 개별적으로 또는 함께 수행한다. 사용자는 시간 낭비나 성능 저하 없이 이러한 프로그램이나 그룹 간에 온 더 플라이로 전환하여 얻은 효과를 사용하거나 목적을 감독할 수 있다. GUI를 사용하는 운영 체제에서는 특정 소프트웨어의 활성 창(또는 유사한 역할을 하는 객체)에서 다른 소프트웨어의 다른 창으로 전환하여 이 작업을 수행하는 경우가 매우 많다.
2-3 트리
Section: 연산

2–3 트리에서 항목을 탐색하는 것은 이진 탐색 트리에서 항목을 탐색하는 것과 유사하다. 각 노드의 데이터 요소가 정렬되어 있으므로, 탐색 함수는 올바른 서브트리와 결국 항목을 포함하는 올바른 노드로 향하게 된다.

T를 2–3 트리로, d를 찾고자 하는 데이터 요소로 둔다. T가 비어 있으면 d는 T에 없고 탐색이 완료된다.

t를 T의 루트로 둔다.

t가 리프라고 가정한다.
만약 d가 t에 없으면 d는 T에 없다. 그렇지 않으면 d는 T에 있다. 더 이상의 단계는 필요 없으며 탐색이 완료된다.
2-3 트리
Section: 정의

T가 데이터 요소 a와 b를 가진 3-노드이며, a  < b이다. T가 왼쪽 자식 p, 중간 자식 q, 오른쪽 자식 r을 가진다면,
p, q, r은 같은 높이의 2–3 트리이다.
a는 p의 각 데이터 요소보다 크고 q의 각 데이터 요소보다 작다.
b는 q의 각 데이터 요소보다 크고 r의 각 데이터 요소보다 작다.

2-노드

3-노드

T가 2–3 트리인 경우는 다음 문장 중 하나만 참일 때이다:

T가 비어 있다. 즉, T에 노드가 없다.

T가 데이터 요소 a를 가진 2-노드이다. T가 왼쪽 자식 p와 오른쪽 자식 q를 가진다면,
p와 q는 같은 높이의 2–3 트리이다.
a는 p의 각 요소보다 크다.
a는 q의 각 데이터 요소보다 작다.
2-3-4 트리
Section: 삭제

제거하려는 리프로 가는 도중에 2-노드(루트 노드 제외)가 발견되면 다음 조정을 수행한다.

이 노드 양쪽의 형제 노드가 3-노드 또는 4-노드인 경우(따라서 1개 이상의 키를 가짐) 해당 형제 노드와 회전을 수행한다.
이 노드에 가장 가까운 다른 형제 노드의 키가 두 노드를 바라보는 부모 키로 올라간다.
부모 키는 이 노드로 내려와 3-노드를 형성한다.
원래 회전된 형제 키와 함께 있던 자식은 이제 이 노드의 추가 자식이 된다.

부모가 2-노드이고 형제 노드도 2-노드인 경우, 세 요소를 모두 결합하여 새 4-노드를 형성하고 트리를 줄인다. (이 규칙은 부모 2-노드가 루트인 경우에만 트리거될 수 있다. 경로상의 다른 모든 2-노드는 2-노드가 아니도록 수정되었을 것이기 때문이다. 이것이 여기서 "트리를 줄인다"는 것이 균형을 유지하는 이유이다. 이것은 또한 합병 작업의 중요한 가정이다.)
2-3-4 트리

2-노드는 하나의 데이터 요소를 가지며, 내부 노드인 경우 두 개의 자식 노드를 가진다.

3-노드는 두 개의 데이터 요소를 가지며, 내부 노드인 경우 세 개의 자식 노드를 가진다.

컴퓨터 과학에서 2–3–4 트리 (또는 2–4 트리)는 사전을 구현하는 데 사용할 수 있는 자가 균형 자료 구조이다. 이 숫자는 자식 노드가 있는 모든 노드 (내부 노드)가 두 개, 세 개 또는 네 개의 자식 노드를 갖는 트리를 의미한다.
2-3-4 트리
Section: 삽입

남은 3-노드 (22, 29)는 두 개의 2-노드 (22)와 (29)로 분할된다. 새 부모 (10, 20, 24)로 다시 올라간다.

가장 오른쪽 자식 (29)으로 내려간다. (해당 간격 (24, ∞)에 25가 포함되어 있다.)

루트 (10, 20)에서 시작하여 가장 오른쪽 자식 (22, 24, 29)으로 내려간다. (해당 간격 (20, ∞)에 25가 포함되어 있다.)

노드 (22, 24, 29)는 4-노드이므로 중간 요소 24가 부모 노드로 올라간다.
스케이프고트 트리
Section: 작업

재균형 작업은  시간(서브트리 노드 수에 따라 달라짐)이 걸리므로, 삽입은 최악의 경우  시간이 걸린다. 그러나 이러한 최악의 시나리오가 분산되어 있으므로 삽입은 의 분할 상환 시간이 걸린다.

노드 v의 불균형(Imbalance)을 왼쪽 노드와 오른쪽 노드의 크기 차이의 절댓값에서 1을 뺀 값 또는 0 중 큰 값으로 정의한다. 다시 말해:

v를 뿌리로 하는 서브트리를 재구성한 직후, I(v) = 0이다.
스케이프고트 트리

대부분의 균형 트리 알고리즘에서 사용되는 작고 점진적인 재균형 작업 대신, 스케이프고트 트리는 드물지만 비용이 많이 드는 "희생양"을 선택하여 희생양을 뿌리로 하는 서브트리를 완전한 이진 트리로 완전히 재구성한다. 따라서 스케이프고트 트리는 최악의 경우 의 갱신 성능을 가진다.

최악의 경우  탐색 시간을 제공하는 다른 대부분의 자가 균형 이진 탐색 트리와 달리, 스케이프고트 트리는 일반적인 이진 탐색 트리에 비해 노드당 추가 메모리 오버헤드가 없다: 키와 값 외에, 노드는 자식 노드에 대한 두 개의 포인터만 저장한다. 이는 스케이프고트 트리를 구현하기 쉽게 만들고, 데이터 구조 정렬 덕분에 노드 오버헤드를 최대 3분의 1까지 줄일 수 있다.
스케이프고트 트리
Section: 이론

여기서 size는 재귀적으로 정의될 수 있다:

심지어 퇴화된 트리(연결 리스트)도 α=1이면 이 조건을 만족하지만, α=0.5이면 거의 완전 이진 트리만 일치한다.

알파-무게 균형 이진 탐색 트리는 또한 알파-높이 균형이어야 한다. 즉,

이진 탐색 트리는 노드의 절반이 루트의 왼쪽에 있고 절반이 오른쪽에 있으면 무게 균형이 잡혀 있다고 말한다.
알파-무게 균형 노드는 완화된 무게 균형 기준을 충족하는 것으로 정의된다:
트립 (자료 구조)
Section: 연산

교집합 알고리즘도 유사하지만, join 도우미 루틴이 필요하다. 합집합, 교집합, 차집합 각각의 복잡성은 크기 m과 n을 가진 트립의 경우 m ≤ n일 때 O(m log ⁠n/m⁠)이다. 또한, 합집합에 대한 재귀 호출은 서로 독립적이므로 병렬로 실행될 수 있다.

여기서 분할은 두 개의 트리를 반환하는 것으로 가정한다: 하나는 입력 키보다 작은 키를 포함하고, 다른 하나는 더 큰 키를 포함한다. (이 알고리즘은 비파괴적이지만, 제자리 파괴적 버전도 존재한다.)
트립 (자료 구조)
Section: 암시적 트립

주어진 범위에서 덧셈, 색칠

주어진 범위에서 요소 뒤집기

암시적 트립의 아이디어는 배열 인덱스를 키로 사용하지만 명시적으로 저장하지 않는 것이다. 그렇지 않으면 업데이트(삽입/삭제)로 인해 트리의  노드에서 키가 변경될 수 있다.

암시적 트립은 일반 트립의 간단한 변형으로,  시간 내에 다음 연산을 지원하는 동적 배열로 볼 수 있다:

어떤 위치에든 요소 삽입

어떤 위치에서든 요소 제거

주어진 범위에서 합계, 최소 또는 최대 요소 찾기
트립 (자료 구조)
Section: 설명

트립은 1989년 라이문트 자이델과 세실리아 R. 아라곤에 의해 처음 기술되었다. 그 이름은 혼성어로 트리와 힙을 합친 것이다.
이는 각 키에 (무작위로 선택된) 숫자 우선순위가 부여된 카르테시안 트리이다. 다른 이진 탐색 트리와 마찬가지로 노드의 중위 순회 순서는 키의 정렬된 순서와 같다. 트리의 구조는 힙 순서를 유지해야 한다는 요구 사항에 의해 결정된다. 즉, 모든 비리프 노드의 우선순위는 자식의 우선순위보다 크거나 같아야 한다. 따라서 일반적으로 카르테시안 트리와 마찬가지로 루트 노드는 최대 우선순위 노드이며, 왼쪽 및 오른쪽 서브트리는 해당 노드의 왼쪽과 오른쪽에 있는 정렬된 순서의 서브시퀀스에서 동일한 방식으로 형성된다.

트립을 설명하는 동등한 방법은 가장 높은 우선순위부터 노드를 이진 탐색 트리에 삽입하여 재조정 없이 형성될 수 있다는 것이다. 따라서 우선순위가 독립적인 무작위 숫자(두 노드가 동일한 우선순위를 가질 가능성이 거의 없도록 충분히 큰 우선순위 공간에서 분포된)라면 트립의 모양은 무작위 이진 탐색 트리의 모양과 동일한 확률 분포를 갖는다. 무작위 이진 탐색 트리는 무작위로 선택된 삽입 순서로 재조정 없이 노드를 삽입하여 형성된 탐색 트리이다. 무작위 이진 탐색 트리는 높은 확률로 로그 높이를 갖는 것으로 알려져 있으므로 트립도 마찬가지이다. 이는 퀵 정렬의 이진 탐색 트리 논증과 유사하며 퀵 정렬이 예상  시간에 실행된다. 이진 탐색 트리가 정렬의 동적 문제 버전의 해법이라면, 트립은 우선순위가 피벗 선택을 안내하는 동적 퀵 정렬에 특히 해당한다.
판 엠데 보아스 트리
Section: 지원되는 연산

vEB 트리는 또한 Minimum 및 Maximum 연산을 지원하며, 이는 각각 트리에 저장된 최소 및 최대 원소를 반환한다. 최소 및 최대 원소는 각 트리에 속성으로 저장되므로 이 둘 모두  시간에 실행된다.

Delete: 주어진 키를 가진 키/값 쌍 제거

Lookup: 주어진 키와 관련된 값 찾기

FindNext: 주어진 k보다 큰 가장 작은 키를 가진 키/값 쌍 찾기

FindPrevious: 주어진 k보다 작은 가장 큰 키를 가진 키/값 쌍 찾기
판 엠데 보아스 트리
Section: 유사한 구조

x-고속 트라이와 더 복잡한 y-고속 트라이는 vEB 트리와 유사한 업데이트 및 쿼리 시간을 가지며, 무작위 해시 테이블을 사용하여 사용되는 공간을 줄인다. x-고속 트라이는 O(n log M) 공간을 사용하는 반면, y-고속 트라이는 O(n) 공간을 사용한다.

융합 트리는 유한 유니버스에서 w-비트 정수에 대한 연관 배열을 구현하는 또 다른 유형의 트리 자료 구조이다. 이들은 워드 수준 병렬 처리 및 비트 조작 기술을 사용하여 선행자/후속자 쿼리 및 업데이트에 대해 O(logw n) 시간을 달성한다. 여기서 w는 워드 크기이다. 융합 트리는 O(n) 공간을 사용하며 해싱 또는 지수 트리를 사용하여 동적으로 만들 수 있다.
판 엠데 보아스 트리
Section: 기능

위 경우 중 어느 하나라도, 어떤 서브트리 T.children[i]에서 마지막 원소 x 또는 y를 삭제하면 T.aux에서도 i를 삭제한다.

코드:

다시 한번, 이 절차의 효율성은 단 하나의 원소만 포함하는 vEB 트리에서 삭제하는 데 상수 시간만 걸린다는 사실에 달려 있다. 특히, 두 번째 Delete 호출은 삭제 이전에 x가 T.children[i]에 유일한 원소였을 때만 실행된다.

만약 x≠T.min 및 x≠T.max이면 x를 포함하는 서브트리 T.children[i]에서 x를 삭제한다.

만약 x == T.max이면 vEB 트리에서 두 번째로 큰 값 y를 찾아 T.max=y로 설정해야 한다. 이전 경우와 같이 x를 삭제하는 것부터 시작한다. 그러면 값 y는 T.min이거나 T.children[T.aux.max].max이므로 O(1) 시간에 찾을 수 있다.
기수 트리
Section: 다른 자료 구조와의 비교

그러나 기수 트리는 트라이의 단점도 공유한다. 요소 문자열 또는 문자열로 효율적으로 가역적으로 매핑되는 요소에만 적용될 수 있으므로, 전순서를 가진 모든 데이터 형식에 적용되는 균형 탐색 트리의 완전한 일반성이 부족하다. 문자열로의 가역 매핑은 균형 탐색 트리에 필요한 전순서를 생성하는 데 사용될 수 있지만, 그 반대는 불가능하다. 이는 데이터 형식이 비교 연산만 제공하고 (역)직렬화 연산은 제공하지 않는 경우에도 문제가 될 수 있다.

해시 테이블은 일반적으로 예상 O(1) 삽입 및 삭제 시간을 갖는다고 하지만, 이는 키의 해시 계산을 상수 시간 연산으로 간주할 때만 해당된다. 키 해싱을 고려하면 해시 테이블은 예상 O(k) 삽입 및 삭제 시간을 가지지만, 충돌 처리 방식에 따라 최악의 경우 더 오래 걸릴 수 있다. 기수 트리는 최악의 경우 O(k) 삽입 및 삭제를 갖는다. 기수 트리의 후행/선행 연산은 해시 테이블에서 구현되지 않는다.
기수 트리

컴퓨터 과학에서 기수 트리, 래딕스 트리(radix tree) 또는 기수 트라이(radix trie) 또는 압축 접두사 트리(compact prefix tree) 또는 압축 트라이(compressed trie)는 유일한 자식인 각 노드가 부모와 병합되는 공간 최적화된 트라이 (접두사 트리)를 나타내는 자료 구조이다. 그 결과 모든 내부 노드의 자식 수는 기수 트리의 기수 r 이하이며, 여기서 r = 2x (일부 정수 x ≥ 1). 일반 트리와 달리 엣지는 단일 요소뿐만 아니라 요소 시퀀스로도 레이블을 지정할 수 있다. 이로 인해 기수 트리는 작은 집합 (특히 문자열이 긴 경우) 및 긴 접두사를 공유하는 문자열 집합에 훨씬 더 효율적이다.

일반 트리(전체 키가 불일치 지점까지 시작부터 한꺼번에 비교됨)와 달리, 각 노드의 키는 비트 덩어리별로 비교되며, 해당 노드의 해당 덩어리에 있는 비트의 양은 기수 트라이의 기수 r이다. r이 2일 때, 기수 트라이는 이진(즉, 해당 노드의 키의 1비트 부분을 비교)이며, 이는 트라이 깊이를 최대화하는 대신 희소성을 최소화한다. 즉, 키에서 분기하지 않는 비트 문자열의 혼동까지 최대화한다. r ≥ 4가 2의 거듭제곱일 때, 기수 트라이는 r-진 트라이이며, 이는 잠재적 희소성을 희생하여 기수 트라이의 깊이를 줄인다.
기수 트리
Section: 변형

일반적인 관행은 부모가 데이터 집합에서 유효한 키를 나타내는 상황에서 자식이 하나만 있는 부모를 허용하지 않는 기준을 완화하는 것이다. 이 변형 기수 트리는 적어도 두 개 이상의 자식을 가진 내부 노드만 허용하는 것보다 더 높은 공간 효율성을 달성한다.

HAT-트라이는 기수 트리를 기반으로 하는 캐시 인식 자료 구조로, 효율적인 문자열 저장 및 검색, 그리고 순서 있는 반복을 제공한다. 시간과 공간 모두에서 성능은 캐시 인식 해시 테이블과 비교할 만하다.
접미사 트리
Section: 구현

각 노드와 엣지를  공간으로 표현할 수 있다면, 전체 트리는  공간으로 표현될 수 있다. 트리 내 모든 엣지의 모든 문자열 길이의 총합은 이지만, 각 엣지는 S의 부분 문자열의 위치와 길이로 저장될 수 있어 총 공간 사용량은  컴퓨터 워드가 된다. 접미사 트리의 최악의 공간 사용량은 피보나치 워드에서 볼 수 있으며, 전체  노드를 제공한다.

접미사 트리를 구현할 때 중요한 선택은 노드 간의 부모-자식 관계이다. 가장 일반적인 방법은 형제 리스트라고 불리는 연결 리스트를 사용하는 것이다. 각 노드는 첫 번째 자식에 대한 포인터와 자신이 속한 자식 리스트의 다음 노드에 대한 포인터를 가진다. 효율적인 실행 시간 속성을 가진 다른 구현은 해시 맵, 정렬되거나 정렬되지 않은 배열 (배열 두 배 확장과 함께), 또는 균형 탐색 트리를 사용한다. 우리는 다음에 관심이 있다.
접미사 트리
Section: 외부 구성

반면에, (몇) GB/시간으로 확장 가능한 디스크 기반 접미사 트리를 구성하기 위한 실제 작업이 있었다.
최신 방법은 TDD,
TRELLIS,
DiGeST,
및
B2ST이다.

TDD와 TRELLIS는 전체 인간 유전체까지 확장되어 수십 기가바이트 크기의 디스크 기반 접미사 트리를 생성한다. 그러나 이러한 방법은 3GB를 초과하는 시퀀스 컬렉션을 효율적으로 처리할 수 없다. DiGeST는 훨씬 더 나은 성능을 보이며 약 6시간 내에 약 6GB 크기의 시퀀스 컬렉션을 처리할 수 있다.

접미사 트리의 메모리 사용량은 선형적이지만 실제 시퀀스 컬렉션의 크기보다 상당히 크다. 큰 텍스트의 경우 구성에 외부 메모리 접근 방식이 필요할 수 있다.

외부 메모리에서 접미사 트리를 구성하는 이론적 결과가 있다.
Farach-Colton, Ferragina & Muthukrishnan (2000)의 알고리즘은 정렬과 동일한 I/O 복잡도를 가지므로 이론적으로 최적이다.
그러나 이 알고리즘의 전체적인 복잡성으로 인해 지금까지 실용적인 구현이 이루어지지 못했다.
접미사 트리
Section: 기능

모든 개의 tandem repeat를  시간 내에 찾고, k-불일치 tandem repeat를  시간 내에 찾는다.

에 대해 의 최소 개 문자열에 대한 최장 공통 부분 문자열을  시간 내에 찾는다.

길이 인 패턴 P를 최대 개의 불일치를 허용하며  시간 내에 검색한다. 여기서 z는 일치하는 횟수이다.

모든 개의 최대 회문을  시간 내에 찾거나,  길이의 간격이 허용되는 경우  시간 내에, 또는 개의 불일치가 허용되는 경우  시간 내에 찾는다.
쿼드트리
Section: 유형

다각형 맵 쿼드트리(또는 PM 쿼드트리)는 퇴화될 수 있는 (즉, 고립된 정점이나 가장자리를 가질 수 있는) 다각형 컬렉션을 저장하는 데 사용되는 쿼드트리의 변형이다.
 PM 쿼드트리와 가장자리 쿼드트리 사이의 큰 차이점은 고려 중인 셀이 셀 내의 정점에서 세그먼트가 만나는 경우에도 세분화되지 않는다는 것이다.

가장자리 쿼드트리(PM 쿼드트리와 매우 유사하게)는 점 대신 선을 저장하는 데 사용된다. 곡선은 셀당 하나의 선분만 남을 때까지 매우 세밀하게 셀을 세분화하여 근사화된다. 모서리/정점 근처에서 가장자리 쿼드트리는 최대 분해 수준에 도달할 때까지 계속 분할한다. 이로 인해 극도로 불균형한 트리가 생성되어 인덱싱 목적을 상실할 수 있다.
쿼드트리

모든 형태의 쿼드트리는 몇 가지 공통적인 특징을 공유한다.

공간을 적응 가능한 셀로 분해한다.

각 셀(또는 버킷)은 최대 용량을 가진다. 최대 용량에 도달하면 버킷이 분할된다.

분할된 영역은 정사각형 또는 직사각형일 수 있으며, 임의의 모양을 가질 수도 있다. 이 자료 구조는 1974년 라파엘 핀켈과 J.L. 벤틀리에 의해 쿼드트리라고 명명되었다. 유사한 분할은 Q-트리라고도 알려져 있다.
쿼드트리
Section: 쿼드트리를 이용한 이미지 처리

논의를 단순화하기 위해 쿼드트리 노드의 자식이 Z-차순 (SW, NW, SE, NE)을 따른다고 가정하자. 이 구조를 믿을 수 있기 때문에, 어떤 셀에 대해서도 계층 구조의 다른 수준에서 인접한 셀을 찾기 위해 쿼드트리를 탐색하는 방법을 안다.

알고리즘은 세 단계로 작동한다.

검은색 픽셀 간의 인접 관계를 설정한다.

첫 번째 단계의 동등 관계를 처리하여 각 연결 성분에 대해 고유한 레이블을 얻는다.

검은색 픽셀에 해당 연결 성분과 연결된 레이블을 지정한다.
펜윅 트리

이 구조는 1989년 보리스 랴프코가 제안했으며 1992년에 추가 수정이 발표되었다. 이후 피터 펜윅이 1994년 논문에서 이 구조를 설명한 후 펜윅 트리라는 이름으로 알려지게 되었다.

값의 단순 배열은 업데이트하기 쉽지만(상수 시간) 누적 합을 계산하거나 접두사 길이를 검색하는 데는  시간이 필요하다.

누적 합 배열은 상수 시간에 누적 합을 반환하고,  시간에 접두사 길이를 검색할 수 있지만, 값 중 하나를 업데이트하는 데는  시간이 필요하다.
펜윅 트리
Section: 동기

값의 배열이 주어졌을 때, 때로는 특정 결합적이항 연산 (정수의 덧셈이 가장 흔함)에 따라 각 인덱스까지의 값의 누적 합을 계산하는 것이 바람직하다. 펜윅 트리는 기본 값 배열의 변경을 허용하고 모든 후속 쿼리가 이러한 변경을 반영하도록 하면서, 어떤 인덱스에서든 누적 합 또는 접두사 합을 쿼리하는 방법을 제공한다.

펜윅 트리는 적응형 산술 부호화를 구현하는 데 특별히 고안되었는데, 이는 생성된 각 심볼의 수를 유지하고 이를 주어진 심볼보다 작은 심볼의 누적 확률로 변환해야 한다. 지원하는 연산의 개발은 주로 이 경우의 사용에 동기가 부여되었다.
펜윅 트리
Section: 설명

노드 는 개의 자식()을 가지며, 총 개의 자손을 가진다. (이 숫자에는 보다 큰 노드가 포함되며, 이 노드들은 생략되고 액세스되지 않는다.)

아래 다이어그램은 16개 노드 펜윅 트리의 쿼리 트리의 구조를 보여주며, 루트를 포함하므로 15개 요소 배열 A에 해당한다:

쿼리 트리는 노드 의 부모가 가 되도록 정의된다. 예를 들어, 6 = 1102의 부모는 4 = 1002이다. 암시적 노드 0은 루트이다.

트리의 각 레벨 는 개의 고유한 2의 거듭제곱 합에 해당하는 인덱스를 가진 노드를 포함한다(은 빈 합 0을 나타냄). 예를 들어, 레벨 은 노드 를 포함하고 레벨 는 노드 를 포함한다.
다항 위계
Section: 정의

다항 위계의 클래스에 대한 여러 동등한 정의가 있다.

다항 위계의 신탁 정의를 위해 다음을 정의한다.

여기서 P는 다항 시간 내에 해결 가능한 결정 문제들의 집합이다. 그런 다음 i ≥ 0에 대해 다음을 정의한다.

여기서 는 클래스 A의 어떤 완전 문제에 대한 신탁에 의해 다항 시간에 해결 가능한 결정 문제들의 집합이다. 클래스  및 는 유사하게 정의된다. 예를 들어,  이고 는 어떤 NP-완전 문제에 대한 오라클을 가진 결정적 튜링 기계로 다항 시간 안에 해결 가능한 문제들의 클래스이다.
다항 위계
Section: 다른 클래스와의 관계

다항 위계에 완전 문제가 있다면, 그것은 유한하게 많은 고유한 수준만을 가진다. PSPACE-완전 문제가 존재하므로, PSPACE = PH라면 다항 위계는 붕괴해야 한다. 왜냐하면 PSPACE-완전 문제는 어떤 k에 대한 -완전 문제가 될 것이기 때문이다.

다항 위계는 지수 위계와 산술적 위계의 아날로그(훨씬 낮은 복잡도에서)이다.

PH는 PSPACE 내에 포함되어 있지만, 두 클래스가 같은지는 알려져 있지 않다. 이 문제의 유용한 재정식화는 PH = PSPACE인 경우에만 유한 구조에 대한 2차 논리가 관계에 대한 관계(즉, 2차 변수에 대한) 전이 폐포 연산자의 추가로 추가적인 능력을 얻지 못한다는 것이다.
다항 위계

위계 내의 클래스는 수량자 순서에 대한 제한이 있는 공식에 대해 정량화 부울 공식이 참인지 묻는 완전한 문제(다항 시간 환원과 관련하여)를 가진다. 위계에서 동일한 수준 또는 연속적인 수준의 클래스 간의 등식은 해당 수준으로 위계가 "붕괴"함을 의미한다는 것이 알려져 있다.

계산 복잡도 이론에서 다항 위계(Polynomial hierarchy), 다항 시간 위계는 NP 및 Co-NP 클래스를 일반화하는 위계적인 복잡도 종류이다. 위계의 각 클래스는 PSPACE 내에 포함된다. 이 위계는 신탁 기계 또는 교대 튜링 기계를 사용하여 정의할 수 있다. 이는 수리 논리학의 산술적 위계 및 해석적 위계에 대한 자원 제약적 대응물이다. 위계 내 클래스의 합집합은 PH로 표기된다.
PP (복잡도)

결정 문제가 PP에 속한다면, 확률적 결정을 내릴 수 있는 다항 시간 실행 알고리즘이 존재하며, 이 알고리즘은 1/2보다 높은 확률로 올바른 답을 반환한다. 좀 더 실용적인 용어로 설명하면, 이 종류는 무작위 다항 시간 알고리즘을 충분한(그러나 유한한) 횟수만큼 실행함으로써 어떤 고정된 정확도까지 해결할 수 있는 문제들의 종류이다.

복잡도 이론에서 PP 또는 PPT는 모든 인스턴스에 대해 오차 확률이 1/2 미만으로 다항 시간에 확률적 튜링 기계로 해결 가능한 결정 문제의 종류이다. 약어 PP는 확률적 다항 시간을 의미한다. 이 복잡도 종류는 길(Gill)이 1977년에 정의했다.
PP (복잡도)
Section: 정의

M은 모든 입력에 대해 다항 시간으로 실행된다.

L에 있는 모든 x에 대해 M(x,y) = 1을 만족하는 길이 p(|x|)의 문자열 y의 비율이 1/2보다 크다.

L에 없는 모든 x에 대해 M(x,y) = 1을 만족하는 길이 p(|x|)의 문자열 y의 비율이 1/2보다 작다.

이 정의에서 문자열 y는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 결과에 해당한다.

두 정의 모두에서, "미만"은 "이하"로 변경될 수 있고(아래 참조), 임계값 1/2은 (0,1) 범위의 어떤 고정된 유리수로 대체될 수 있으며, 이는 종류를 변경하지 않는다.
PP (복잡도)
Section: PP 대 BPP

더 일반적으로, c가 입력 크기 에 다항적으로, 즉 와 같이 의존할 수 있다면, 알고리즘을 번 재실행하고 다수결을 취할 수 있다. 호프딩 부등식에 의해, 이는 우리에게 BPP 알고리즘을 제공한다.

중요한 점은 이 상수 c가 입력에 의존하도록 허용되지 않는다는 것이다. 반면에, PP 알고리즘은 다음과 같은 작업을 수행할 수 있다.

YES 인스턴스의 경우, 입력 길이 n에 대해 1/2 + 1/2n의 확률로 YES를 출력한다.
NEXPTIME

모든 x와 y에 대해, 기계 M은 입력 에 대해  시간 내에 실행된다.

L에 속하는 모든 x에 대해, 길이 의 문자열 y가 존재하여 을 만족한다.

L에 속하지 않는 모든 x와 길이 의 모든 문자열 y에 대해, 을 만족한다.

우리는 다음을 알고 있다.

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

또한, 시간 위계 정리에 의해 다음을 알 수 있다.

NP ⊊ NEXPTIME

만약 P = NP라면, NEXPTIME = EXPTIME (패딩 논증); 더 정확히는, E ≠ NE일 때에만 P에 속하지 않는 희소 언어가 NP에 존재한다.
NEXPTIME
Section: 다른 특성화

이 두 가지 확장은 함께 증명 시스템의 능력을 크게 확장하여 NEXPTIME의 모든 언어를 인식할 수 있게 한다. 이 클래스는 PCP(poly, poly)라고 불린다. 더 나아가, 이 특성화에서 검증자는 단지 상수 비트만 읽도록 제한될 수 있다. 즉, NEXPTIME = PCP(poly, 1)이다. 자세한 내용은 확률적으로 검사 가능한 증명을 참조하라.

검증 기계에 무작위성, 즉 동전을 던질 수 있는 능력을 추가한다.

증거를 테이프에 검증자에게 단순히 주는 대신, 증거에 대한 무작위 접근을 제공한다. 검증자는 증거 문자열의 인덱스를 지정하고 해당 비트를 받을 수 있다. 검증자가 다항 길이의 인덱스를 쓸 수 있기 때문에, 지수적으로 긴 증명 문자열을 인덱싱할 수 있다.
DTIME
Section: 기계 모델

P와 같은 견고한 종류의 경우, DTIME을 정의하는 데 사용되는 정확한 기계 모델은 자원의 성능에 영향을 주지 않으면서 변경될 수 있다. 계산 복잡성 문헌은 특히 매우 작은 시간 종류를 논의할 때 다중 테이프 튜링 기계를 기반으로 DTIME을 정의하는 경우가 많다. 다중 테이프 결정론적 튜링 기계는 단일 테이프 기계보다 2차 시간 가속을 제공할 수 없다.

튜링 기계의 선형 속도 향상 정리 때문에, 시간 경계의 곱셈 상수는 DTIME 종류의 범위에 영향을 주지 않는다; 유한 상태 제어의 상태 수를 늘리고 테이프 알파벳의 크기를 늘림으로써 항상 상수 곱셈 속도 향상을 얻을 수 있다. 파파디미트리우의 진술에서, 언어 L에 대해,
DTIME
Section: DTIME의 복잡도 종류

DTIME은 시간 계층 정리를 만족하며, 이는 점근적으로 더 많은 양의 시간이 항상 엄격하게 더 큰 문제 집합을 생성한다는 것을 의미한다.

잘 알려진 복잡도 종류 P는 다항식 시간 DTIME으로 해결할 수 있는 모든 문제를 포함한다. 이는 공식적으로 다음과 같이 정의할 수 있다.

P는 선형 시간 문제 를 포함하는 가장 작은 견고한 종류이다 (AMS 2004, Lecture 2.2, pg. 20). P는 "계산적으로 실현 가능한" 것으로 간주되는 가장 큰 복잡도 종류 중 하나이다.
DTIME

DTIME 자원은 특정 양의 연산 시간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 입력 크기 n의 문제가 으로 해결될 수 있다면, 복잡도 종류  (또는 )를 가진다. 사용되는 메모리 공간의 양에는 제한이 없지만, 다른 복잡성 자원(예: 교대)에는 제한이 있을 수 있다.

계산 복잡도 이론에서 DTIME 또는 TIME은 결정론적 튜링 기계의 연산 시간 연산 자원이다. 이는 "일반적인" 물리 컴퓨터가 특정 알고리즘을 사용하여 특정 계산 문제를 해결하는 데 걸리는 시간(또는 계산 단계 수)을 나타낸다. 이는 중요한 실제 자원(컴퓨터가 문제를 해결하는 데 걸리는 시간)과 매우 밀접하게 관련되어 있기 때문에 가장 잘 연구된 복잡성 자원 중 하나이다.
NTIME
Section: 다른 복잡도 종류와의 관계

잘 알려진 복잡도 종류인 NP는 NTIME을 사용하여 다음과 같이 정의할 수 있다:

마찬가지로, 종류 NEXP는 NTIME을 사용하여 다음과 같이 정의된다:

비결정론적 시간 위계 정리는 비결정론적 기계가 점근적으로 더 많은 시간에 더 많은 문제를 해결할 수 있다고 말한다.

NTIME은 다음 방식으로 DSPACE와도 관련이 있다. 모든 시간 구성 가능 함수 t(n)에 대해 다음이 성립한다:

.

NTIME의 일반화는 교대 튜링 기계로 정의되는 ATIME이다. 다음이 성립하는 것으로 밝혀졌다:
NSPACE
Section: 다른 복잡도 종류와의 관계

언어 L이 비결정적 TM에 의해 공간 S(n) (여기서 S(n) ≥ log n)에서 결정된다면, L이 결정적 TM에 의해 시간 O(CS(n))에서 결정되도록 하는 상수 C가 존재한다.

NSPACE는 결정적 튜링 기계의 메모리 공간 종류인 DSPACE의 비결정적 대응물이다. 정의에 따라, 그리고 새비치 정리에 따라, 우리는 다음을 가진다.

NSPACE는 다음 정리를 통해 결정적 튜링 기계의 시간 복잡도를 결정하는 데에도 사용될 수 있다.
NSPACE
Section: 복잡도 종류

몇 가지 중요한 복잡도 종류는 NSPACE로 정의할 수 있다. 다음이 포함된다.

REG = DSPACE(O(1)) = NSPACE(O(1)), 여기서 REG는 정규 언어의 종류이다(비결정성은 상수 공간에서 능력을 추가하지 않는다).

NL = NSPACE(O(log n))

CSL = NSPACE(O(n)), 여기서 CSL은 문맥 의존 언어의 종류이다.

PSPACE = NPSPACE =

EXPSPACE = NEXPSPACE =