{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T03:03:49Z","timestamp":1772507029368,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540601784","type":"print"},{"value":"9783540447207","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_78","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:46Z","timestamp":1330278586000},"page":"30-51","source":"Crossref","is-referenced-by-count":10,"title":["On feasible numbers"],"prefix":"10.1007","author":[{"given":"Vladimir Yu.","family":"Sazonov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"3_CR1","volume-title":"Bounded Arithmetic","author":"S.R. Buss","year":"1986","unstructured":"Buss, S.R. (1986) Bounded Arithmetic, Bibliopolis, Napoli, 1986."},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science 223","first-page":"125","volume-title":"Structure in Complexity Theory","author":"S.R. Buss","year":"1986","unstructured":"Buss, S.R. (1986) The polynomial hierarchy and intuitionistic bounded arithmetic, in: Structure in Complexity Theory, Lecture Notes in Computer Science 223 (Springer, Berlin) 125\u2013143."},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A. (1975) Feasibly constructive proofs and the prepositional calculus, in: Proceedings 7th ACM Symposium on the Theory of Computation, 83\u201397.","DOI":"10.1145\/800116.803756"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0168-0072(93)90044-E","volume":"63","author":"S.A. Cook","year":"1993","unstructured":"Cook, S.A. and Urquhart, A. (1993) Functional interpretations of feasibly constructive arithmetic, Annals of Pure and Applied Logic 63, 103\u2013200.","journal-title":"Annals of Pure and Applied Logic"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Dragalin, A.G. (1985) Correctness of inconsistent theories with notions of feasibility, in: Lecture Notes in Computer Science, 208, Springer-Verlag, 58\u201379.","DOI":"10.1007\/3-540-16066-3_7"},{"key":"3_CR6","first-page":"129","volume-title":"Logic Colloquium'80","author":"R.O. Gandy","year":"1982","unstructured":"Gandy, R.O. (1982) Limitations to mathematical knowledge, in: D. van Dalen, D.Laskar, J. Smiley eds., Logic Colloquium'80, North-Holland, Amsterdam, 129\u2013146."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Gurevich, Y. (1983) Algebras of feasible functions, in: FOCS'83, pp.210\u2013214.","DOI":"10.1109\/SFCS.1983.5"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"H\u00e1jek, P., and Pudl\u00e1k, P. (1993) Metamathematics of First-order Arithmetic, Perspectives of Mathematical Logic, 460 pp. Springer-Verlag.","DOI":"10.1007\/978-3-662-22156-3"},{"key":"3_CR9","unstructured":"Immerman, N. (1982) Relational queries computable in polynomial time, in: 14th STOC, pp. 147\u2013152."},{"key":"3_CR10","first-page":"10","volume-title":"Kibernetika \u2014 neogranichennye vozmozhnosti i vozmozhnye ogranichenija. Itogi razvitija","author":"A.N. Kolmogorov","year":"1979","unstructured":"Kolmogorov, A.N.(1979) Automata and life (in Russian), Kibernetika \u2014 neogranichennye vozmozhnosti i vozmozhnye ogranichenija. Itogi razvitija. Moskwa, Nauka, 10\u201329."},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Kraji\u010dek, J., (1995) Bounded Arithmetic, Propositional Logic and Complexity Theory, to appear in Cambridge University Press.","DOI":"10.1017\/CBO9780511529948"},{"key":"3_CR12","doi-asserted-by":"crossref","DOI":"10.1515\/9781400858927","volume-title":"Predicative arithmetic","author":"E. Nelson","year":"1986","unstructured":"Nelson, E. (1986) Predicative arithmetic, Princeton University Press, Princeton, New Jersey."},{"key":"3_CR13","first-page":"137","volume":"88","author":"V.P. Orevkov","year":"1979","unstructured":"Orevkov, V.P. (1979) The lower bounds of complexity the deductions increasing after cut elimination. In: Zapiski nauchnych seminarov LOMI AN SSSR, 88,137\u2013162. (In Russian)","journal-title":"Zapiski nauchnych seminarov LOMI AN SSSR"},{"issue":"3","key":"3_CR14","first-page":"494","volume":"36","author":"R. Parikh","year":"1971","unstructured":"Parikh, R. (1971) Existence and feasibility in arithmetic, JSL, 36, (3), 494\u2013508.","journal-title":"JSL"},{"key":"3_CR15","unstructured":"Prawitz, D. (1965) Natural Deduction, Stockholm."},{"issue":"7","key":"3_CR16","first-page":"319","volume":"16","author":"V. Sazonov","year":"1980","unstructured":"Sazonov, V.Yu. (1980) Polynomial computability and recursivity in finite domains. Elektronische Informationsverarbeitung und Kybernetik, 16, (7), 319\u2013323.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"3_CR17","first-page":"562","volume-title":"Lecture Notes in Computer Science, 88","author":"V. Sazonov","year":"1980","unstructured":"Sazonov, V.Yu. (1980a) A logical approach to the problem \u201cP=NP?\u201d, in: Lecture Notes in Computer Science, 88, Springer, New York, 562\u2013575. (An important correction to this paper is given in [Lecture Notes in Computer Science, 118, Springer, New York,1981, p.490.])"},{"key":"3_CR18","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/3-540-18740-5_84","volume":"278","author":"V. Sazonov","year":"1987","unstructured":"Sazonov, V.Yu. (1987) Bounded set theory and polynomial computability, FCT'87, Lecture Notes in Computer Science, 278, p.391\u2013397.","journal-title":"Lecture Notes in Computer Science"},{"key":"3_CR19","series-title":"Sibirskoje otdelenije","first-page":"138","volume-title":"Trudy instituta matematiki, Sibirskoje otdelenie akademii nauk SSSR, \u201cMatematicheskaja logika i algoritmicheskije problemy\u201d","author":"V. Sazonov","year":"1989","unstructured":"Sazonov, V.Yu. (1989) An equivalence between polynomial constructivity of Markov's principle and the equality P=NP (in Russian), in: Trudy instituta matematiki, Sibirskoje otdelenie akademii nauk SSSR, \u201cMatematicheskaja logika i algoritmicheskije problemy\u201d, Novosibirsk, \u201cNauka\u201d, Sibirskoje otdelenije, 138\u2013165. (See also shorter English version with the same title in P.Petkov ed., Mathematical Logic, Proceedings ffof the Heyting's conference, sept., 1988, Varna, Plenum Press, New York, 1990, 351\u2013360.)."},{"issue":"1","key":"3_CR20","first-page":"331","volume":"57","author":"V. Sazonov","year":"1992","unstructured":"Sazonov, V.Yu. (1992) On feasible numbers, Abstracts of papers of European Summer Meeting of the Association for Symbolic Logic, Logic Colloquium'89, Berlin, JSL, 57 (1) 331.","journal-title":"JSL"},{"issue":"3","key":"3_CR21","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0003-4843(78)90011-6","volume":"15","author":"R. Statman","year":"1978","unstructured":"Statman, R. (1978) Bounds for proof-search and speed-up of the predicate calculus. Ann. Math. Logic, 15 (3), 225\u2013287.","journal-title":"Ann. Math. Logic"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Statman, R. (1979) Lower bounds on Herbrand's theorem, Proc. of the AMS, 75 (1).","DOI":"10.2307\/2042682"},{"key":"3_CR23","unstructured":"Troelstra, A.S. (1990) Remarks on intuitionism and the philosophy of mathematics (revised version), ITLI Prepublication Series X-90-01, University of Amsterdam, 18 pp."},{"key":"3_CR24","volume-title":"Constructivism in Mathematics. An introduction, Vol. I, II","author":"A.S. Troelstra","year":"1988","unstructured":"Troelstra, A.S. and van Dalen, D. (1988) Constructivism in Mathematics. An introduction, Vol. I, II, North-Holland, Amsterdam."},{"key":"3_CR25","unstructured":"Vardi, M.Y. (1982) The complexity of relational query languages, STOC'82, pp. 137\u2013146."},{"key":"3_CR26","unstructured":"Vopenka, P. (1979) Mathematics in the Alternative Set Theory, Leipzig."},{"key":"3_CR27","unstructured":"Yesenin-Volpin, A.S., (1959) Analysis of the potential feasibility, in: Logicheskije issledovanija, Moskwa, AN SSSR, 218\u2013262. (In Russian)."}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_78.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:55:45Z","timestamp":1605646545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_78","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}