요소 고유성 문제

Element distinctness problem

계산 복잡도 이론에서 요소 구별성 문제 또는 요소 고유성 문제는 목록의 모든 요소가 구별되는지를 결정하는 문제입니다.

이것은 많은 다른 계산 모델에서 잘 연구된 문제이다.이 문제는 목록을 정렬한 후 동일한 요소가 연속적으로 존재하는지 확인하는 것으로 해결할 수 있습니다.또한 각 항목을 해시 테이블에 삽입하고 동일한 해시 테이블 [1]셀에 배치된 요소만 비교하는 랜덤화 알고리즘에 의해 선형 예상 시간 내에 해결할 수도 있습니다.

계산 복잡성의 몇 가지 하한을 문제의 문제에 대한 요소 구별성 문제를 줄임으로써, 즉, 문제의 문제를 해결한 후에 요소 고유성 문제의 해결책을 빠르게 찾을 수 있다는 것을 입증함으로써 증명한다.

의사결정 트리의 복잡성

이 보고서는 시간 복잡도에, 숫자 목록에 문제의 시간 복잡도, 즉, Θ(nlogn)은 상단 그리고 더 낮은 경계를linearithmic 기능의 주문을 계산하는 원소들은 컴퓨터의 기억을 인덱싱 하는 데(이로 사용될 수 없computation,[2]모델의 대수적 결정 트리 모델에 있는 것으로 알려졌다.ht가능한 해법)이지만 값의 간단한 대수함수를 계산하고 비교해야만 접근할 수 있다.즉, 이 모델에 대해 선형 광학적 시간 복잡도의 점근적 최적 알고리즘이 알려져 있다.대수 계산 트리 모델은 기본적으로 허용 알고리즘이 입력 데이터와 이러한 계산 결과의 비교에 대해 제한된 정도의 다항 연산을 수행할 수 있는 알고리즘이라는 것을 의미합니다.

동일한 하한이 랜덤화된 대수적 의사결정 트리 [3][4]모델에 대해 나중에 증명되었다.

양자 복잡도

또한 양자 알고리즘은 ( 2/){개의 쿼리에서 이 문제를 보다 빠르게 해결할 수 있는 것으로 알려져 있습니다.최적의 알고리즘은 Andris Ambainis의 [5]것입니다.Yaoyun Shi는 처음에 범위의 크기가 충분히 [6]클 때 엄격한 하한을 증명했습니다.Ambainis와[7] Kutin은[8] 독립적으로(그리고 다른 증거를 통해) 모든 기능의 하한을 얻기 위해 작업을 확장했습니다.

일반화:반복 요소 찾기

크기가 n인 멀티셋에서 n/k회 이상 발생하는 요소는 시간 O(n log k)에서 찾을 수 있습니다.요소 구별성 문제는 k=n의 특수한 경우입니다.이 알고리즘은 [9]계산의 의사결정 트리 모델 하에서 최적입니다.

이 알고리즘은 다소 복잡한 [10]출판 역사를 가진 k=2(보이어-무어 다수결 알고리즘)의 특수한 경우에 대한 알고리즘의 일반화이다.

위의 알고리즘은 요소의 식별 테스트에만 의존합니다.정렬이 허용되는 경우 이전에 알려진 순서 통계 검색 알고리즘을 사용할 수 있습니다.예를 들어 k=2의 경우 먼저 선형 시간에서 중위수를 찾은 다음 n/2개 이상의 중위수 원소가 있는지 여부를 쉽게 검정할 수 있습니다.단, 위의 알고리즘은 순서 [10]통계 알고리즘보다 비교가 적게 필요합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 를 클릭합니다Gil, J.; Meyer auf der Heide, F.; Wigderson, A. (1990), "Not all keys can be hashed in constant time", Proc. 22nd ACM Symposium on Theory of Computing, pp. 244–253, doi:10.1145/100216.100247.
  2. ^ 를 클릭합니다Ben-Or, Michael (1983), "Lower bounds for algebraic computation trees", Proc. 15th ACM Symposium on Theory of Computing, pp. 80–86, doi:10.1145/800061.808735.
  3. ^ 를 클릭합니다Grigoriev, Dima; Karpinski, Marek; Heide, Friedhelm Meyer; Smolensky, Roman (1996), "A lower bound for randomized algebraic decision trees", Computational Complexity, 6 (4): 357, doi:10.1007/BF01270387.
  4. ^ 를 클릭합니다Grigoriev, Dima (1999), "Complexity lower bounds for randomized computation trees over zero characteristic fields", Computational Complexity, 8 (4): 316–329, doi:10.1007/s000370050002.
  5. ^ Ambainis, Andris (2007), "Quantum walk algorithm for element distinctness", SIAM Journal on Computing, 37 (1): 210–239, arXiv:quant-ph/0311001, doi:10.1137/S0097539705447311
  6. ^ Shi, Y. (2002). Quantum lower bounds for the collision and the element distinctness problems. Proceedings of the 43rd Symposium on Foundations of Computer Science. pp. 513–519. arXiv:quant-ph/0112086. doi:10.1109/SFCS.2002.1181975.
  7. ^ Ambainis, A. (2005). "Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range". Theory of Computing. 1 (1): 37–46. doi:10.4086/toc.2005.v001a003.
  8. ^ Kutin, S. (2005). "Quantum Lower Bound for the Collision Problem with Small Range". Theory of Computing. 1 (1): 29–36. doi:10.4086/toc.2005.v001a002.
  9. ^ 를 클릭합니다Misra, J.; Gries, D. (1982), "Finding repeated elements", Science of Computer Programming, 2 (2): 143–152, doi:10.1016/0167-6423(82)90012-0, hdl:1813/6345.
  10. ^ a b 를 클릭합니다Boyer, R. S.; Moore, J S. (1991), "MJRTY - A Fast Majority Vote Algorithm", in Boyer, R. S. (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers, pp. 105–117.