Element distinctness problem: Difference between revisions

Revision as of 12:07, 6 June 2023

Revision as of 04:01, 9 June 2023

Line 17:

==Real RAM Complexity==

If the elements in the problem are [[real number|real numbers]], the decision-tree lower bound extends to the [[real RAM|real random-access machine]] model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering ("floor").<ref>{{citation|doi=10.1137/S0097539797329397|title=Topological Lower Bounds on Algebraic Random Access Machines|year=2001|last1=Ben-Amram|first1=Amir M.|journal=SIAM Journal on Computing|volume=31|issue=3|pages=722-761|last2=Galil|first2=Zvi|author2-link=Zvi Galil}}.</ref>. This model covers more algorithms than the algebraic decision-tree model, as it encompasses algorithms that use indexing into tables. However, in this model all program steps are counted, not just decisions.

==Turing Machine complexity==