The recognition problem for the set of perfect squares
- 1 October 1966
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 78-87
- https://doi.org/10.1109/swat.1966.30
Abstract
Lower bounds on the capacity and on the product of capacity and computation time are obtained for machines which recognize the set of squares. The bound on capacity is approached to within a factor of four by a specific machine which carries out a test based on the fact that every non-square is a quadratic non-residue of some rational prime. A machine which carries out a test based on the standard root-extraction algorithm is substantially less efficient in this respect. For neither machine is the bound on the capacity-time product closely approached.Keywords
This publication has 4 references indexed in Scilit:
- ON THE LEAST PRIMITIVE ROOT OF A PRIMEPublished by World Scientific Pub Co Pte Ltd ,2005
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Crossing sequences and off-line turing machine computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- The Least Quadratic Non ResidueAnnals of Mathematics, 1952