{"entities":{"Q1575265":{"pageid":1586005,"ns":120,"title":"Item:Q1575265","lastrevid":72229497,"modified":"2026-04-14T03:29:43Z","type":"item","id":"Q1575265","labels":{"en":{"language":"en","value":"No feasible monotone interpolation for simple combinatorial reasoning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1493208"}},"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":"Q1575265$B966CE04-DD9E-4547-9275-D50376E6E8A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fc8a3d7d99e2b16fc99a37a1d407c27158784028","datavalue":{"value":{"text":"No feasible monotone interpolation for simple combinatorial reasoning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1575265$CB6214F3-2AEE-4DA9-BB5E-76370B7DDFF6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a9777da3c7fd8e004562d8fc33ad9ac11751720","datavalue":{"value":"0947.68129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575265$214A7985-8C6C-4A53-9275-AD2948088758","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"896ae1a5ef098bc551f9d44223032c744e2bd6ee","datavalue":{"value":"10.1016/S0304-3975(99)00142-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575265$F05C6478-8149-483C-9004-BCE8C4D2E149","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$15D7BB5D-0962-4FA0-BB24-C5C4A7A0A552","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3a497233c3b9babc42d370358782cbff338a7a1","datavalue":{"value":{"time":"+2000-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1575265$1B02EABB-A0C1-4555-91D7-68C6291CC1FD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f1f358b4dcdb2f13ad28b1d7283be42e58b3919b","datavalue":{"value":"The feasible monotone interpolation method has been one of the main tools to prove the exponential lower bounds for relatively weak propositional systems. \\textit{N. H. Arai} [Theor. Comput. Sci. 170, No. 1-2, 129-144 (1996; Zbl 0874.03065)] introduced a simple combinatorial reasoning system, GCNF+permutation, as a candidate for an automatizable, though powerful, propositional calculus. We show that the monotone interpolation method is not applicable to prove the superpolynomial lower bounds for Simple Combinatorial Reasoning. At the same time, we show that cutting planes, Hilbert's nullstellensatz and the polynomial calculus do not \\(p\\)-simulate simple combinatorial reasoning.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575265$8FA53283-F05D-4CC5-98A7-D05AA42962BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575265$58F7037C-690E-4E3C-9AE2-383865C846BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c4618fa1531ea8e69efc3569e2d1be5961aea91","datavalue":{"value":"1493208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575265$48541D20-BF62-4F39-A6B0-D21E58CE83E5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e97175fd5d747e7d34cbcc625e3abab53d84653d","datavalue":{"value":"automated theorem proving","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575265$CA6BBC0A-FF69-484B-A57D-5C355FEC81AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"986e975208b070c5142b42b7967bb38dc4fad0f4","datavalue":{"value":"proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575265$E4FE7DFF-5BF4-4046-BA52-8EDA46FE8E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1093f6950436e6545be25dd909b86fbd17fd071e","datavalue":{"value":"Craig's interpolation theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575265$BB871097-33DD-4742-9221-D308DA14EB2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83d5dcaa7aef3dc9ddc3eab92a7db35d53442c07","datavalue":{"value":"proof theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575265$D2FF3C61-8D2B-44E7-88DE-7DBF4B394654","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bcd9adcafff3c3e938b5e5e0f052dd5c7280bbac","datavalue":{"value":{"entity-type":"item","numeric-id":672045,"id":"Q672045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$760B3D36-0113-49D8-B727-3C0C344A1766","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":"Q1575265$9713B28E-99A6-42E9-A432-E8DCBA6D48F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"67a487a3fb672eb98191b9bdbf624338ecd55ae0","datavalue":{"value":{"entity-type":"item","numeric-id":672046,"id":"Q672046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$D6677EE7-B2C5-4ACC-9AA2-420DDCFD6B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86e4e63da862f8ce436f62bf19bd8795337a40ed","datavalue":{"value":{"entity-type":"item","numeric-id":1575637,"id":"Q1575637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$76CB10AC-82FE-423E-975E-1F61DCE66773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6924f4ee8a99479c5b7ea44e6e76cb9c4c20d60","datavalue":{"value":{"entity-type":"item","numeric-id":4503949,"id":"Q4503949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$0D85B7B9-E7AC-480C-B42E-6529181BB74A","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":"Q1575265$44BF0F93-420E-41F8-9DDF-FFD3E9468A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b87d4d660be017ed3a655c9578140dd400c43c7","datavalue":{"value":{"entity-type":"item","numeric-id":4385519,"id":"Q4385519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$6F39A385-CD42-4D82-BADD-4E1ABA8783C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4756f7b3e413b96dc6a797669c55c442b5b6f6f1","datavalue":{"value":{"entity-type":"item","numeric-id":4749821,"id":"Q4749821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$1EA96E3F-AC60-446A-BA52-9DEF95F2A49A","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":"Q1575265$5B527164-F92F-4AC4-8C5D-6A2B4C0EC731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"018ad7ee45a8745682bf748d77e68043fc321cba","datavalue":{"value":{"entity-type":"item","numeric-id":4375799,"id":"Q4375799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575265$ED435239-AE84-4E6E-9352-7F4CBE3640EE","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5fbc6d32f503b7fd2dbed495123da3f4bcea0c22","datavalue":{"value":"Q126812394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575265$68A101A1-3428-4226-9ED1-17F3ADCDAC48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"383a99c8b490e77eb4dfc8823e8a2572ec605157","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(99)00142-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1575265$F8921536-FABE-4598-9387-A2DF3EA98035","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"36dd1d3c9e0b54d0aaa50619ff631ec05f46f56a","datavalue":{"value":"W2075231625","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575265$9451BDD5-111F-4B29-8268-387EEF187651","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f07578be4bb043516c6e8180ac22721d8f931693","datavalue":{"value":{"entity-type":"item","numeric-id":4503949,"id":"Q4503949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a96f7a5ae486f177c6fa44cd2beb7ec4d0a77cb","datavalue":{"value":{"amount":"+0.8878579139709473","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":"Q1575265$9DE8D451-F89F-43A6-86E3-5174F27A447D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f9b0f3f9d830e7cb6bf3406961bac69ec3b7895","datavalue":{"value":{"entity-type":"item","numeric-id":4507332,"id":"Q4507332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e031176e4ab4ba21a5ff6ec86d28caf52b3ebd12","datavalue":{"value":{"amount":"+0.7588459849357605","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":"Q1575265$324932EB-58AB-45F9-AFB6-251EB2837277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cd8a30ceea8c23c439b0c2bf57e1776b9f2d4e0","datavalue":{"value":{"entity-type":"item","numeric-id":4358049,"id":"Q4358049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a246a5507ee035dcadad771ff4bcc12df506c95","datavalue":{"value":{"amount":"+0.7428791522979736","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":"Q1575265$1E6593BE-DCB3-4022-A869-E38C0F7F4B96","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"No feasible monotone interpolation for simple combinatorial reasoning","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/No_feasible_monotone_interpolation_for_simple_combinatorial_reasoning"}}}}}