트랜스디코토머스 모형

Transdichotomous model

계산 복잡성 이론에서, 그리고 좀 더 구체적으로 정수 데이터를 이용한 알고리즘 분석에서, 트랜디코토머스 모델은 기계 워드 크기가 문제 크기와 일치한다고 가정하는 임의 액세스 기계의 변형이다. 이 모델은 마이클 프레드먼과 댄 윌러드가 제안한 것으로,[1] 그는 "기계 모델과 문제 크기의 이분법이 합리적으로 교차하기 때문에"[2] 그 이름을 선택했다.

정렬할 정수가 n개 있는 정수 정렬과 같은 문제에서, 트랜스 디코토머스 모델은 각 정수를 컴퓨터 메모리의 한 단어에 저장할 수 있으며, 단일 단어에 대한 연산은 조작당 일정한 시간이 소요되며, 단일 단어에 저장할 수 있는 비트 수는 최소한 logn이라고2 가정한다. 이 모델에서 복잡도 분석의 목적은 입력 값이나 기계 단어의 실제 크기가 아닌 n에만 의존하는 시간 범위를 찾는 것이다.[3][4] 정수 연산 모델링에서는 기계어의 크기가 제한되어 있다고 가정할 필요가 있는데, 이는 무제한 정밀도의 모델은 불합리하게 강력하기 때문이다(다항식 시간 내에 PSPACE-완전 문제를 해결할 수 있음).[5] 트랜디코토머스 모델은 이러한 유형을 최소로 가정한다. 즉, 일부 한계가 있으며, 입력 데이터에 대한 랜덤 액세스 인덱싱을 허용할 수 있을 정도로 한도가 크다는 것이다.[3]

정수 정렬에 대한 그것의 적용뿐만 아니라, 트랜디코토머스 모델은 우선 순위[6] 큐의 설계와 계산 기하학[3] 및 그래프 알고리즘의 문제에도 적용되었다.[7]

참고 항목

참조

  1. ^ Fredman, Michael L.; Willard, Dan E. (1993), "Surpassing the information-theoretic bound with fusion trees", Journal of Computer and System Sciences, 47 (3): 424–436, doi:10.1016/0022-0000(93)90040-4, MR 1248864.
  2. ^ Benoit, David; Demaine, Erik D.; Munro, J. Ian; Raman, Venkatesh, "Representing trees of higher degree", Algorithms and Data Structures: 6th International Workshop, WADS'99, p. 170.
  3. ^ a b c Chan, Timothy M.; Pǎtraşcu, Mihai (2009), "Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time" (PDF), SIAM Journal on Computing, 39 (2): 703–729, doi:10.1137/07068669X.
  4. ^ Chan, Timothy M.; Pǎtraşcu, Mihai (2010), Transdichotomous Results in Computational Geometry, II: Offline Search, arXiv:1010.1948, Bibcode:2010arXiv1010.1948C.
  5. ^ Bertoni, Alberto; Mauri, Giancarlo; Sabadini, Nicoletta (1981), "A characterization of the class of functions computable in polynomial time on Random Access Machines", Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC '81), pp. 168–176, doi:10.1145/800076.802470.
  6. ^ Raman, Rajeev, "Priority Queues: Small, Monotone and Trans-dichotomous", Proceedings of the Fourth Annual European Symposium on Algorithms (ESA '96), Lecture Notes in Computer Science, vol. 1136, Springer-Verlag, pp. 121–137, doi:10.1007/3-540-61680-2_51.
  7. ^ Fredman, Michael L.; Willard, Dan E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9.


P ≟ NP

이 이론적인 컴퓨터 과학 관련 기사는 단조롭다. 위키피디아를 확장하여 도울 수 있다.