Element distinctness problem: Difference between revisions

Revision as of 16:03, 18 October 2010

Revision as of 16:08, 18 October 2010

Line 16:

The same lower bound was later proved for the [[randomized complexity|randomized]] [[algebraic decision tree]] model.<ref>{{cite journal|doi=10.1007/BF01270387|title=A lower bound for randomized algebraic decision trees|year=1996|author=Grigoriev, Dima|journal=Computational Complexity|volume=6|pages=357|last2=Karpinski|first2=Marek|last3=Heide|first3=Friedhelm Meyer|last4=Smolensky|first4=Roman}}</ref>

It is also known that [[quantum algorithm]]s can solve this problem faster in <math>\Theta\left(N^{2/3}\right)</math> queries. The optimal algorithm is by [[Andris Ambainis]],<ref>{{Cite journal | last1=Ambainis | first1=Andris | author1-link=Andris Ambainis | title=Quantum walk algorithm for element distinctness | id = {{arxiv|quant-ph/0311001}} | doi = 10.1137/S0097539705447311 | journal = [[SIAM Journal on Computing]] | volume = 37 | issue = 1 | year = 2007 | pages=210–239 | postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->[[Category:Articles with inconsistent citation formats]] }}.</ref> and the lower bound is due to [[Scott Aaronson]] and Yaoyun Shi.<ref>{{Cite journal | last1=Aaronson | first1=S. | last2=Shi | first2=Y. | title=Quantum lower bounds for the collision and the element distinctness problems | publisher=Association for Computing Machinery, Inc, One Astor Plaza, 1515 Broadway, New York, NY, 10036-5701, USA, | year=2004 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=51 | issue=4 | pages=595–605 | doi=10.1145/1008731.1008735 | postscript=<!--None-->}}</ref>

Several lower bounds in computational complexity are proved by reducing the element distinctness problem to the problem in question, i.e., by demonstrating that the solution of the element uniqueness problem may be quickly found after solving the problem in question.