×

Frequency computation and bounded queries. (English) Zbl 0874.03048

Summary: There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: \(F^{A}_{a}(x_{1},\ldots,x_{a})=A(x_{1})\cdots A(x_{a})\). We are interested in the complexity (in terms of the number of queries) of approximating \(F^{A}_{a}\). Let \(b\leq a\) and let \(f\) be any function such that \(F^{A}_{a}(x_{1},\ldots,x_{a})\) and \(f(x_{1},\ldots,x_{a})\) agree on at least \(b\) bits. For a general set \(A\) we have matching upper and lower bounds on \(f\) that depend on coding theory. These are applied to get exact bounds for the case where \(A\) is semirecursive, \(A\) is superterse, and (assuming P\(\not=\)NP) \(A=\text{SAT}\). We obtain exact bounds when \(A\) is the halting problem using different methods.

MSC:

03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrawal, M.; Arvind, V., Polynomial time truth-table reductions to p-selective sets, (Proc. 9th Ann. Conf. on Structure in Complexity Theory (1994), IEEE Computer Society Press,: IEEE Computer Society Press, Silver Springs, MD) · Zbl 0871.68082
[2] Amir, A.; Beigel, R.; Gasarch, W. I., Some connections between bounded query classes and nonuniform complexity, (Proc. 5th Ann. Conf. on Structure in Complexity Theory (1990), IEEE Computer Society Press,: IEEE Computer Society Press, Silver Springs, MD), 232-243, A much expanded version has been submitted to Inform. and Comput.
[3] Beigel, R., Query-limited reducibilities, (Ph.D. Thesis (1987), Stanford University), Also available as Report No. STAN-CS-88-1221
[4] Beigel, R., A structural theorem that depends quantitatively on the complexity of SAT, (Proc. 2nd Ann. Conf. on Structure in Complexity Theory (1987), IEEE Computer Society Press,: IEEE Computer Society Press, Silver Springs, MD), 28-32
[5] Beigel, R.; Gasarch, W. I.; Gill, J. T.; Owings, J. C., Terse, superterse, and verbose sets, Inform. and Comput., 103, 68-85 (1993) · Zbl 0781.68057
[6] R. Beigel, M. Kummer and F. Stephan, Approximable sets, to appear. An earlier version appeared in STRUCTURES 1994.; R. Beigel, M. Kummer and F. Stephan, Approximable sets, to appear. An earlier version appeared in STRUCTURES 1994.
[7] Cai, J.; Hemachandra, L. A., Enumerative counting is hard, Inform. Comput., 82, 34-44 (1989) · Zbl 0679.68072
[8] Cohen, G.; Frankl, P., Good coverings of Hamming spaces with spheres, Discrete Math., 56, 125-131 (1989) · Zbl 0579.94017
[9] Cohen, G.; Karpovsky, M.; Mattson, H., Covering radius — survey and recent results, IEEE Trans. Inform. Theory, IT-31, 338-343 (1985) · Zbl 0586.94014
[10] Cohen, G.; Lobstein, A.; Sloane, N., Further results on the covering radius of codes, IEEE Trans. Inform. Theory, IT-32, 680-694 (1986) · Zbl 0618.94014
[11] Gasarch, W., Bounded queries in recursion theory: A survey, (Proc. 6th Ann. Conf. on Structure in Complexity Theory (1991), IEEE Computer Society Press,: IEEE Computer Society Press, Silver Springs, MD), 62-78
[12] W. Gasarch, M.W. Krentel and K. Rappoport, OptP-completeness as the normal behavior of NP-complete problems, Math. Systems Theory; W. Gasarch, M.W. Krentel and K. Rappoport, OptP-completeness as the normal behavior of NP-complete problems, Math. Systems Theory · Zbl 0830.68064
[13] Harizanov, V.; Kummer, M.; Owings, J., Frequency computations and the cardinality theorem, J. Symbolic Logic, 57, 682-687 (1992) · Zbl 0763.03024
[14] Honkala, I., Modified bounds for covering codes, IEEE Trans. Inform. Theory, IT-37, 351-365 (1991) · Zbl 0721.94023
[15] Jockusch, C. G., Semirecursive sets and positive reducibility, Trans. AMS, 131, 420-436 (1968) · Zbl 0198.32402
[16] Krentel, M. W., The complexity of optimization problems, J. Comput. Syst. Sci., 36, 490-509 (1988) · Zbl 0652.68040
[17] Kummer, M., A proof of Beigel’s cardinality conjecture, J. Symbolic Logic, 57, 677-681 (1992) · Zbl 0763.03025
[18] Kummer, M.; Stephan, F., Some aspects of frequency computation, (Interner Bericht 21/91 (1991), Universität Karlsruhe, Fakultät für Informatik)
[19] Kummer, M.; Stephan, F., Effective search problems, Math. Logic Quart., 40 (1994) · Zbl 0806.03027
[20] Ogiwara, M., Polynomial-time membership comparable sets, (Proc. 9th Ann. Conf. on Structure in Complexity Theory (1994), IEEE Computer Society Press,: IEEE Computer Society Press, Silver Springs, MD)
[21] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw Hill,: McGraw Hill, New York · Zbl 0183.01401
[22] Rose, G., An extended notion of computability, (Abstr. Internat. Congress for Logic, Methodology, and Philosophy of Science (1960)), 14
[23] Smullyan, R., Theory of Formal Systems, (Annals of Mathematical Studies, Vol. 47 (1961), Princeton University Press,: Princeton University Press, Princeton, NJ) · Zbl 0097.24503
[24] Soare, R. I., Recursively Enumerable Sets and Degrees, (Perspectives in Mathematical Logic (1987), Springer,: Springer, Berlin) · Zbl 0401.03018
[25] Trakhtenbrot, B. A., On the frequency computation of functions, Algebra Logika, 2, 25-32 (1964), (in Russian)
[26] Wee, G. V., Improved sphere bounds on the covering radius of codes, IEEE Trans. Inform. Theory, IT-34, 237-245 (1988) · Zbl 0653.94014
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.