{"entities":{"Q2498920":{"pageid":2509663,"ns":120,"title":"Item:Q2498920","lastrevid":73275354,"modified":"2026-04-14T15:14:31Z","type":"item","id":"Q2498920","labels":{"en":{"language":"en","value":"Several notes on the power of Gomory-Chv\u00e1tal cuts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5047237"}},"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":"Q2498920$30BD0A23-8284-4A7D-8263-A2A0CB8312CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"220994ba517bce42120fa90d5a374cc8fe79a731","datavalue":{"value":{"text":"Several notes on the power of Gomory-Chv\u00e1tal cuts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2498920$F1447D8C-C93E-4F99-8E98-462A60A8EC9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9464785b45361baa6661ce2e002b2ebbf5f10e6b","datavalue":{"value":"1101.03037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2498920$DB52ADC6-D56C-4BBD-8E6D-232F148346D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"082fc9f964d52bb224385bf2fb43b8343199b054","datavalue":{"value":{"entity-type":"item","numeric-id":234710,"id":"Q234710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$08F66497-6102-408E-8617-68C24785013F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0d6456b60569138224f8420a441d205d7c21b2d","datavalue":{"value":{"entity-type":"item","numeric-id":1777394,"id":"Q1777394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$34EBD6A1-D3A4-4661-B9C1-8C6F0753D602","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$BD095394-0EFA-4E29-BCD1-33C843503300","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"51baedb45b1970a218dc00cb5762a1bbcc63a6f4","datavalue":{"value":{"time":"+2006-08-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2498920$A5C7A5D7-6BA9-4EA7-9827-9AE5E0A4612E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"968179208b0a844d0e4369197aa14fc6e147aa8d","datavalue":{"value":"The paper studies several algebraic proof systems based on linear programming (LP), namely variants of the lift-and-project (L\\&P) system of \\textit{E.~Balas}, \\textit{S.~Ceria} and \\textit{G.~Cor\\-nu\u00e9\\-jols} [Math. Program., Ser.~A 58, No.~3, 295--324 (1993; Zbl 0796.90041)], the cutting plane (CP) system [\\textit{V.~Chv\u00e1tal}, Discrete Math. 4, 305--337 (1973; Zbl 0253.05131)], and their resolution extensions in the spirit of \\textit{J. Kraj\u00ed\u010dek} [J. Symb. Log.~63, No.~4, 1582--1596 (1998; Zbl 0930.03081)].   The authors prove that CP polynomially simulates L\\&P proofs whose coefficients are restricted to integer numbers written in unary. Moreover, the resolution extension R(LP) polynomially simulates R(CP) proofs with the same restriction, and R(L\\&P) and R(LP) are polynomially equivalent without any restriction on the coefficients. The last part of the paper presents polynomial-size R(LP) proofs of Tseitin tautologies for regular graphs of constant degree, based on \\textit{D.~Grigoriev}, \\textit{E.~A.~Hirsch} and \\textit{D.~V.~Pasechnik} [Mosc. Math. J.~2, No.~4, 647--679 (2002; Zbl 1027.03044)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2498920$F4768EFB-37C7-48C4-8BEB-B2212A34D27C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf05c748b19f894b0cb445a65a1da1ca24dbc809","datavalue":{"value":{"entity-type":"item","numeric-id":331053,"id":"Q331053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$3D3393F4-312E-442F-AE00-9B8D6ABD9D5A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2498920$99F25B4E-D4D2-4B75-B264-B7DA4C340B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2498920$1056F0CE-FA1E-45A1-A389-58263AF42412","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"af1124e21eb68b74a88d765a98fa568f5515add7","datavalue":{"value":"5047237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2498920$DDDAF551-B6DB-42B7-9E61-802C2FEA0B00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"beacc345177607df4ab1f59f0170626c9d1a1d90","datavalue":{"value":"propositional proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2498920$9CD81309-AC0E-4577-AD0C-4E9C5A94439B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfeff29eb4c15469599e33e92d2c0f12df97d184","datavalue":{"value":"algebraic proof systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2498920$6AB20666-3837-4150-A9D3-B471784FB50E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2498920$468521A4-50BA-49F0-AFE4-BCF9AE37EB9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2498920$FCB07FF5-B956-47AC-B558-CC3E9B0F3AE7","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":"Q2498920$443DFBF0-E0D2-4197-847A-E1C02BA2CF29","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"15b0062d7e1700f055c6147e4bf73ae71c1e0375","datavalue":{"value":"https://doi.org/10.1016/j.apal.2005.12.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q2498920$001BEDB7-8D1A-4337-B2F0-05989C717768","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0323a6781f1861f74e6963538b89ed0c3f5f3b83","datavalue":{"value":"W2080045420","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2498920$9DC30BD0-4899-470D-8DEA-D91CB24CC22A","rank":"normal"}],"P223":[{"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":"Q2498920$98D314CC-BC27-44D2-BA1A-1E0174AE64E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbe1958fb29532b90e09c713c0b31c18a6b57a9","datavalue":{"value":{"entity-type":"item","numeric-id":4892411,"id":"Q4892411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$1C3A89BD-883D-4456-A15A-6BF1A7B19560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fc668831a6565a498110f2aeac4eebcb5e83ad5","datavalue":{"value":{"entity-type":"item","numeric-id":4228469,"id":"Q4228469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$95B34DC2-1F3E-49D6-BBED-E027AEB1C4DD","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":"Q2498920$6A628E7A-9BFC-4CC1-998F-9EF62E8EBA25","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":"Q2498920$839E5F60-73DF-44B9-96F7-BEBE724E0FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cebc572d627a83eaa191f68127ff59e387905680","datavalue":{"value":{"entity-type":"item","numeric-id":580175,"id":"Q580175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$61106191-0905-4DD0-8778-628F7BC63118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54723723fa204d746ee536bf31ad3e21f36a80d0","datavalue":{"value":{"entity-type":"item","numeric-id":1123134,"id":"Q1123134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$AC36D99E-207A-43C8-AC73-1152770AFEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8ec8f6f81428bd8769215213b5291205ed0250d","datavalue":{"value":{"entity-type":"item","numeric-id":1313833,"id":"Q1313833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$C8332063-0B52-4C11-9D2E-F49ED5E0DD3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c94d017d89fe8a00bee910dd24c96d75202f025b","datavalue":{"value":{"entity-type":"item","numeric-id":4012419,"id":"Q4012419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$B7892225-5E99-4CD4-9E9E-A41BD31E3B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f45d398cee7029b6c4eb7c6c0e2a1a407fff02c","datavalue":{"value":{"entity-type":"item","numeric-id":4934563,"id":"Q4934563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$4BF4DEE4-B7DD-4863-977C-E13EC7CA0D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eddf41ebe03e34e5faba6f69cc20868f2c5964b","datavalue":{"value":{"entity-type":"item","numeric-id":4737524,"id":"Q4737524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$1C699349-04C5-4844-9C21-F5417BDF92C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21bcd39d4d572ce00371c8bcc7e5ce715cd1a257","datavalue":{"value":{"entity-type":"item","numeric-id":4807964,"id":"Q4807964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$407BC8EE-1C08-4A9B-9612-35C8DBB8F7B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"547393787ecd9fd7a123ee35d81ac7d16e2dff3a","datavalue":{"value":{"entity-type":"item","numeric-id":4353563,"id":"Q4353563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$B4D5B789-909C-4715-B68D-82813E8380FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a88182aa7b77c4eb7005a57d5eab42f257cbc74f","datavalue":{"value":{"entity-type":"item","numeric-id":4254700,"id":"Q4254700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$F3389185-3C8D-41B2-9C60-3D7AD8AAE2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aca5f96fbc34b09e5346c7b54e907eb6f5aedb8b","datavalue":{"value":{"entity-type":"item","numeric-id":1401356,"id":"Q1401356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$1A0DC6BD-6BBD-45F4-8FC1-6C3D08A4A815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9aa7e63ff28463bee3f9b1aaa19f1ce51fa643df","datavalue":{"value":{"entity-type":"item","numeric-id":2367913,"id":"Q2367913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$5273523D-1D9A-4285-A582-AB3921383C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29f440a5bcc8c5e9b60d6c728c05d9a09887fe96","datavalue":{"value":{"entity-type":"item","numeric-id":4234107,"id":"Q4234107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$7555BEBF-C0A0-48F2-BB7B-5176407E1C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40f34823cac176489a74f3e54ebb7fe9577d93ab","datavalue":{"value":{"entity-type":"item","numeric-id":4372917,"id":"Q4372917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$32276763-AE64-486A-A18E-FC30D7B0454C","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":"Q2498920$55D88D0E-5D84-4884-B850-C7AA604E38CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"728810277830424bd131e6e77eef399df584ccea","datavalue":{"value":{"entity-type":"item","numeric-id":3780485,"id":"Q3780485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$E6353042-E84C-4BE8-B105-8AAF4FADF42C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b873186fa5e30279e410bea330a6ed356bfc2234","datavalue":{"value":{"entity-type":"item","numeric-id":5943090,"id":"Q5943090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2498920$26AB481B-3DB5-462F-AF52-3268F0019388","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f50112d85917c25d751fe74e901a726c14fa6e11","datavalue":{"value":"10.1016/J.APAL.2005.12.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2498920$8526AC01-0D5E-468E-9983-069D6E4EBF38","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"614e0625461ba0ce6dd12019630b9e50b7a8631d","datavalue":{"value":{"entity-type":"item","numeric-id":580175,"id":"Q580175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9175d9f8da8173f501b77c6a0ecccfb4ddfd84bc","datavalue":{"value":{"amount":"+0.8154018521308899","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":"Q2498920$F9E27FF0-A7AB-4786-BD47-FCFA7769A7D3","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":"ed2207a1abca0fdea10167ee888bb84baa6adbd1","datavalue":{"value":{"amount":"+0.7867227792739868","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":"Q2498920$1D886D73-DCFE-4603-AEC5-703A7348FA40","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":"66443bc5ad95113279bac2ce609979a331c16a3f","datavalue":{"value":{"amount":"+0.7784332633018494","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":"Q2498920$3FCE1133-01A6-49AB-842F-C23FD4DBC9B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf670fa68de4694250b0337c3ae20c464ce2712c","datavalue":{"value":{"entity-type":"item","numeric-id":3002766,"id":"Q3002766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b379ae892e528c05ae3da974964fd09adf530c2c","datavalue":{"value":{"amount":"+0.7781698107719421","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":"Q2498920$B98FEFC5-E5A3-4692-8035-C00A001498F7","rank":"normal"},{"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":"aa8b067d235c63f701871d22e7f067a43dc8bcfa","datavalue":{"value":{"amount":"+0.7748554348945618","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":"Q2498920$F8212025-5599-4D45-BB70-A9944DB7DE7A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Several notes on the power of Gomory-Chv\u00e1tal cuts","badges":[]}}}}}