乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:12:11Z","timestamp":1725534731400},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_18","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T08:37:10Z","timestamp":1246696630000},"page":"195-209","source":"Crossref","is-referenced-by-count":8,"title":["Unconditional Lower Bounds against Advice"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"18_CR1","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1137\/S0097539792233907","volume":"23","author":"E. Allender","year":"1994","unstructured":"Allender, E., Gore, V.: A uniform circuit lower bound for the permanent. SIAM Journal on Computing\u00a023(5), 1026\u20131049 (1994)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"18_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1490270.1490272","volume":"1","author":"S. Aaronson","year":"2009","unstructured":"Aaronson, S., Wigderson, A.: Algebrization: A New Barrier in Complexity Theory. ACM Trans. Comput. Theory\u00a01(1), 1\u201354 (2009), \n \n http:\/\/doi.acm.org\/10.1145\/1490270.1490272","journal-title":"ACM Trans. Comput. Theory"},{"issue":"2","key":"18_CR3","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00037-001-8190-2","volume":"10","author":"H. Buhrman","year":"2001","unstructured":"Buhrman, H., Fenner, S., Fortnow, L., Torenvliet, L.: Two oracles that force a big crunch. Computational Complexity\u00a010(2), 93\u2013116 (2001)","journal-title":"Computational Complexity"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01, 3\u201340 (1991)","journal-title":"Computational Complexity"},{"issue":"4","key":"18_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P =? NP question. SIAM Journal on Computing\u00a04(4), 431\u2013442 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S.: A hierarchy for nondeterministic time complexity. In: Conference Record, Fourth Annual ACM Symposium on Theory of Computing, Denver, Colorado, May 1-3, 1972, pp. 187\u2013192 (1972)","DOI":"10.1145\/800152.804913"},{"issue":"6","key":"18_CR7","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1145\/1101821.1101822","volume":"52","author":"L. Fortnow","year":"2005","unstructured":"Fortnow, L., Lipton, R., van Melkebeek, D., Viglas, A.: Time-space lower bounds for satisfiability. Journal of the ACM\u00a052(6), 833\u2013865 (2005)","journal-title":"Journal of the ACM"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polynomial time. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 316\u2013324 (2004)","DOI":"10.1109\/FOCS.2004.33"},{"key":"18_CR9","unstructured":"Fortnow, L., Santhanam, R., Trevisan, L.: Promise hierarchies. Electronic Colloquium on Computational Complexity (ECCC)\u00a011(98) (2004)"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R., Trevisan, L.: Hierarchies for semantic classes. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (2005)","DOI":"10.1145\/1060590.1060642"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Homer, S., Mocas, S.: Nonuniform lower bounds for exponential time classes. In: 20th International Symposium on Mathematical Foundations of Computer Science, pp. 159\u2013168 (1995)","DOI":"10.1007\/3-540-60246-1_122"},{"issue":"4","key":"18_CR12","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R. Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences\u00a065(4), 672\u2013694 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. In: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, pp. 355\u2013364 (2003)","DOI":"10.1145\/780542.780595"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Verbeek, R.: On the monte carlo space constructible functions and separation results for probabilistic complexity classes. Information and Computation\u00a075 (1987)","DOI":"10.1016\/0890-5401(87)90057-5"},{"issue":"5","key":"18_CR15","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A.R. Klivans","year":"2002","unstructured":"Klivans, A.R., van Melkebeek, D.: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM J. Comput.\u00a031(5), 1501\u20131526 (2002), \n \n http:\/\/dx.doi.org\/10.1137\/S0097539700389652","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"18_CR16","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0304-3975(95)00078-X","volume":"158","author":"S.E. Mocas","year":"1996","unstructured":"Mocas, S.E.: Separating classes in the exponential-time hierarchy from classes in PH. Theoretical Computer Science\u00a0158(1-2), 221\u2013231 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"18_CR17","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. Journal of Computer and System Sciences\u00a049(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"18_CR18","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A. Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055(1), 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"18_CR19","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1137\/0210057","volume":"10","author":"C. Rackoff","year":"1981","unstructured":"Rackoff, C., Seiferas, J.: Limitations on separating nondeterministic complexity classes. SIAM Journal on Computing\u00a010(4), 742\u2013745 (1981)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"18_CR20","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"Seiferas, J., Fischer, M., Meyer, A.: Separating nondeterministic time complexity classes. Journal of the ACM\u00a025(1), 146\u2013167 (1978)","journal-title":"Journal of the ACM"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.: Pseudorandomness and average-case complexity via uniform reductions. In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, vol.\u00a017 (2002)","DOI":"10.1109\/CCC.2002.1004348"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"van Melkebeek, D., Pervyshev, K.: A generic time hierarchy for semantic models with one bit of advice. In: Proceedings of 21st Annual IEEE Conference on Computational Complexity, pp. 129\u2013144 (2006)","DOI":"10.1109\/CCC.2006.7"},{"issue":"3","key":"18_CR23","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0304-3975(83)90015-4","volume":"26","author":"S. \u017d\u00e1k","year":"1983","unstructured":"\u017d\u00e1k, S.: A Turing machine time hierarchy. Theoretical Computer Science\u00a026(3), 327\u2013333 (1983)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T02:00:25Z","timestamp":1552096825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}