Adaptive logspace reducibility and parallel time. (English) Zbl 0815.68054

Àlvarez, C.; Balcázar, J. L.; Jenner, B.

Math. Syst. Theory 28, No. 2, 117-140 (1995).

Summary: We discuss two notions of functional oracle for logarithmic space-bounded machines, which differ in whether there is only one oracle tape for both the query and the answer or a separate tape for the answer, which can still be read while the next query is already being constructed. The first notion turns out to be basically nonadaptive, behaving like access to an oracle set. The second notion, on the other hand, is adaptive. By imposing appropriate bounds on the number of functional oracle queries made in this computation model, we obtain new characterizations of the NC and AC hierarchies; thus the number of oracle queries can be considered as a measure of parallel time. Using this characterization of parallel classes, we solve open questions of Wilson.

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Keywords:

functional oracle; logarithmic space-bounded machines

References:

[1]	C. Àlvarez, B. Jenner, A very hard log-space counting class,Theoretical Computer Science 107 (1993), 3-30. · Zbl 0813.68098 · doi:10.1016/0304-3975(93)90252-O
[2]	J. L. Balcázar, J. Díaz, J. Gabarró,Structural Complexity, Vol. I, Springer-Verlag, Berlin, 1988. · Zbl 0638.68040
[3]	J. L. Balcázar, J. Díaz, J. Gabarró,Structural Complexity, Vol. II, Springer-Verlag, Berlin, 1990. · Zbl 0746.68032
[4]	D. A. Mix Barrington, N. Immerman, H. Straubing, On uniformity within NC1,Journal of Computer and System Sciences 41(3) (1990), 274-306. · Zbl 0719.68023 · doi:10.1016/0022-0000(90)90022-D
[5]	A. Borodin, On relating time and space to size and depth,SIAM Journal of Computing 6(4) (1977), 733-744. · Zbl 0366.68039 · doi:10.1137/0206054
[6]	A. Borodin, S. A. Cook, P. Dymond, W. L. Ruzzo, M. Tompa, Two applications of complementation via inductive counting,SIAM Journal of Computing 18(3) (1989), 559-578. · Zbl 0678.68031 · doi:10.1137/0218038
[7]	S. Buss, The Boolean formula value problem is in ALOGTIME,Proc. 19th Annual ACM Symposium on Theory of Computing (1987), pp. 123-131.
[8]	S. R. Buss, L. Hay, On truth-table reducibility to SAT and the difference hierarchy over NP,Proc. 3rd Structure in Complexity Theory Conference (1988), pp. 224-233.
[9]	J. Castro, C. Seara, Characterizations of some complexity classes between ? 2 p and ? 2 p . Report LSI-90-27, Universitat Politècnica de Catalunya, Barcelona. · Zbl 0860.68048
[10]	J. Castro, C. Seara, The ?-operator and the low hierarchy. Report LSI-92-16-R, Universitat Politècnica de Catalunya, Barcelona. · Zbl 0860.68048
[11]	S. A. Cook, A taxonomy of problems with fast parallel algorithms,Information and Control 64 (1985), 2-22. · Zbl 0575.68045 · doi:10.1016/S0019-9958(85)80041-3
[12]	L. A. Hemachandra, The strong exponential hierarchy collapses,Proc. 19th Annual ACM Symposium on Theory of Computing (1987), pp. 110-122.
[13]	J.-W. Hong, On simularity and duality of computation (I),Information and Control 62 (1984), 109-128. · Zbl 0589.68038 · doi:10.1016/S0019-9958(84)80030-3
[14]	J.-W. Hong,Computation: Computability, Similarity and Duality, Pitman, London, 1986. · Zbl 0665.68042
[15]	B. Jenner, B. Kirsig, Alternierung und Logarithmischer Platz, Dissertation (in German), Universität Hamburg, 1989. · Zbl 0701.68030
[16]	J. Kadin, PNP[log n] and sparse Turing-complete sets for NP,Proc. 2nd Structure in Complexity Theory Conference (1987), pp. 33-40.
[17]	M. W. Krentel, The complexity of optimization problems,Proc. 18th Annual ACM Symposium on Theory of Computing (1986), pp. 69-76.
[18]	R. Ladner, N. Lynch, Relativization of questions about log space computability,Mathematical Systems Theory 10 (1976), 19-32. · Zbl 0341.68036 · doi:10.1007/BF01683260
[19]	R. Ladner, N. Lynch, A. Selman, Comparison of polynomial-time reducibilities,Theoretical Computer Science 1 (1975), 103-123. · Zbl 0321.68039 · doi:10.1016/0304-3975(75)90016-X
[20]	W. Ruzzo, On uniform circuit complexity,Journal of Computer and System Sciences 22 (1981), 365-383. · Zbl 0462.68013 · doi:10.1016/0022-0000(81)90038-6
[21]	K. Wagner, Bounded query classes,SIAM Journal on Computing 19(5) (1990), 833-846. · Zbl 0711.68047 · doi:10.1137/0219058
[22]	C. B. Wilson, Relativized NC,Mathematical Systems Theory 20 (1987), 13-29. · Zbl 0627.68043 · doi:10.1007/BF01692056
[23]	C. B. Wilson, Decomposing NC and AC,SIAM Journal on Computing 19(2) (1990), 384-396. (Preliminary version at 4th Structure in Complexity Theory Conference, 1989.) · Zbl 0692.68045 · doi:10.1137/0219024