{"entities":{"Q580175":{"pageid":581942,"ns":120,"title":"Item:Q580175","lastrevid":49092058,"modified":"2026-01-06T14:16:50Z","type":"item","id":"Q580175","labels":{"en":{"language":"en","value":"On the complexity of cutting-plane proofs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016594"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$EC08C2DD-9313-4B6D-A6D5-80F592CC21E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bf7f6f9d05292d7f8f5d3ef70daf7e709355b59f","datavalue":{"value":{"text":"On the complexity of cutting-plane proofs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q580175$74108FB7-3BD4-48F7-A7C2-1F10D516B5F4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5da6769267a737d189d82eb1fc4c7ef78e199102","datavalue":{"value":"0625.90056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580175$D5381123-E4DD-451E-8E7F-C3FE225EE72B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"96b5ebedb5135fdf302329b338d34323a0106688","datavalue":{"value":"10.1016/0166-218X(87)90039-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580175$86CBDCD2-A991-4D82-858B-D1C60F7064DA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c66a437d74ae466cacad614cef92f8e5d71204e6","datavalue":{"value":{"entity-type":"item","numeric-id":239429,"id":"Q239429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$0416E3D6-82F3-4F76-A78E-634B4EE11F42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"39fa6a381924a014b9e21aa8cbb5f54740e98a79","datavalue":{"value":{"entity-type":"item","numeric-id":744211,"id":"Q744211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$508953D3-EBF3-4B28-A7AB-87DE2DCEDED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c129f4888c20470ec7508e6617afd6aa87b5ce40","datavalue":{"value":{"entity-type":"item","numeric-id":751504,"id":"Q751504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$8BDBD848-D813-4761-924E-37216EBA8189","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$BC9707C9-FF4D-4866-8998-1707D3246A2B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q580175$A75497B9-7F22-404C-8747-D3F270557E8A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9245ce51c6ef52cfcb6b46e0173ac2638ffb3b57","datavalue":{"value":"As introduced by \\textit{V. Chvatal} [Discrete Math. 4, 305-337 (1973; Zbl 0253.05131)] cutting planes provide a canonical way of proving that every integral solution of a given system of linear inequalities satisfies another specified inequality. In this note we make several observations on the complexity of such proofs in general and when restricted to provide the unsatisfiability of formulae in the propositional calculus.","type":"string"},"datatype":"string"},"type":"statement","id":"Q580175$A4AB4849-A1F5-4406-A6D7-72F9A4D1A4CD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580175$515907A5-9C38-4CBB-A4C1-CED2A69BF96C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580175$BC2BA04B-738E-4156-A499-280D734C9346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580175$EFE5C4F6-FB3E-4832-B583-B0B6B7BE9B2E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ead3017a26e6e3c6aabaeed7fe8866c33ec5f696","datavalue":{"value":"4016594","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580175$4AE6CF11-FE75-46A1-9008-2AE2D50E3AB7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5db0ad225cd2c306f6fb47a3099e383146746038","datavalue":{"value":"complexity of cutting-plane proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q580175$420AD434-A038-41A5-A606-098C3D9B40BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cb92aeecbf00e239d7159360d87ee92ae282861","datavalue":{"value":"integral solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q580175$794287D9-96CF-4670-B9ED-8BA62AF9159F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"780aa31aabe63e350d953e44e392b588d88bd8b1","datavalue":{"value":"system of linear inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q580175$44CDDCA1-C053-49C4-B455-F12A2B7AB8CD","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$A24113E9-48DA-4892-A7F0-0BA9CAB246A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"50cfad429314e1605f6ade5a2c59b3e9f12f443e","datavalue":{"value":{"entity-type":"item","numeric-id":1076512,"id":"Q1076512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$33F0F05B-4611-4FC1-91EE-949A58633E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b52d0e09120391f1d21c6bdfdf55f135dcce6c1f","datavalue":{"value":{"entity-type":"item","numeric-id":4170530,"id":"Q4170530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$875922B4-B333-4DB9-A2C5-F1519F6CF208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6023f8076a9f82218c7e12475fb91bd59480856","datavalue":{"value":{"entity-type":"item","numeric-id":2971603,"id":"Q2971603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$623AE10E-8458-4682-B42D-032135470186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b8154126bb7dcff376a3fb5230eefc60388d66","datavalue":{"value":{"entity-type":"item","numeric-id":5652222,"id":"Q5652222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$19820A10-C0BA-4000-B9CC-46BC6A592E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa9316bc21130945e76158a0803667b9b47faaef","datavalue":{"value":{"entity-type":"item","numeric-id":2557712,"id":"Q2557712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$0211E5AA-DD14-4A93-96BF-86BAE1928526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2efdce0fdc040cf654e2a84802c55bcebe88632","datavalue":{"value":{"entity-type":"item","numeric-id":5685112,"id":"Q5685112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$13B97E24-900D-47A2-A4EF-526BA7081B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d78aebc03382f2bd4411dc4c5ad65fcd17d42f5","datavalue":{"value":{"entity-type":"item","numeric-id":4177607,"id":"Q4177607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$8E66A35D-7D38-4E13-A5B1-F6DBBEFF9ED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b94cde8ebd60fd481ae822a3fd5992b434b36c25","datavalue":{"value":{"entity-type":"item","numeric-id":1068092,"id":"Q1068092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$EE46F894-5222-415F-917B-30C57BE62F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a549ed1d776396be3e4308655e166de224ba89","datavalue":{"value":{"entity-type":"item","numeric-id":4133141,"id":"Q4133141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$FB162F70-9874-4039-942A-AC52157473A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bea75da9fa67a5f77faa9362cd4aa6c737c792a","datavalue":{"value":{"entity-type":"item","numeric-id":4194955,"id":"Q4194955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$65A0F758-22CB-40A4-B7CC-A9E23457A01B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e86f696cea8930253e0ba8a16b8bef20f6a7f17","datavalue":{"value":{"entity-type":"item","numeric-id":3793940,"id":"Q3793940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$6358DF8E-505B-4F33-B4D3-5D5C7782506C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"625529be9cbb76c2b436d7af2d11d74a8f6bffaf","datavalue":{"value":{"entity-type":"item","numeric-id":5402564,"id":"Q5402564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$9B458BAE-64A4-4D92-9B30-0FC9F5A6CCBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebea33f2e693df44f0638331ccbcd56f31e0d6f8","datavalue":{"value":{"entity-type":"item","numeric-id":5645210,"id":"Q5645210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$D0DCE931-D920-433A-99E8-11299CDFEFC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b03c46dfc7b75e41a2df8bca90ca883242552b78","datavalue":{"value":{"entity-type":"item","numeric-id":768371,"id":"Q768371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$C6076E49-B22F-404B-88E7-403CBF23F3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec2fa04d400281f100817ce7e13bdaafd2683670","datavalue":{"value":{"entity-type":"item","numeric-id":1071750,"id":"Q1071750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$7BF6C104-584F-4D80-9B38-090D4E5020CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a4709e61495201737f4eba392124a3a98ba41a8","datavalue":{"value":{"entity-type":"item","numeric-id":4189049,"id":"Q4189049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$9E06FA1E-64F0-4252-BA6D-6897097471EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b369429581047e1dabd46e6eafe270ef5ac985","datavalue":{"value":{"entity-type":"item","numeric-id":3037135,"id":"Q3037135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$045FE00E-D7F4-4020-AEC8-CEA1A2DF2C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92a3e9debcab806c14aff8e499e51be47c884542","datavalue":{"value":{"entity-type":"item","numeric-id":3745276,"id":"Q3745276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$4815020D-B6E8-4C52-927A-E5ABEAACFD99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62ebef9379ad97d2bdc3c2e7f5717f221d056cb","datavalue":{"value":{"entity-type":"item","numeric-id":5514129,"id":"Q5514129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$84A74764-76BD-4B9E-B74A-3F0BB8DC6052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"527920fc408f387b501ad5e37205a5ae6fc14b7a","datavalue":{"value":{"entity-type":"item","numeric-id":4161089,"id":"Q4161089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$7A19A68A-33DE-4053-B544-05752D0A7119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ef272d96a58799915f8a0b53fe2d5749a3e79a6","datavalue":{"value":{"entity-type":"item","numeric-id":3883904,"id":"Q3883904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$18EAFDAD-DB59-4731-8C54-AFAD92EB4732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$0F946484-733F-4A51-A7B0-F5E0D28168C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e98bea2faf0f1e7139247049b725eb54de257627","datavalue":{"value":{"entity-type":"item","numeric-id":5593816,"id":"Q5593816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580175$E7BBE86A-D0FF-44BC-ADB7-94AE58D54F62","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"156847d7386a9bfeae5e07aa400f03355c0c39ba","datavalue":{"value":"https://doi.org/10.1016/0166-218x(87)90039-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q580175$D736E372-9335-4391-ACC0-76413D124BF3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08d6654a6fdfcaf44802522607240947dd303582","datavalue":{"value":"W2038193643","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580175$B5FB6E0D-047C-4799-9F0B-96EF0ABB48C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99ce90f53827001ef14b5751ceb40b9ee8a355be","datavalue":{"value":{"entity-type":"item","numeric-id":4281687,"id":"Q4281687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5f1cfef6cac9e122449a2af9c01ad47c9603044","datavalue":{"value":{"amount":"+0.8649435043334961","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q580175$173F4B65-3C61-4B08-BB0A-8550F064D860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9beb2689392e607bfa4d1a42dff7641e3736a43","datavalue":{"value":{"entity-type":"item","numeric-id":1898117,"id":"Q1898117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5f1cfef6cac9e122449a2af9c01ad47c9603044","datavalue":{"value":{"amount":"+0.8649435043334961","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q580175$EA086CDF-5D29-4C6B-A303-36A9098541BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7aaabe75ac40230053c43c100bda99f2a88fd5ea","datavalue":{"value":{"entity-type":"item","numeric-id":1813835,"id":"Q1813835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c100104bc6849b5972c7410373a879e8494d370a","datavalue":{"value":{"amount":"+0.8538439273834229","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q580175$7E6F16D5-B90D-45E4-8662-8EED13BB1E78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc885c023182d4d76c9909ba3e107db4a2c793f3","datavalue":{"value":{"entity-type":"item","numeric-id":3569838,"id":"Q3569838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c25ae0579ef5158cc8aace58216c1b81a490091","datavalue":{"value":{"amount":"+0.8427679538726807","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q580175$00CBF23A-9BFF-4E18-8225-EB33F3996E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfe68199cf01e3dcb6a7ce52d5f30175da480ac7","datavalue":{"value":{"entity-type":"item","numeric-id":4601841,"id":"Q4601841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cc22dc1d90dd23f9ce52a4e42daa80d1dcc001c","datavalue":{"value":{"amount":"+0.8343579769134521","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q580175$FA55AB0F-8A2F-48A8-804F-EF51438F7174","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:580175","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:580175"}}}}}