{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:49:13Z","timestamp":1725662953307},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540164869"},{"type":"electronic","value":"9783540398257"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_111","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:46:39Z","timestamp":1330195599000},"page":"362-382","source":"Crossref","is-referenced-by-count":4,"title":["Parallel computation and the NC hierarchy relativized"],"prefix":"10.1007","author":[{"given":"Christopher B.","family":"Wilson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/BF01744301","volume":"13","author":"D. Angluin","year":"1980","unstructured":"D. Angluin, \u201eOn Relativizing Auxiliary Pushdown Machines,\u201d Math. Systems Theory 13(1980), pp 283\u2013299","journal-title":"Math. Systems Theory"},{"issue":"4","key":"27_CR2","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay, \u201eRelativizations of the P=?NP Question,\u201d SIAM Journal on Computing, vol. 4, no. 4, Dec. 1975, pp 431\u2013452","journal-title":"SIAM Journal on Computing"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"T. Baker and A. Selman, \u201eA Second Step toward the Polynomial Hierarchy,\u201d Proc. 17th FOCS (1976), pp 71\u201375","DOI":"10.1109\/SFCS.1976.2"},{"key":"27_CR4","unstructured":"N. Blum, \u201eA Boolean Function Requiring 3n Network Size,\u201d Tech. Report A82\/13 (June 1982), Universit\u00e4t des Saarlandes"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. V. Book","year":"1984","unstructured":"R. V. Book, T. J. Long, and A. Selman, \u201cQuantitative Relativizations of Complexity Classes,\u201d SIAM Journal on Computing 13(1984), pp 461\u2013486","journal-title":"SIAM Journal on Computing"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"R. V. Book, T. J. Long, and A. Selman, \u201cQualitative Relativizations of Complexity Classes,\u201d to appear in the Journal of Computer and System Sciences (1985)","DOI":"10.1016\/0022-0000(85)90053-4"},{"issue":"4","key":"27_CR7","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"A. Borodin, \u201cOn Relating Time and Space to Size and Depth,\u201d SIAM Journal on Computing, vol. 6, no. 4, Dec. 1977, pp 733\u2013744","journal-title":"SIAM Journal on Computing"},{"key":"27_CR8","unstructured":"J. Buss, \u201cRelativized Alternation\u201d, proceedings of this conference"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"S. Cook, \u201cThe Classification of Problems which Have Fast Parallel Algorithms,\u201d Technical Report #164\/83 University of Toronto, Department of Computer Science (1983)","DOI":"10.1007\/3-540-12689-9_95"},{"key":"27_CR10","unstructured":"S. Cook, private communication"},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"R. Ladner and N. Lynch, \u201cRelativizations of Questions about Log-Space Reducibility,\u201d Math. Systems Theory 10(1976), pp 19\u201332","journal-title":"Math. Systems Theory"},{"key":"27_CR12","unstructured":"P. Orponen, \u201cGeneral Nonrelativizability Results for Parallel Models of Computation,\u201d Proceedings of the Winter School on Theoretical Computer Science, 1984, pp 194\u2013205"},{"issue":"3","key":"27_CR13","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0206030","volume":"6","author":"W. Paul","year":"1977","unstructured":"W. Paul, \u201cA 2.5n Lower Bound on the Combinatorial Complexity of Boolean Functions,\u201d SIAM Journal on Computing, vol. 6, no. 3, Sept. 1977, pp 427\u2013443","journal-title":"SIAM Journal on Computing"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"W.Paul, N. Pippenger, E. Szemeredi, and W. Trotter, \u201cOn Nondeterminism versus Determinism and Related Problems,\u201d Proceedings of the 24th FOCS, 1983, pp 429\u2013438","DOI":"10.1109\/SFCS.1983.39"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"N. Pippenger, \u201cOn Simultaneous Resource Bounds (Preliminary Version),\u201d Proceedings of the 20th FOCS (1979), pp 307\u2013311","DOI":"10.1109\/SFCS.1979.29"},{"issue":"4","key":"27_CR16","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1137\/0210057","volume":"10","author":"C. W. Rackoff","year":"1981","unstructured":"C. W. Rackoff and J. I. Seiferas, \u201cLimitations on Separating Nondeterministic Complexity Classes,\u201d SIAM Journal on Computing, vol. 10, no. 4, Nov. 1981, pp 742\u2013745","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"27_CR17","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W. L. Ruzzo","year":"1984","unstructured":"W. L. Ruzzo, J. Simon, and M. Tompa, \u201cSpace-Bounded Hierarchies and Probabilistic Computations,\u201d Journal of Computer and System Sciences 28, 2(April 1984), pp 216\u2013230","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"27_CR18","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. L. Ruzzo","year":"1981","unstructured":"W. L. Ruzzo, \u201cOn Uniform Circuit Complexity,\u201d Journal of Computer and System Sciences 22, 3(1981), pp 365\u2013383","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR19","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"W. Savitch, \u201cRelationships between Nondeterministic and Deterministic Tape Complexities,\u201d Journal of Computer and System Sciences 4(1970), pp 177\u2013192","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR20","unstructured":"I. Simon, \u201cOn Some Subrecursive Reducibilities,\u201d Ph.D. Dissertation, Stanford Univ., March 1977"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer, \u201cThe Polynomial Time Hierarchy,\u201d Theoretical Computer Science 3(1977), pp 1\u201322","journal-title":"Theoretical Computer Science"},{"key":"27_CR22","unstructured":"C. Wilson, \u201cRelativized Circuit Size and Depth,\u201d Technical Report #179\/85 University of Toronto, Department of Computer Science (1985)"},{"issue":"2","key":"27_CR23","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. Wilson","year":"1985","unstructured":"C. Wilson, \u201cRelativized Circuit Complexity,\u201d Journal of Computer and System Sciences 31, 2(October 1985), pp 169\u2013181","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"A. Yao, \u201cSeparating the Polynomial-Time Hierarchy by Oracles,\u201d Proc. 26th FOCS, (1985), pp 1\u201310","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_111.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:10:30Z","timestamp":1605643830000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_111","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}