{"entities":{"Q1813835":{"pageid":1824577,"ns":120,"title":"Item:Q1813835","lastrevid":46208464,"modified":"2025-12-24T07:53:05Z","type":"item","id":"Q1813835","labels":{"en":{"language":"en","value":"Cutting-plane proofs in polynomial space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5237"}},"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":"Q1813835$10322E9B-7967-4C74-8F3E-A29592E42577","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a0905e32b39e2863940ccf705c62f06562e73782","datavalue":{"value":{"text":"Cutting-plane proofs in polynomial space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1813835$3CD09224-2457-4F7D-BB6C-94A336ABDC29","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"be392cfec1b58d9d67628ebdc36e28d174832d1e","datavalue":{"value":"0735.90048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813835$A25D2D6F-BE52-4B37-A7BD-89A96571AEE6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"25c8b38a2652940f61889a48895a69d14777bbf5","datavalue":{"value":"10.1007/BF01580849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813835$361C9658-0968-4686-897B-761D8987B976","rank":"normal"}],"P16":[{"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":"Q1813835$05F0D0B8-9753-437D-8A0C-B007CB4BDF61","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$BB8F7D14-5803-4137-8630-D9ABA891BB84","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1813835$4718A1B5-CAF2-4AF2-A8CE-EA2AAA042BBE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"884b337da9f8e15f3d3665f6f348464d70d0feb6","datavalue":{"value":"In order to prove that a system of linear inequalities \\(a^ T_ ix\\leq b_ i\\), \\(1\\leq i\\leq m\\), has no integral solution, for \\(i=1,\\ldots,M\\) one may recursively derive a linear inequality \\(a^ T_{m+i}x\\leq b_{m+i}\\), by nonnegative linear combination of previously known linear inequalities and integer roundown of the resulting righthandside. Then, if the last inequality is of the form \\(0^ Tx\\leq-1\\), infeasibility is obvious. Such a system of \\(m+M\\) inequalities is called a cutting plane proof of length \\(M\\). The existence of cutting plane proofs for systems with rational coefficients is well-known. Here, for such systems, the existence of a cutting plane proof of length \\(O(n^{3n})\\) is shown, which can be carried out in polynomial workspace.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813835$37625EDE-E439-463D-8A33-A017D1EB8774","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5500d0e3ae3870dfabd55c7acf03571be7dc260a","datavalue":{"value":{"entity-type":"item","numeric-id":1018087,"id":"Q1018087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$CE5DE5A0-4CC1-4BE3-BFB3-C12D1D53539D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813835$44B3812E-0A60-411D-BC8C-BA4B0C1DD23A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813835$180473DD-71A9-4248-8EA7-6E8A47FF76B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813835$7894941C-CDF1-4710-88D1-0D91F916447A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4a7a26db0e7dff923f033553de7caaaea2eaf77e","datavalue":{"value":"5237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813835$E1BC989E-EB31-47C4-B250-9EF69A60F056","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b9c5a0cba0f97232b66bfa1a041428636b46a07","datavalue":{"value":"non-existence of integral solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813835$4B2C1EA5-E7C4-4E09-9717-F2514C812BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"780aa31aabe63e350d953e44e392b588d88bd8b1","datavalue":{"value":"system of linear inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813835$C721B762-5527-4278-83A2-1658FFF3D18F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e15b52a9d8b60dd58ccc43e0160f4015e483c078","datavalue":{"value":"cutting plane proof","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813835$148BD8F8-C500-4347-98B9-A656FEC4B882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc4e6a4b642ce35de5dceb373a9fc6e6d6efb56a","datavalue":{"value":"rational coefficients","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813835$03D1930B-942C-403E-9C6B-96D10691580A","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":"Q1813835$0BFC0F1A-1E5B-47AC-AFD3-35898695813C","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":"Q1813835$E10CCC24-6538-4276-BB6D-0287F733EDE2","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":"Q1813835$840B0226-BACE-4061-B321-D3D41A58F8C9","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":"Q1813835$85908F5B-9948-4A98-AC3F-06378D22857E","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":"Q1813835$1C3AC28B-BF50-4092-8269-3B8EAFB8A3D5","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":"Q1813835$D147FBBD-8DFA-4518-8250-C5599AA5AE27","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":"Q1813835$C7FF718C-016B-4FE9-8A9E-C296AAF906E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8bced2c88bb3f79c405b650dcc49d42df378140","datavalue":{"value":{"entity-type":"item","numeric-id":3696859,"id":"Q3696859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$C10F0BF8-E898-4D99-A51E-353ED7A3E8DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9cdc996ad6a2d6bc6c15f31d7c4c57ae7effab5","datavalue":{"value":{"entity-type":"item","numeric-id":3888840,"id":"Q3888840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$AAB31299-28AE-4F55-B110-8513C04C96B6","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":"Q1813835$C4CBCF74-4146-4D98-A95E-570DF3B1B38A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32866bf2d31b9cf1002630f1a4c01f322b0cc4f7","datavalue":{"value":{"entity-type":"item","numeric-id":3217947,"id":"Q3217947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$8626B9FD-A8BE-4D6B-8917-3F68552998B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c9ee08bf2113ff3da12debab83a452160edd63","datavalue":{"value":{"entity-type":"item","numeric-id":1309040,"id":"Q1309040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$162EC36E-64F3-4686-9A32-EF24233F3590","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":"Q1813835$C38E36F3-301E-42FC-ADB8-169B875C3F51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34b74e05f8eeb34a69e1761409f15ac9e04c8087","datavalue":{"value":{"entity-type":"item","numeric-id":3780763,"id":"Q3780763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$D12797DE-A918-450C-B179-24C7383DA06D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a0f65086eff7a2f88ff828884c33b327fcd1f34","datavalue":{"value":{"entity-type":"item","numeric-id":3757974,"id":"Q3757974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$64667102-A163-40C7-8BD0-F9D9ADB549CF","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":"Q1813835$B5BDB221-6F86-4D0E-8890-B0563B7EDA20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64aeaa85587aeb8505e54a77d579017e954e0b6b","datavalue":{"value":{"entity-type":"item","numeric-id":3703656,"id":"Q3703656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813835$A3358AC8-4DBF-4098-A743-BA456CB3570F","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":"Q1813835$DC8B8C8D-D25A-4DCD-BD22-70ACA5F3C443","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":"Q1813835$0159BC04-02E8-4BBF-A5FE-0F9A7118306E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80ff141bc8e11524b858ecb83df0bd33229d72dc","datavalue":{"value":"https://doi.org/10.1007/bf01580849","type":"string"},"datatype":"url"},"type":"statement","id":"Q1813835$A12DBF3C-7B70-4272-AB61-C20F876E7B3A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7fb50ad80e079a55aba54692daa27a312fc0e470","datavalue":{"value":"W1990237439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813835$AA8024F9-FCFF-421C-852B-9E1357350467","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":"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":"Q1813835$34AC7136-F341-47A3-9BE1-818A404AD165","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":"cf2ba42737e2f5c8d046a5eab6e7e16e16318b5b","datavalue":{"value":{"amount":"+0.835821807384491","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":"Q1813835$5A0A4536-4F01-481D-8351-CE53D0E32648","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":"efba07d51fbf72fdeb0569022df58ef9ba0d225a","datavalue":{"value":{"amount":"+0.8278947472572327","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":"Q1813835$97D07836-2ECF-416E-946B-700949A3F5B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a65b2f26886358e7abe03f6b645cf5d7c19a2063","datavalue":{"value":{"entity-type":"item","numeric-id":1123134,"id":"Q1123134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e5f7f76527d852c6cc6eaaaeb4003dd5f8ad7a6","datavalue":{"value":{"amount":"+0.8150716423988342","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":"Q1813835$8DF12918-3476-474D-B680-A2ACC29A645E","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":"df4ea8bd8afff774f4503b157af9f0942f6615be","datavalue":{"value":{"amount":"+0.8150280117988586","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":"Q1813835$26A3BA2A-29AC-4A33-8FFA-F2D0E454C268","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1813835","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1813835"}}}}}