{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T12:05:56Z","timestamp":1749125156285},"publisher-location":"Berlin\/Heidelberg","reference-count":18,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354010027X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0022533","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T00:49:12Z","timestamp":1132706952000},"page":"562-575","source":"Crossref","is-referenced-by-count":12,"title":["A logical approach to the problem \u201cP=NP?\u201d"],"prefix":"10.1007","author":[{"given":"V. Yu.","family":"Sazonov","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Cook, S.A., The Complexity of Theorem Proving Procedures, Conf. Record of 3rd ACM Symposium on Theory of Computing, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Feasibly Constructive Proofs and the Propositional Calculus, 17th Ann.Symp. on Theory of Computing, Conf. Record, May 1975, 83\u201397.","DOI":"10.1145\/800116.803756"},{"key":"42_CR3","first-page":"748","volume":"189","author":"M.I. Dekhtjar'","year":"1969","unstructured":"Dekhtjar', M.I., On the impossibility to eliminate the complete enumeration under the computation of functions relatively to their graphs, Doklady Akad.Nauk SSSR, v. 189, 1969, 748\u2013751 (in Russian).","journal-title":"Doklady Akad.Nauk SSSR"},{"key":"42_CR4","first-page":"218","volume-title":"An analysis of potential feasibility, Logiceskije issledovanija","author":"A.S. Yesenin-Volpin","year":"1959","unstructured":"Yesenin-Volpin, A.S., An analysis of potential feasibility, Logiceskije issledovanija, Akad.Nauk SSSR, Moscow, 1959, 218\u2013262 (in Russian)."},{"key":"42_CR5","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"Fagin, R., Generalized First-Order Spectra and Polynomial Time Recognizable sets, Complexity of Computations, SIAM-AMS Proc., vol.7, 1974, 43\u201373.","journal-title":"SIAM-AMS Proc."},{"issue":"4","key":"42_CR6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1008335.1008336","volume":"8","author":"J. Hartmanis","year":"1976","unstructured":"Hartmanis, J., Hopcroft, J.E., Independence Result in Computer Science, ACM SIGACT News, 8 (1976), No 4, 3\u201324.","journal-title":"ACM SIGACT News"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Jones, N.D., Selman, A.L., Turing Machines and the Spectra of First-Order Formulas with Equality, Proc. 4th ACM Symp. on Theory of Computing, 1972, 157\u2013167.","DOI":"10.1145\/800152.804909"},{"key":"42_CR8","first-page":"115","volume":"3","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A., Universal Enumeration Tasks, Problemy Peredaci Informacii, IX, 3, 1973, 115\u2013116 (in Russian).","journal-title":"Problemy Peredaci Informacii, IX"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Lipton, R., Model Theoretic Aspects of Computational Complexity, Proc. of the 1978 FOCS Symposium, 193\u2013200 (1978).","DOI":"10.1109\/SFCS.1978.23"},{"key":"42_CR10","doi-asserted-by":"crossref","unstructured":"De Millo, R.A., Lipton, R.J., Some connections between mathematical Logic and Complexity Theory, Proc. of the 1979 STOC, 153\u2013159 (1979).","DOI":"10.21236\/ADA071719"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"O'Donnell, M., A Programming Language Theorem which is Independent of Peano Arithmetic, Proc. of the 1979 STOC, 176\u2013188 (1979).","DOI":"10.1145\/800135.804411"},{"issue":"3","key":"42_CR12","doi-asserted-by":"crossref","first-page":"494","DOI":"10.2307\/2269958","volume":"36","author":"K. Parikh","year":"1971","unstructured":"Parikh, K., Existence and Feasibility in Arithmetic, the Journal of Symbolic Logic, vol. 36, No 3, 1971, 494\u2013508.","journal-title":"the Journal of Symbolic Logic"},{"key":"42_CR13","first-page":"133","volume-title":"Theory in which lower exponential complexity bound for NP complete tasks is unprovable, 5th All-Union Conf. on math. logic","author":"V. Y. Sazonov","year":"1979","unstructured":"Sazonov, V. Yu., Theory in which lower exponential complexity bound for NP complete tasks is unprovable, 5th All-Union Conf. on math. logic, Institute of Mathem., Novosibirsk, 1979, p. 133 (in Russian)."},{"key":"42_CR14","unstructured":"Sazonov, V.Yu., Polynomial computability and recursivity in finite domains, to be published."},{"issue":"4","key":"42_CR15","first-page":"569","volume":"70","author":"B.A. Trakhtenbrot","year":"1950","unstructured":"Trakhtenbrot, B.A., The impossibility of an algorithm for the decidability problem on finite classes, Doklady AN SSSR, 70, No 4 (1950), 569\u2013572 (in Russian).","journal-title":"Doklady AN SSSR"},{"key":"42_CR16","doi-asserted-by":"crossref","unstructured":"Trakhtenbrot, B.A., The formalization of some notions in terms of the complexity of computations, P. Suppes et al., eds., Logic, Methodology and Philosophy of Sciences IV, North-Holl., 1973, 205\u2013213 (in Russian).","DOI":"10.1016\/S0049-237X(09)70359-3"},{"key":"42_CR17","unstructured":"Takeuti, G., Proof Theory, North-Holland, 1975."},{"key":"42_CR18","first-page":"75","volume":"2","author":"S.V. Yablonsky","year":"1959","unstructured":"Yablonsky, S.V., On the algorithmic difficulties of minimal schemes synthesis, Problemy Kybernetiki, 2, 1959, Moscow, 75\u2013121 (in Russian).","journal-title":"Problemy Kybernetiki"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1980"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0022533","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T00:21:50Z","timestamp":1586564510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022533"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354010027X"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0022533","relation":{},"subject":[]}}