Relativized NC. (English) Zbl 0627.68043

Wilson, Christopher B.

Math. Syst. Theory 20, No. 1, 13-29 (1987).

This paper introduces a notion of relativized depth for circuit families and discusses issues regarding uniform families of relativized circuits. This allows us to define a version of relativized NC and compare it under various oracles with relativized L, NL, and P. We see that \(NC_ 1\) is properly contaied in L if and only if there exists an oracle A such that \(NC_ 1^ A\) is properly contained in \(L^ A\). There is an oracle A where the hierarchy collapses, \(NC_ 1^ A=NC^ A\), and another where \(NC_ 1^ A\subset NC^ A_ 2\subset...\subset NC^ A\subset P^ A\). We then construct an A so that, for any k, \(NC^ A_ 1\) contains a set not in \(NSPACE^ A(O(n^ k))\), suggesting that the notion of relativized space is too weak or that of relativized depth is too strong.

MSC:

68Q25

Analysis of algorithms and problem complexity

Keywords:

relativized complexity classes; relativized depth for circuit families; uniform families of relativized circuits; relativized NC; oracles

References:

[1]	E. Allender, The complexity of sparse sets inP, Proceedings of the Structure in Complexity Theory Conference, Springer-Verlag, New York, 1986, pp. 1–11.
[2]	D. Angluin, On relativizing auxiliary pushdown machines,Math. Systems Theory,13 (1980), 283–299. · doi:10.1007/BF01744301
[3]	T. Baker, J. Gill, and R. Solovay, Relativizations of theP = ?NP question,SIAM J. Comput.,4 (1975), 431–452. · Zbl 0323.68033 · doi:10.1137/0204037
[4]	P. Beame, S. Cook, and J. Hoover, Log depth circuits for division and related problems,Proceedings of the 25th Symposium on Foundations of Computer Science, 1984, pp. 1–6. · Zbl 0797.68074
[5]	N. Blum, A Boolean function requiring 3n network size,Theoret. Comput. Sci.,28 (1984), 337–345. · Zbl 0539.94036 · doi:10.1016/0304-3975(83)90029-4
[6]	R. V. Book, T. J. Long, and A. Selman, Quantitative relativizations of complexity classes,SIAM J. Comput.,13 (1984), 461–486. · Zbl 0599.03041 · doi:10.1137/0213030
[7]	R. V. Book, T. J. Long, and A. Selman, Qualitative relativizations of complexity classes,J. Comput. System Sci.,30 (1985), 395–413. · Zbl 0569.03016 · doi:10.1016/0022-0000(85)90053-4
[8]	A. Borodin, On relating time and space to size and depth,SIAM J. Comput.,6 (1977), 733–744. · Zbl 0366.68039 · doi:10.1137/0206054
[9]	S. Cook, A taxonomy of problems with fast parallel algorithms,Inform. and Control,64 (1985), 2–22. · Zbl 0575.68045 · doi:10.1016/S0019-9958(85)80041-3
[10]	R. Lander and N. Lynch, Relativizations of questions about log-space reducibility,Math. Systems Theory,10 (1976), 19–32. · Zbl 0341.68036 · doi:10.1007/BF01683260
[11]	P. Orponen, General nonrelativizability results for parallel models of computation,Proceedings of the Winter School on Theoretical Computer Science, 1984, pp. 194–205.
[12]	W. Paul, A 2.5n lower bound on the combinatorial complexity of Boolean functions,SIAM J. Comput.,6 (1977), 427–443. · Zbl 0358.68081 · doi:10.1137/0206030
[13]	W. Paul, N. Pippenger, E. Szemeredi, and W. Trotter, On nondeterminism versus determinism and related problems,Proceedings of the 24th Symposium on Foundations of Computer Science, 1983, pp. 429–438.
[14]	N. Pippenger, On simultaneous resource bounds (prelinary version),Proceedings of the 20th Symposium on Foundations of Computer Science, (1979), pp. 307–311.
[15]	C. W. Rackoff and J. I. Seiferas, Limitations on separating nondeterministic complexity classes,SIAM J. Comput.,10 (1981), 742–745. · Zbl 0468.68052 · doi:10.1137/0210057
[16]	W. L. Ruzzo, On uniform circuit complexity,J. Comput. System Sci.,22 (1981), 365–383. · Zbl 0462.68013 · doi:10.1016/0022-0000(81)90038-6
[17]	W. L. Ruzzo, J. Simon, and M. Tompa, Space-bounded hierarchies and probabilistic computations,J. Comput. System Sci.,28 (1984), 216–230. · Zbl 0573.68021 · doi:10.1016/0022-0000(84)90066-7
[18]	W. Savitch, Relationships between nondeterministic and deterministic tape complexities,J. Comput. System Sci.,4 (1970), 177–192. · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X
[19]	C. P. Schnorr, The network complexity and the Turing machine complexity of finite functions,Acta Inform.,7 (1976), 95–107. · Zbl 0338.02019 · doi:10.1007/BF00265223
[20]	I. Simon, On some subrecursive reducibilities, Ph.D. dissertation, Stanford University, 1977.
[21]	L. Stockmeyer, The polynomial time hierarchy,Theoret. Comput. Sci.,3 (1977), 1–22. · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
[22]	C. Wilson, Relativized circuit size and depth, Technical Report # 179/85, Department of Computer Science, University of Toronto, 1985.
[23]	C. Wilson, Relativized circuit complexity,J. Comput. System Sci.,31 (1985), 169–181. · Zbl 0583.68023 · doi:10.1016/0022-0000(85)90040-6
[24]	A. Yao, Separating the polynomial-time hierarchy by oracles,Proceedings of the 26th Symposium on Foundations of Computer Science, 1985, pp. 1–10.