{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T12:53:50Z","timestamp":1725886430631},"publisher-location":"Cham","reference-count":61,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319436678"},{"type":"electronic","value":"9783319436692"}],"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"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-43669-2_10","type":"book-chapter","created":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T06:14:07Z","timestamp":1493964847000},"page":"143-168","source":"Crossref","is-referenced-by-count":0,"title":["Complexity Barriers as Independence"],"prefix":"10.1007","author":[{"given":"Antonina","family":"Kolokolova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,6]]},"reference":[{"key":"10_CR1","first-page":"109","volume":"81","author":"S. Aaronson","year":"2003","unstructured":"S. Aaronson, Is P versus NP formally independent? Bull. Eur. Assoc. Theor. Comput. Sci. 81, 109\u2013136 (2003)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"S. Aaronson, A. Wigderson, Algebrization: a new barrier in complexity theory. ACM Trans. Comput. Theory 1 (1) (2009). Preliminary version in STOC\u201908","DOI":"10.1145\/1490270.1490272"},{"key":"10_CR3","doi-asserted-by":"publisher","unstructured":"M. Ajtai, \u03c3 1 1-formulae on finite structures. Ann. Pure Appl. Log. 24 (1), 1\u201348 (1983)","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"10_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S. Arora","year":"2009","unstructured":"S. Arora, B. Barak, Computational Complexity: A Modern Approach, 1st edn. (Cambridge University Press, New York, 2009)","edition":"1"},{"key":"10_CR5","unstructured":"S. Arora, S. Safra, Probabilistic checking of proofs: a new characterization of NP. J. Assoc. Comput. Mach. 45 (1), 70\u2013122 (1998). Preliminary version in FOCS\u201992"},{"key":"10_CR6","unstructured":"S. Arora, R. Impagliazzo, U. Vazirani, Relativizing versus nonrelativizing techniques: the role of local checkability. Manuscript (1992)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems. J. Assoc. Comput. Mach. 45 (3), 501\u2013555 (1998). Preliminary version in FOCS\u201992","DOI":"10.1145\/278298.278306"},{"key":"10_CR8","first-page":"30","volume-title":"E-mail and the unexpected power of interaction, in Proceedings, Fifth Annual Structure in Complexity Theory Conference, 1990","author":"L. Babai","year":"1990","unstructured":"L. Babai, E-mail and the unexpected power of interaction, in Proceedings, Fifth Annual Structure in Complexity Theory Conference, 1990 (IEEE, Barcelona, 1990), pp.\u00a030\u201344"},{"key":"10_CR9","volume-title":"Graph isomorphism in quasipolynomial time, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing","author":"L. Babai","year":"2016","unstructured":"L. Babai, Graph isomorphism in quasipolynomial time, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (2016)"},{"issue":"1","key":"10_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, C. Lund, Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1 (1), 3\u201340 (1991)","journal-title":"Comput. Complex."},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T.P. Baker","year":"1975","unstructured":"T.P. Baker, J. Gill, R. Solovay, Relativizations of the P=?NP question. SIAM J. Comput. 4 (4), 431\u2013442 (1975)","journal-title":"SIAM J. Comput."},{"key":"10_CR12","unstructured":"S. Ben-David, S. Halevi, On the Independence of P versus NP, Tech. Report 714, Technion (1992)"},{"issue":"1","key":"10_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"C.H. Bennett, J. Gill, Relative to a random Oracle A, P A \u2260 NP A \u2260 coNP A with probability 1. SIAM J. Comput. 10 (1), 96\u2013113 (1981)","journal-title":"SIAM J. Comput."},{"key":"10_CR14","volume-title":"Bounded Arithmetic","author":"S.R. Buss","year":"1986","unstructured":"S.R. Buss, Bounded Arithmetic (Bibliopolis, Naples, 1986)"},{"issue":"1","key":"10_CR15","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/S0022-0000(05)80084-4","volume":"49","author":"R. Chang","year":"1994","unstructured":"R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. H\u00e5stad, D. Ranjan, P. Rohatgi, The random oracle hypothesis is false. J. Comput. Syst. Sci. 49 (1), 24\u201339 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR16","first-page":"24","volume-title":"Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science","author":"A. Cobham","year":"1964","unstructured":"A. Cobham, The intrinsic computational difficulty of functions, in Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, ed. by Y.\u00a0Bar-Hillel (North-Holland, Amsterdam, 1964), pp.\u00a024\u201330"},{"key":"10_CR17","doi-asserted-by":"publisher","unstructured":"S.A. Cook, The complexity of theorem-proving procedures, in Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971), pp.\u00a0151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"10_CR18","doi-asserted-by":"publisher","unstructured":"S.A. Cook, A hierarchy for nondeterministic time complexity, in Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, STOC \u201872 (1972), pp.\u00a0187\u2013192","DOI":"10.1145\/800152.804913"},{"key":"10_CR19","doi-asserted-by":"publisher","unstructured":"S.A. Cook, Feasibly constructive proofs and the propositional calculus, in Proceedings of the Seventh Annual ACM Symposium on Theory of Computing (1975), pp.\u00a083\u201397","DOI":"10.1145\/800116.803756"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0168-0072(03)00056-3","volume":"124","author":"S.A. Cook","year":"2003","unstructured":"S.A. Cook, A. Kolokolova, A second-order system for polytime reasoning based on Gr\u00e4del\u2019s theorem. Ann. Pure Appl. Log. 124, 193\u2013231 (2003)","journal-title":"Ann. Pure Appl. Log."},{"key":"10_CR21","volume-title":"Logical foundations of proof complexity, in Perspectives in Logic of the Association for Symbolic Logic","author":"S.A. Cook","year":"2008","unstructured":"S.A. Cook, P. Nguyen, Logical foundations of proof complexity, in Perspectives in Logic of the Association for Symbolic Logic (Cambridge University Press, Cambridge, 2008)"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"10_CR23","unstructured":"L. Fortnow, The role of relativization in complexity theory. Bull. Eur. Assoc. Theor. Comput. Sci. 52, 229\u2013244 (1994). Columns: Structural Complexity"},{"issue":"7","key":"10_CR24","doi-asserted-by":"publisher","first-page":"135","DOI":"10.4086\/toc.2009.v005a007","volume":"5","author":"L. Fortnow","year":"2009","unstructured":"L. Fortnow, A simple proof of Toda\u2019s theorem. Theory Comput. 5 (7), 135\u2013140 (2009)","journal-title":"Theory Comput."},{"key":"10_CR25","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"L. Fortnow, M. Sipser, Are there interactive protocols for co-NP Languages? Inf. Process. Lett. 28, 249\u2013251 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10_CR26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J.B. Saxe, M. Sipser, Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17 (1), 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. Assoc. Comput. Mach. 38, 691\u2013729 (1991)","journal-title":"J. Assoc. Comput. Mach."},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, The Expressive Power of Second Order Horn Logic. Lecture Notes in Computer Science, vol.\u00a0480 (Springer, Heidelberg, 1991), pp.\u00a0466\u2013477","DOI":"10.1007\/BFb0020821"},{"key":"10_CR29","volume-title":"Metamathematics of first-order arithmetic, in Perspectives in Mathematical Logic","author":"P. H\u00e1jek","year":"1998","unstructured":"P. H\u00e1jek, P. Pudl\u00e1k, Metamathematics of first-order arithmetic, in Perspectives in Mathematical Logic (Springer, Berlin\/Heidelberg, 1998)"},{"issue":"4","key":"10_CR30","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1008335.1008336","volume":"8","author":"J. Hartmanis","year":"1976","unstructured":"J. Hartmanis, J.E. Hopcroft, Independence results in computer science. ACM SIGACT News 8 (4), 13\u201324 (1976)","journal-title":"ACM SIGACT News"},{"key":"10_CR31","unstructured":"J. Hartmanis, R.E. Stearns, Computational complexity of recursive sequences, in Proceedings of the Fifth Annual IEEE Symposium on Foundations of Computer Science (1964), pp.\u00a082\u201390"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis, R.E. Stearns, On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285\u2013306 (1965)","journal-title":"Trans. Am. Math. Soc."},{"key":"10_CR33","unstructured":"J. H\u00e5stad, Almost optimal lower bounds for small depth circuits, in Randomness and Computation, ed. by S.\u00a0Micali. Advances in Computing Research, vol.\u00a05 (JAI Press, Greenwich, 1989), pp.\u00a0143\u2013170"},{"issue":"4","key":"10_CR34","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F.C. Hennie","year":"1966","unstructured":"F.C. Hennie, R.E. Stearns, Two-tape simulation of multitape Turing machines. J. Assoc. Comput. Mach. 13 (4), 533\u2013546 (1966)","journal-title":"J. Assoc. Comput. Mach."},{"key":"10_CR35","unstructured":"R. Impagliazzo, V. Kabanets, A. Kolokolova, An axiomatic approach to algebrization (in preparation)"},{"key":"10_CR36","doi-asserted-by":"publisher","unstructured":"R. Impagliazzo, V. Kabanets, A. Kolokolova, An axiomatic approach to algebrization, in Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (2009), pp.\u00a0695\u2013704","DOI":"10.1145\/1536414.1536509"},{"key":"10_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.apal.2003.12.003","volume":"129","author":"E. Je\u0159\u00e1bek","year":"2004","unstructured":"E. Je\u0159\u00e1bek, Dual weak pigeonhole principle, Boolean complexity, and derandomization. Ann. Pure Appl. Log. 129, 1\u201337 (2004)","journal-title":"Ann. Pure Appl. Log."},{"issue":"3","key":"10_CR38","doi-asserted-by":"publisher","first-page":"959","DOI":"10.2178\/jsl\/1191333850","volume":"72","author":"E. Je\u0159\u00e1bek","year":"2007","unstructured":"E. Je\u0159\u00e1bek, Approximate counting in bounded arithmetic. J. Symb. Log. 72 (3), 959\u2013993 (2007)","journal-title":"J. Symb. Log."},{"issue":"3","key":"10_CR39","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1093\/logcom\/exm017","volume":"17","author":"E. Je\u0159\u00e1bek","year":"2007","unstructured":"E. Je\u0159\u00e1bek, On independence of variants of the weak pigeonhole principle. J. Log. Comput. 17 (3), 587\u2013604 (2007)","journal-title":"J. Log. Comput."},{"issue":"3","key":"10_CR40","doi-asserted-by":"publisher","first-page":"829","DOI":"10.2178\/jsl\/1245158087","volume":"74","author":"E. Je\u0159\u00e1bek","year":"2009","unstructured":"E. Je\u0159\u00e1bek, Approximate counting by hashing in bounded arithmetic. J. Symb. Log. 74 (3), 829\u2013860 (2009)","journal-title":"J. Symb. Log."},{"issue":"1","key":"10_CR41","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00037-009-0263-7","volume":"18","author":"A. Juma","year":"2009","unstructured":"A. Juma, V. Kabanets, C. Rackoff, A. Shpilka, The black-box query complexity of polynomial summation. Comput. Complex. 18 (1), 59\u201379 (2009)","journal-title":"Comput. Complex."},{"issue":"2","key":"10_CR42","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1093\/logcom\/exq008","volume":"22","author":"A. Kolokolova","year":"2012","unstructured":"A. Kolokolova, Expressing versus proving: relating forms of complexity in logic. J. Log. Comput. 22 (2), 267\u2013280 (2012)","journal-title":"J. Log. Comput."},{"key":"10_CR43","volume-title":"Bounded arithmetic, propositional logic and complexity theory, in Encyclopedia of Mathematics and Its Applications","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"J. Kraj\u00ed\u010dek, Bounded arithmetic, propositional logic and complexity theory, in Encyclopedia of Mathematics and Its Applications (Cambridge University Press, Cambridge, 1995)"},{"key":"10_CR44","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"L. Levin, Universal sorting problems. Problems. Inf. Transm. 9, 265\u2013266 (1973)","journal-title":"Problems. Inf. Transm."},{"issue":"4","key":"10_CR45","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"C. Lund, L. Fortnow, H. Karloff, N. Nisan, Algebraic methods for interactive proof systems. J. Assoc. Comput. Mach. 39 (4), 859\u2013868 (1992)","journal-title":"J. Assoc. Comput. Mach."},{"key":"10_CR46","doi-asserted-by":"publisher","first-page":"494","DOI":"10.2307\/2269958","volume":"36","author":"R. Parikh","year":"1971","unstructured":"R. Parikh, Existence and feasibility of arithmetic. J. Symb. Log. 36, 494\u2013508 (1971)","journal-title":"J. Symb. Log."},{"key":"10_CR47","doi-asserted-by":"publisher","unstructured":"P. Pudl\u00e1k, Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction. Springer Monographs in Mathematics (Springer, New York, 2013)","DOI":"10.1007\/978-3-319-00119-7"},{"key":"10_CR48","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/oso\/9780198536901.003.0012","volume-title":"Arithmetic, Proof Theory and Computational Complexity","author":"A.A. Razborov","year":"1993","unstructured":"A.A. Razborov, An equivalence between second-order bounded domain bounded arithmetic and first-order bounded arithmetic, in Arithmetic, Proof Theory and Computational Complexity, ed. by P. Clote, J. Kraj\u00ed\u010dek (Clarendon Press, Oxford, 1993), pp.\u00a0247\u2013277"},{"key":"10_CR49","first-page":"344","volume-title":"Bounded arithmetic and lower bounds in boolean complexity, in Feasible Mathematics II","author":"A.A. Razborov","year":"1995","unstructured":"A.A. Razborov, Bounded arithmetic and lower bounds in boolean complexity, in Feasible Mathematics II (Springer, New York, 1995), pp.\u00a0344\u2013386"},{"issue":"1","key":"10_CR50","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1070\/IM1995v059n01ABEH000009","volume":"59","author":"A.A. Razborov","year":"1995","unstructured":"A.A. Razborov, Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izv. Math. 59 (1), 205\u2013227 (1995)","journal-title":"Izv. Math."},{"key":"10_CR51","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razborov","year":"1997","unstructured":"A.A. Razborov, S. Rudich, Natural proofs. J. Comput. Syst. Sci. 55, 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR52","doi-asserted-by":"publisher","unstructured":"R. Santhanam, Circuit lower bounds for Merlin-Arthur classes, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (2007), pp.\u00a0275\u2013283","DOI":"10.1145\/1250790.1250832"},{"issue":"2","key":"10_CR53","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"W.J. Savitch, Relationships between nondeterministic and deterministic space complexities. J. Comput. Syst. Sci. 4 (2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10_CR54","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"A. Shamir, IP=PSPACE. J. Assoc. Comput. Mach. 39 (4), 869\u2013877 (1992)","journal-title":"J. Assoc. Comput. Mach."},{"key":"10_CR55","doi-asserted-by":"publisher","unstructured":"R.E. Stearns, J. Hartmanis, P.M. Lewis\u00a0II, Hierarchies of memory limited computations, in SWCT (FOCS) (1965), pp.\u00a0179\u2013190","DOI":"10.1109\/FOCS.1965.11"},{"key":"10_CR56","unstructured":"L.J. Stockmeyer, The complexity of decision problems in automata theory and logic, Ph.D. thesis, Massachusetts Institute of Technology, 1974"},{"key":"10_CR57","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1093\/oso\/9780198536901.003.0016","volume-title":"Arithmetic, Proof Theory and Computational Complexity","author":"G. Takeuti","year":"1993","unstructured":"G. Takeuti, RSUV isomorphism, in Arithmetic, Proof Theory and Computational Complexity, ed. by P. Clote, J. Kraj\u00ed\u010dek (Clarendon Press, Oxford, 1993), pp.\u00a0364\u2013386"},{"issue":"5","key":"10_CR58","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda, PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20 (5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"key":"10_CR59","unstructured":"A.M. Turing, Systems of logic based on ordinals, in Proceedings of the London Mathematical Society. Second Series, vol.\u00a045 (1939), pp.\u00a0161\u2013228"},{"key":"10_CR60","unstructured":"P. van Emde\u00a0Boas, Turing machines for dummies\u2014why representations do matter, in SOFSEM (2012), pp.\u00a014\u201330"},{"key":"10_CR61","doi-asserted-by":"publisher","unstructured":"R. Williams, Nonuniform ACC circuit lower bounds. J. ACM 61 (1), 2 (2014)","DOI":"10.1145\/2559903"}],"container-title":["Theory and Applications of Computability","The Incomputable"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-43669-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,23]],"date-time":"2024-06-23T23:16:54Z","timestamp":1719184614000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-43669-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319436678","9783319436692"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-43669-2_10","relation":{},"ISSN":["2190-619X","2190-6203"],"issn-type":[{"type":"print","value":"2190-619X"},{"type":"electronic","value":"2190-6203"}],"subject":[],"published":{"date-parts":[[2017]]}}}