{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T20:16:15Z","timestamp":1648671375519},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2005,5,3]],"date-time":"2005-05-03T00:00:00Z","timestamp":1115078400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2005,8]]},"DOI":"10.1007\/s00153-005-0279-x","type":"journal-article","created":{"date-parts":[[2005,5,2]],"date-time":"2005-05-02T10:41:48Z","timestamp":1115030508000},"page":"667-675","source":"Crossref","is-referenced-by-count":1,"title":["Hardness assumptions in the foundations of theoretical computer science"],"prefix":"10.1007","volume":"44","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,3]]},"reference":[{"key":"279_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Pseudorandom generators in propositional proof complexity, Ext. abstract. In: Proc. of the 41st Annual Symp. on Foundation of Computer Science, 2000, pp.43\u201353","DOI":"10.1109\/SFCS.2000.892064"},{"key":"279_CR2","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proc. 3rd Annual ACM Symp. on Theory of Computing, ACM Press, 1971, pp. 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"279_CR3","unstructured":"Cook, S. A.: Feasibly constructive proofs and the propositional calculus. In: Proc. 7th Annual ACM Symp. on Theory of Computing, ACM Press, 1975, pp. 83\u201397"},{"key":"279_CR4","unstructured":"Cook, S. A.: The P versus NP problem, at: http:\/\/www.claymath.org\/ prizeproblems\/pvsnp.htm"},{"key":"279_CR5","first-page":"1979","volume":"44","author":"Cook","year":"1","unstructured":"Cook, S.A., Reckhow, A.R.: The relative efficiency of propositional proof systems, J. Symbolic Logic, 44 (1), 1979, pp.36\u201350","journal-title":"Symbolic Logic,"},{"key":"279_CR6","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Foundations of Cryptography, Vol.1, Cambridge University Press, (2001)","DOI":"10.1017\/CBO9780511546891"},{"key":"279_CR7","doi-asserted-by":"crossref","unstructured":"Hastad, J., Impagliazzo, R., Levin, L., Luby, M.: A Pseudorandom Generator from any one-way function, SIAM Journal on Computing, vol. 28, 1999, pp 1364\u20131396","DOI":"10.1137\/S0097539793244708"},{"key":"279_CR8","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP unless E has sub-exponential circuits: derandomizing the XOR lemma. In: Proc. of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 220\u2013229"},{"key":"279_CR9","unstructured":"Kraj\u00ed\u010dek, J.: Bounded arithmetic, propositional logic, and complexity theory, Encyclopedia of Mathematics and Its Applications, vol. 60, Cambridge University Press, (1995)."},{"key":"279_CR10","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek, J.: On the weak pigeonhole principle, Fundamenta Mathematicae, vol. 170 (1\u20133), 2001, pp.123\u2013140","DOI":"10.4064\/fm170-1-8"},{"key":"279_CR11","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek, J.: Tautologies from pseudo-random generators, Bulletin of Symbolic Logic, 7 (2), (2001), pp.197\u2013212","DOI":"10.2307\/2687774"},{"key":"279_CR12","first-page":"2004","volume":"69","author":"Kraj\u00ed\u010dek","year":"1","unstructured":"Kraj\u00ed\u010dek, J.: Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds, J. of Symbolic Logic, 69 (1), 2004, pp. 265\u2013286","journal-title":"of Symbolic Logic,"},{"key":"279_CR13","first-page":"1989","volume":"54","author":"Kraj\u00ed\u010dek","year":"3","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations, J. Symbolic Logic, 54 (3), 1989, pp. 1063\u20131079","journal-title":"Symbolic Logic,"},{"key":"279_CR14","unstructured":"Levin, L.: Universal Search Problems (in Russian), Problems of Information Transmission, 9 (3), 1973, pp. 265\u2013266"},{"key":"279_CR15","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: Resolution lower bounds for perfect matching principles, In: Proc. of the 17th IEEE Conf. on Computational Complexity, 2002, pp. 29\u201338","DOI":"10.1109\/CCC.2002.1004336"},{"key":"279_CR16","unstructured":"Razborov, A.A.: Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution, preprint, December\u201902"},{"key":"279_CR17","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring, In: Proc. 35nd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1994, pp. 124\u2013134","DOI":"10.1109\/SFCS.1994.365700"},{"key":"279_CR18","doi-asserted-by":"crossref","unstructured":"Sipser, M.: The history and status of the P versus NP question, In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ACM Press, 1992, pp. 603\u2013618","DOI":"10.1145\/129712.129771"},{"key":"279_CR19","first-page":"1998","volume":"20","author":"Smale","year":"2","unstructured":"Smale, S.: Mathematical Problems for the Next Century, Math. Intelligencer, 20 (2), 1998, pp. 7\u201315","journal-title":"Intelligencer,"},{"key":"279_CR20","unstructured":"Yao, A.C.-C.: Classical Physics and the Church-Turing Thesis, ECCC:http:\/\/www.eccc.uni-trier.de\/eccc-local\/Lists\/TR-2002.html TR02-062."}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-005-0279-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00153-005-0279-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-005-0279-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T19:36:40Z","timestamp":1558640200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00153-005-0279-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,3]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2005,8]]}},"alternative-id":["279"],"URL":"https:\/\/doi.org\/10.1007\/s00153-005-0279-x","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5,3]]}}}