scientific article; zbMATH DE number 4117838
[For the entire collection see Zbl 0681.00016.] Decision trees and random access machines with the set of arithmetic operations \(\{+,-,*,/,<,\lfloor \rfloor \}\) are considered as computing models for algebraic computations. A lower bound proof technique is developed in order to show the \(\Omega\) ((log n)\({}^{1/2})\) lower bound (for both types of the computing models considered) for deciding whether an n-bit integer is a perfect square. This result is a valuable contribution to lower bound techniques, and the technique introduced here can be also used to establish lower bounds for some other computing problems.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4732103)