{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T12:46:04Z","timestamp":1778589964613,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"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":[[1996,1]]},"DOI":"10.1007\/bf01845704","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T17:25:13Z","timestamp":1119979513000},"page":"33-62","source":"Crossref","is-referenced-by-count":21,"title":["Cutting planes, connectivity, and threshold logic"],"prefix":"10.1007","volume":"35","author":[{"given":"Samuel R.","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Clote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01845704_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4612-3466-1_1","volume-title":"Feasible Mathematics","author":"M. Ajtai","year":"1990","unstructured":"Ajtai, M.: Parity and the pigeonhole principle. In: Buss, S.R., Scott, P.J. (eds.) Feasible Mathematics, pp. 1\u201324. Basel: Birkh\u00e4user 1990"},{"key":"BF01845704_CR2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"Ajtai, M., Fagin, R.: Reachability is harder for directed than for undirected finite graphs. J. Symb. Logic55: 113\u2013150 (1990)","journal-title":"J. Symb. Logic"},{"key":"BF01845704_CR3","first-page":"200","volume-title":"Proceedings of the 24th Annual ACM Symposium on Theory of Computing","author":"P. Beame","year":"1992","unstructured":"Beame, P., Impagliazzo, R., Kraj\u00ed\u010dek, J., Pitassi, T., Pudl\u00e1k, P., Woods, A.: Exponential lower bounds for the pigeonhole principle. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 200\u2013220. New York: Association for Computing Machinery 1992"},{"key":"BF01845704_CR4","series-title":"Proceeding of the 27th ACM Symposium on Theory of Computing","first-page":"303","volume-title":"The relative complexity of NP search problems","author":"P. Beame","year":"1995","unstructured":"Beame, P., Cook, S., Papadimitriou, C., Pitassi, T.: The relative complexity of NP search problems. Proceeding of the 27th ACM Symposium on Theory of Computing, pp. 303\u2013314. New York: Association for Computing Machinery 1995"},{"key":"BF01845704_CR5","doi-asserted-by":"crossref","first-page":"916","DOI":"10.2307\/2273826","volume":"52","author":"S. Buss","year":"1987","unstructured":"Buss, S.: The propositional pigeonhole principle has polynomial size Frege proofs. J. Symb. Logic52: 916\u2013927 (1987)","journal-title":"J. Symb. Logic"},{"key":"BF01845704_CR6","unstructured":"Buss, S., Clote, P.: Threshold logic proof systems. Manuscript (May 1995)"},{"key":"BF01845704_CR7","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(88)90072-2","volume":"62","author":"S. Buss","year":"1988","unstructured":"Buss, S., Tur\u00e1n, G.: Resolution proofs of generalized pigeonhole principles. Theor. Comput. Sci.62: 311\u2013317 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"BF01845704_CR8","volume-title":"Arithmetic, Proof Theory and Computational Complexity","year":"1993","unstructured":"Clote, P., Kraj\u00ed\u010dek, J. (eds.): Arithmetic, Proof Theory and Computational Complexity, 428 p. Oxford: Oxford University Press 1993"},{"key":"BF01845704_CR9","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1109\/LICS.1992.185542","volume-title":"Proceedings of 7th Annual IEEE Symposium on Logic in Computer Science","author":"P. Clote","year":"1992","unstructured":"Clote, P.: Cutting planes and constant depth Frege proofs. In: Proceedings of 7th Annual IEEE Symposium on Logic in Computer Science, pp. 296\u2013307. Piscataway, NJ: IEEE Computer Science Press 1992"},{"key":"BF01845704_CR10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1995.1126","volume":"121","author":"P. Clote","year":"1995","unstructured":"Clote, P.: Cutting plane and Frege proofs. Inf. Comput.121: 103\u2013122 (1995)","journal-title":"Inf. Comput."},{"key":"BF01845704_CR11","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1977","unstructured":"Cook, S.A., Reckhow, R.: On the relative efficiency of propositional proof systems. J. Symb. Logic44: 36\u201350 (1977)","journal-title":"J. Symb. Logic"},{"key":"BF01845704_CR12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"Cook, W., Coullard, C.R., Turan, G.: On the complexity of cutting plane proofs. Discr. Appl. Math.18: 25\u201338 (1987)","journal-title":"Discr. Appl. Math."},{"key":"BF01845704_CR13","series-title":"Lecture Notes in Computer Science","first-page":"174","volume-title":"Computer Science Logic 1990, vol. 552","author":"A. Goerdt","year":"1992","unstructured":"Goerdt, A.: Cutting plane versus Frege proof systems. In: B\u00f6rger, E. (ed.) Computer Science Logic 1990, vol. 552, pp 174\u2013194. Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer 1992"},{"key":"BF01845704_CR14","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"Haken, A.: The intractability of resolution. Theor. Comput. Sci.39: 297\u2013305 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"BF01845704_CR15","volume-title":"An Introduction to the Theory of Numbers","author":"G.H. Hardy","year":"1979","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford: Clarendon Press 1979","edition":"5th edn."},{"key":"BF01845704_CR16","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1109\/LICS.1994.316069","volume-title":"Proceedings of 9th Annual IEEE Symposium on Logic in Computer Science","author":"R. Impagliazzo","year":"1994","unstructured":"Impagliazzo, R., Pitassi, T., Urquhart, A.: Upper and lower bounds for tree-like cutting planes proofs. In: Proceedings of 9th Annual IEEE Symposium on Logic in Computer Science, pp. 220\u2013228. Piscataway, NJ: IEEE Computer Science Press 1994"},{"key":"BF01845704_CR17","first-page":"284","volume-title":"Feasible Mathematics, vol. II","author":"J. Kraj\u00ed\u010dek","year":"1994","unstructured":"Kraj\u00ed\u010dek, J.: On Frege and extended Frege systems. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics, vol. II, pp. 284\u2013319. Basel: Birkh\u00e4user 1994"},{"key":"BF01845704_CR18","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci.48:498\u2013532 (1994)","journal-title":"J. Comput. System Sci."},{"key":"BF01845704_CR19","volume-title":"Combinatorial Optimization","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization. London: Prentice-Hall 1982"},{"key":"BF01845704_CR20","series-title":"Lecture Notes in Mathematics","first-page":"317","volume-title":"Methods in Mathematical Logic","author":"J.B. Paris","year":"1983","unstructured":"Paris, J.B., Wilkie, A.J.: Counting problems in bounded arithmetic. In: di Prisco, C.A. (ed.) Methods in Mathematical Logic, pp. 317\u2013340. Lecture Notes in Mathematics 1130. Berlin Heidelberg New York: Springer 1983"},{"key":"BF01845704_CR21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/7531.8928","volume":"34","author":"A. Urquhart","year":"1987","unstructured":"Urquhart, A.: Hard examples for resolution. J. Assoc. Comput. Machinery34: 209\u2013219 (1987)","journal-title":"J. Assoc. Comput. Machinery"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01845704.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01845704\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01845704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T17:04:29Z","timestamp":1557421469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01845704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["BF01845704"],"URL":"https:\/\/doi.org\/10.1007\/bf01845704","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}