On the limits of computations with the floor function. (English) Zbl 0659.68051
The authors define the concept of an “analytic computation tree” (ACT) as an algorithmic model (decision tree) which operates on \({\mathbb{R}}^ n\) and at each step either (a) compares a real number with 0 and branches according to the result, or (b) computes a real function which is a composition of analytic functions and the floor function. ACTs appear thus as a direct generalization of the “algebraic computation trees” introduced by M. Ben-Or [Proc. 15th Ann. ACM Symp. Theory Comput., 80-86 (1983)].
Topological arguments are used in an attempt to characterize those languages (subsets of \({\mathbb{R}}^ n)\) which are decidable by ACTs. Necessary conditions for a language to be accepted (or accepted by halting) by an ACT are derived; these are expressed in terms of zero sets with open complements or in terms of Lebesgue or Jordan measurable sets. As an application of these results, it is shown that the languages \({\mathbb{Q}}^ n\), REL (the \({\mathbb{Z}}\)-linearly dependent n-tuples of reals), and ALG (the algebraically dependent n-tuples) are accepted (but not their complements in \({\mathbb{R}}^ n)\).
Topological arguments are used in an attempt to characterize those languages (subsets of \({\mathbb{R}}^ n)\) which are decidable by ACTs. Necessary conditions for a language to be accepted (or accepted by halting) by an ACT are derived; these are expressed in terms of zero sets with open complements or in terms of Lebesgue or Jordan measurable sets. As an application of these results, it is shown that the languages \({\mathbb{Q}}^ n\), REL (the \({\mathbb{Z}}\)-linearly dependent n-tuples of reals), and ALG (the algebraically dependent n-tuples) are accepted (but not their complements in \({\mathbb{R}}^ n)\).
Reviewer: J.Weinstein
MSC:
68W99 | Algorithms in computer science |
26E05 | Real-analytic functions |
28A05 | Classes of sets (Borel fields, \(\sigma\)-rings, etc.), measurable sets, Suslin sets, analytic sets |
54C50 | Topology of special sets defined by functions |
Keywords:
decidable languages; analytic computation tree; real function; analytic functions; floor function; algebraic computation trees; halting; measurable setsReferences:
[1] | Ben Or, M., Lower bounds for algebraic computation trees, (Proc. 15th Ann. ACM Symp. Theory of Computing (1983)), 80-86 |
[2] | Dobkin, D.; Lipton, R. J., A lower bound of \(12n^2\) on linear search programs for the knapsack problem, J. Comput. Systems Sci., 16, 413-417 (1978) · Zbl 0397.68045 |
[3] | Hastad, J.; Helfrich, B.; Lagarias, J.; Schnorr, C. P., Polynomial time algorithms for finding integer relations among real numbers, (Monien, B.; Vidal-Nagnet, G., STACS ’86, Lecture Notes in Computer Science, Vol. 210 (1986), Springer-Verlag: Springer-Verlag Heidelberg), 105-118, revised version. SIAM J. Comput., in press · Zbl 0606.68033 |
[4] | Klein, P.; Meyer auf der Heide, F., A lower bound for the knapsack problem on random access machines, Acta Inform., 19, 385-395 (1983) · Zbl 0515.68037 |
[5] | Lovász, L., (An Algorithmic Theory of Numbers, Graphs and Convexity (1985), University of Bonn), Report No. 85368-OR |
[6] | Lautemann, C.; Meyer auf der Heide, F., Lower time bounds for integer programming with two variables, Inform. Process. Lett., 21, 101-105 (1985) · Zbl 0587.90072 |
[7] | Meyer auf der Heide, F., Lower bounds for solving linear diophantine equations on RAMs, J. Assoc. Comput. Mach., 32, 4, 929-937 (1985) · Zbl 0633.68031 |
[8] | Range, R. M., Holomorphic functions and integral representations in several complex variables, (Grad. Texts in Mathematics, Vol. 108 (1986), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0208.10303 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.