乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T17:23:52Z","timestamp":1725902632581},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662553855"},{"type":"electronic","value":"9783662553862"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-662-55386-2_3","type":"book-chapter","created":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T07:24:53Z","timestamp":1498634693000},"page":"31-47","source":"Crossref","is-referenced-by-count":0,"title":["Total Search Problems in Bounded Arithmetic and Improved Witnessing"],"prefix":"10.1007","author":[{"given":"Arnold","family":"Beckmann","sequence":"first","affiliation":[]},{"given":"Jean-Jos\u00e9","family":"Razafindrakoto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,29]]},"reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"issue":"1","key":"3_CR2","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1142\/S0219061309000847","volume":"9","author":"A Beckmann","year":"2009","unstructured":"Beckmann, A., Buss, S.R.: Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic. J. Math. Log. 9(1), 103\u2013138 (2009). doi:\n10.1142\/S0219061309000847","journal-title":"J. Math. Log."},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Beckmann, A., Buss, S.R.: Characterising definable search problems in bounded arithmetic via proof notations. In: Ways of Proof Theory. Ontos Series on Mathematical Logic, vol. 2, pp. 65\u2013133. Ontos Verlag, Heusenstamm (2010)","DOI":"10.1515\/9783110324907.65"},{"issue":"1","key":"3_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2559950","volume":"15","author":"A Beckmann","year":"2014","unstructured":"Beckmann, A., Buss, S.R.: Improved witnessing and local improvement principles for second-order bounded arithmetic. ACM Trans. Comput. Log. 15(1), 35 (2014). doi:\n10.1145\/2559950\n\n. (Art. 2)","journal-title":"ACM Trans. Comput. Log."},{"key":"3_CR5","series-title":"Studies in Proof Theory. Lecture Notes","volume-title":"Bounded Arithmetic","author":"SR Buss","year":"1986","unstructured":"Buss, S.R.: Bounded Arithmetic. Studies in Proof Theory. Lecture Notes, vol. 3. Bibliopolis, Naples (1986)"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/plms\/s3-69.1.1","volume":"69","author":"SR Buss","year":"1994","unstructured":"Buss, S.R., Kraj\u00ed\u010dek, J.: An application of Boolean complexity to separation problems in bounded arithmetic. Proc. Lond. Math. Soc. (3) 69(1), 1\u201321 (1994). doi:\n10.1112\/plms\/s3-69.1.1","journal-title":"Proc. Lond. Math. Soc. (3)"},{"issue":"3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.2307\/2586729","volume":"63","author":"M Chiari","year":"1998","unstructured":"Chiari, M., Kraj\u00ed\u010dek, J.: Witnessing functions in bounded arithmetic and search problems. J. Symb. Log. 63(3), 1095\u20131115 (1998). doi:\n10.2307\/2586729","journal-title":"J. Symb. Log."},{"key":"3_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511676277","volume-title":"Logical Foundations of Proof Complexity","author":"S Cook","year":"2010","unstructured":"Cook, S., Nguyen, P.: Logical Foundations of Proof Complexity, 1st edn. Cambridge University Press, New York (2010)","edition":"1"},{"issue":"4","key":"3_CR9","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/2635822","volume":"6","author":"SA Cook","year":"2014","unstructured":"Cook, S.A., Filmus, Y., L\u00ea, D.T.M.: The complexity of the comparator circuit value problem. ACM Trans. Comput. Theory 6(4), 44 (2014). doi:\n10.1145\/2635822","journal-title":"ACM Trans. Comput. Theory"},{"key":"3_CR10","unstructured":"Eguchi, N.: Characterising complexity classes by inductive definitions in bounded arithmetic, June 2013. ArXiv e-prints"},{"issue":"5","key":"3_CR11","doi-asserted-by":"publisher","first-page":"386","DOI":"10.4169\/amer.math.monthly.120.05.386","volume":"120","author":"D Gale","year":"2013","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 120(5), 386\u2013391 (2013). doi:\n10.4169\/amer.math.monthly.120.05.386\n\n. (Reprint of MR1531503)","journal-title":"Am. Math. Mon."},{"key":"3_CR12","series-title":"Graduate Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, New York (1999). doi:\n10.1007\/978-1-4612-0539-5"},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988). doi:\n10.1016\/0022-0000(88)90046-3\n\n. (In: 26th IEEE Conference on Foundations of Computer Science, Portland, OR (1985))","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"3_CR14","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"RM Karp","year":"1985","unstructured":"Karp, R.M., Wigderson, A.: A fast parallel algorithm for the maximal independent set problem. J. Assoc. Comput. Mach. 32(4), 762\u2013773 (1985). doi:\n10.1145\/4221.4226","journal-title":"J. Assoc. Comput. Mach."},{"issue":"6","key":"3_CR15","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.apal.2010.12.002","volume":"162","author":"LA Ko\u0142odziejczyk","year":"2011","unstructured":"Ko\u0142odziejczyk, L.A., Nguyen, P., Thapen, N.: The provably total NP search problems of weak second order bounded arithmetic. Ann. Pure Appl. Log. 162(6), 419\u2013446 (2011). doi:\n10.1016\/j.apal.2010.12.002","journal-title":"Ann. Pure Appl. Log."},{"issue":"1\u20132","key":"3_CR16","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0168-0072(91)90043-L","volume":"52","author":"J Kraj\u00ed\u010dek","year":"1991","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P., Takeuti, G.: Bounded arithmetic and the polynomial hierarchy. Ann. Pure Appl. Logic 52(1\u20132), 143\u2013153 (1991). doi:\n10.1016\/0168-0072(91)90043-L\n\n. (In: International Symposium on Mathematical Logic and Its Applications, Nagoya (1988))","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2178\/jsl\/1185803628","volume":"72","author":"J Kraj\u00ed\u010dek","year":"2007","unstructured":"Kraj\u00ed\u010dek, J., Skelley, A., Thapen, N.: NP search problems in low fragments of bounded arithmetic. J. Symb. Log. 72(2), 649\u2013672 (2007). doi:\n10.2178\/jsl\/1185803628","journal-title":"J. Symb. Log."},{"key":"3_CR18","doi-asserted-by":"publisher","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC 1985, pp. 1\u201310. ACM, New York (1985). doi:\n10.1145\/22145.22146","DOI":"10.1145\/22145.22146"},{"issue":"2","key":"3_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/0022-0000(92)90024-D","volume":"44","author":"EW Mayr","year":"1992","unstructured":"Mayr, E.W., Subramanian, A.: The complexity of circuit value and network stability. J. Comput. Syst. Sci. 44(2), 302\u2013323 (1992). doi:\n10.1016\/0022-0000(92)90024-D","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"3_CR20","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theoret. Comput. Sci. 81(2), 317\u2013324 (1991). doi:\n10.1016\/0304-3975(91)90200-L\n\n. (Algorithms, Automata, Complexity and Games)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"DA Mix-Barrington","year":"1990","unstructured":"Mix-Barrington, D.A., Immerman, N., Straubing, H.: On uniformity within NC1. J. Comput. Syst. Sci. 41(3), 274\u2013306 (1990). doi:\n10.1016\/0022-0000(90)90022-D","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR22","unstructured":"Morioka, T.: Classification of search problems and their definability in bounded arithmetic (2001)"},{"key":"3_CR23","unstructured":"Razafindrakoto, J.J.: Witnessing theorems in bounded arithmetic and applications. Ph.D. thesis, Swansea University (2016). \nhttp:\/\/cs.swan.ac.uk\/~csjjr\/Papers\/thesis.pdf"},{"issue":"7\u20138","key":"3_CR24","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/s00153-011-0240-0","volume":"50","author":"N Thapen","year":"2011","unstructured":"Thapen, N.: Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem. Arch. Math. Log. 50(7\u20138), 665\u2013680 (2011). doi:\n10.1007\/s00153-011-0240-0","journal-title":"Arch. Math. Log."},{"issue":"3","key":"3_CR25","doi-asserted-by":"publisher","first-page":"942","DOI":"10.2307\/2275794","volume":"61","author":"D Zambella","year":"1996","unstructured":"Zambella, D.: Notes on polynomially bounded arithmetic. J. Symb. Log. 61(3), 942\u2013966 (1996). doi:\n10.2307\/2275794","journal-title":"J. Symb. Log."}],"container-title":["Lecture Notes in Computer Science","Logic, Language, Information, and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-55386-2_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,3]],"date-time":"2017-07-03T06:27:06Z","timestamp":1499063226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-55386-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783662553855","9783662553862"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-55386-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}