Abstract
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 relativizedNC and compare it under various oracles with relativizedL, NL, andP. We see thatNC 1 is properly contained inL if and only if there exists an oracleA such thatNC A1 is properly contained inL A. There is an oracleA where the hierarchy collapses,NC A1 = NC A, and another whereNC A1 ⊂NC A2 ⊂ ⋯ ⊂NC A ⊂P A. We then construct anA so that, for anyk, NC A1 contains a set not inNSPACE A(O(n k)), suggesting that the notion of relativized space is too weak or that of relativized depth is too strong.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Allender, The complexity of sparse sets inP, Proceedings of the Structure in Complexity Theory Conference, Springer-Verlag, New York, 1986, pp. 1–11.
D. Angluin, On relativizing auxiliary pushdown machines,Math. Systems Theory,13 (1980), 283–299.
T. Baker, J. Gill, and R. Solovay, Relativizations of theP = ?NP question,SIAM J. Comput.,4 (1975), 431–452.
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.
N. Blum, A Boolean function requiring 3n network size,Theoret. Comput. Sci.,28 (1984), 337–345.
R. V. Book, T. J. Long, and A. Selman, Quantitative relativizations of complexity classes,SIAM J. Comput.,13 (1984), 461–486.
R. V. Book, T. J. Long, and A. Selman, Qualitative relativizations of complexity classes,J. Comput. System Sci.,30 (1985), 395–413.
A. Borodin, On relating time and space to size and depth,SIAM J. Comput.,6 (1977), 733–744.
S. Cook, A taxonomy of problems with fast parallel algorithms,Inform. and Control,64 (1985), 2–22.
R. Lander and N. Lynch, Relativizations of questions about log-space reducibility,Math. Systems Theory,10 (1976), 19–32.
P. Orponen, General nonrelativizability results for parallel models of computation,Proceedings of the Winter School on Theoretical Computer Science, 1984, pp. 194–205.
W. Paul, A 2.5n lower bound on the combinatorial complexity of Boolean functions,SIAM J. Comput.,6 (1977), 427–443.
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.
N. Pippenger, On simultaneous resource bounds (prelinary version),Proceedings of the 20th Symposium on Foundations of Computer Science, (1979), pp. 307–311.
C. W. Rackoff and J. I. Seiferas, Limitations on separating nondeterministic complexity classes,SIAM J. Comput.,10 (1981), 742–745.
W. L. Ruzzo, On uniform circuit complexity,J. Comput. System Sci.,22 (1981), 365–383.
W. L. Ruzzo, J. Simon, and M. Tompa, Space-bounded hierarchies and probabilistic computations,J. Comput. System Sci.,28 (1984), 216–230.
W. Savitch, Relationships between nondeterministic and deterministic tape complexities,J. Comput. System Sci.,4 (1970), 177–192.
C. P. Schnorr, The network complexity and the Turing machine complexity of finite functions,Acta Inform.,7 (1976), 95–107.
I. Simon, On some subrecursive reducibilities, Ph.D. dissertation, Stanford University, 1977.
L. Stockmeyer, The polynomial time hierarchy,Theoret. Comput. Sci.,3 (1977), 1–22.
C. Wilson, Relativized circuit size and depth, Technical Report # 179/85, Department of Computer Science, University of Toronto, 1985.
C. Wilson, Relativized circuit complexity,J. Comput. System Sci.,31 (1985), 169–181.
A. Yao, Separating the polynomial-time hierarchy by oracles,Proceedings of the 26th Symposium on Foundations of Computer Science, 1985, pp. 1–10.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wilson, C.B. RelativizedNC . Math. Systems Theory 20, 13–29 (1987). https://doi.org/10.1007/BF01692056
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01692056