{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:27Z","timestamp":1725664407475},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_86","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:49:02Z","timestamp":1330260542000},"page":"210-220","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Some consequences of cryptographical conjectures for S 2 1 and EF"],"prefix":"10.1007","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Pudl\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0217013","volume":"17","author":"W.B. Alexi","year":"1988","unstructured":"W.B. Alexi, B.Chor, O. Goldreich, C.P. Schnorr (1988) RSA and Rabin functions: Certain parts are as hard as the whole, SIAM J. Comp., 17, pp.194\u2013209.","journal-title":"SIAM J. Comp."},{"key":"11_CR2","unstructured":"S.R. Buss (1986) Bounded Arithmetic, Bibliopolis."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S. A. (1975) Feasibly constructive proofs and the propositional calculus, in: Proc. 7\nth\nAnnual ACM Symp. on Theory of Computing, pp. 83\u201397. ACM Press.","DOI":"10.1145\/800116.803756"},{"issue":"2","key":"11_CR4","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1090\/S0002-9947-1993-1124169-X","volume":"338","author":"J. Kraj\u00ed\u010dek","year":"1993","unstructured":"Kraj\u00ed\u010dek, J. (1993) Fragments of bounded arithmetic and bounded query classes, Transactions of the A.M.S., 338(2): 587\u2013598.","journal-title":"Transactions of the A.M.S."},{"issue":"1","key":"11_CR5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.2307\/2275250","volume":"59","author":"J. Kraj\u00ed\u010dek","year":"1994","unstructured":"-(1994) Lower bounds to the size of constant-depth propositional proofs, Journal of Symbolic Logic, 59(1):73\u201386.","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR6","unstructured":"-(1994) Bounded arithmetic, propositional logic and complexity theory, Cambridge University Press, in print."},{"key":"11_CR7","unstructured":"-(1994) Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, submitted."},{"issue":"3","key":"11_CR8","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"Kraj\u00ed\u010dek, J., and Pudl\u00e1k, P. (1989) Propositional proof systems, the consistency of first order theories and the complexity of computations, J. Symbolic Logic, 54(3):1063\u20131079","journal-title":"J. Symbolic Logic"},{"key":"11_CR9","doi-asserted-by":"crossref","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., and Takeuti, G. (1991) Bounded arithmetic and the polynomial hierarchy, Annals of Pure and Applied Logic, 52: 143\u2013153.","journal-title":"Annals of Pure and Applied Logic"},{"key":"11_CR10","unstructured":"Papadimitriou, A. (1994) Computational complexity, Addison-Wesley."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Paris, J, and Wilkie, A. (1985) Counting problems in bounded arithmetic, in: Methods in Mathematical Logic, LNM 1130, pp.317\u2013340.Springer.","DOI":"10.1007\/BFb0075316"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0204018","volume":"4","author":"V.R. Pratt","year":"1975","unstructured":"Pratt, V.R. (1975) Every prime has a succinct certificate, SIAM J. Computing, 4:214\u2013220.","journal-title":"SIAM J. Computing"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"A.A. Razborov (1994) Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic, Izvestiya of the RAN, to appear.","DOI":"10.1070\/IM1995v059n01ABEH000009"},{"key":"11_CR14","unstructured":"-(1994) On provably disjoint NP-pairs, Basic Research in Computer Science Center, Aarhus, RS-94-36, preprint."},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"M. Rivest","year":"1978","unstructured":"M. Rivest, A. Shamir and L. Adleman (1978) A method of obtaining digital signatures and public-key cryptosystems. ACM Communications 21, pp. 120\u2013126.","journal-title":"ACM Communications"},{"key":"11_CR16","unstructured":"G. Takeuti (1992) RSUV isomorphism, in Arithmetic, Proof Theory and Computational Complexity, Clote and Kraj\u00ed\u010dek eds., Oxford Univ. Press, pp. 364\u2013386."}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_86","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:37:23Z","timestamp":1558255043000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_86","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}