{"entities":{"Q1126839":{"pageid":1137588,"ns":120,"title":"Item:Q1126839","lastrevid":66188328,"modified":"2026-04-12T08:08:26Z","type":"item","id":"Q1126839","labels":{"en":{"language":"en","value":"Unsolvable systems of equations and proof complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1184383"}},"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":"Q1126839$A026F47D-81EC-4FBA-98E3-CC4923ABAEA8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e7d945e193771ecbde3b971e07f613ba4073f848","datavalue":{"value":{"text":"Unsolvable systems of equations and proof complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1126839$1C28C429-106C-4379-8AFC-93A819419EE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7977f1ad1690cd5d3e8a76278b15d66142571de0","datavalue":{"value":"0903.03033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126839$84D89698-97B2-48BF-A204-C28D8B43945E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38b40ed6cb099fba5da493703b11839c0af89042","datavalue":{"value":{"entity-type":"item","numeric-id":202089,"id":"Q202089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126839$A02F17C1-C85E-4976-88FD-4EE2C6435200","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4add3c5163a5eee9bbe20dc8a36386ab43b68fd6","datavalue":{"value":{"entity-type":"item","numeric-id":168490,"id":"Q168490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126839$37CB6C87-355B-4BE1-9CF6-48C60D43F270","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0213be50779ba5bffb4613228959545da04beaec","datavalue":{"value":{"time":"+1998-08-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1126839$809D9554-27CA-4C07-9CAB-8F11C2860078","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"88b185e99570e657ab99f3553cb9bf89e99af638","datavalue":{"value":"https://eudml.org/doc/232165","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126839$084F1161-87CE-4B74-BE87-7DC502B5F6CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"1a86eb821f00b168356ba01b0beee765898d8ba0","datavalue":{"value":"http://www.emis.de/journals/DMJDMV/xvol-icm/14/Pitassi.MAN.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126839$57CD27E4-B83E-44EC-9030-1434152FA234","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ceb162ebcb47572454ed94717ba9429becea8400","datavalue":{"value":"This is a survey of an algebraic approach to the efficiency of propositional proof systems. To a formula \\(C\\) in conjunctive normal form, one associates a set of polynomials \\(Q_i\\). (An atom \\(p\\) goes to \\(1-y\\), \\(\\neg p\\) to \\(y\\), and \\(\\vee\\) is replaced by \\(x\\). Thus each conjunct results in a polynomial. And, add \\(y^2-y\\) to confine the values to \\(0\\) and \\(1\\).) The given \\(C\\) is refutable iff the \\(Q_i\\)'s have no \\(0/1\\) solution iff, by the Nullstellensatz, \\(\\sum P_iQ_i= 1\\) for some \\(P_i\\)'s. According to the author, ``Algebraic proof systems are appealing because of their simplicity and non-syntactic nature'' -- and, of course, much work has been done by algebraists on equations, the Nullstellensatz, etc. She compares algebraic proofs to Frege, resolution systems, etc., and talks about some methods and results (e.g., the design method, lower bounds for pigeonhole principles). The author gives good directions for future work by citing and commenting on open problems. We have also a recent good survey article by \\textit{A. Urquhart} about ``The complexity of propositional proofs'' [Bull. Symb. Log. 1, No. 4, 425-467 (1995; Zbl 0845.03025)]. Compared to it, the present article is more research oriented in a narrowly focused area.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126839$8320CFCA-A4FF-4E38-AF35-646072B00A52","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126839$637D5544-1496-4BF8-B876-5ABB327AABBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"419d6f2b09c39920e34f63114ff159a2f0a01812","datavalue":{"value":"03B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126839$245CA562-1D52-4006-82C9-CF0764DF4D9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126839$B3EDDB3E-797B-4A52-B0C8-CD133F39E89B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"86a2b7d213304295c0024a701ebf52bb20302731","datavalue":{"value":"1184383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126839$B500BDA2-D4B5-4912-9701-4D148E326999","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"beacc345177607df4ab1f59f0170626c9d1a1d90","datavalue":{"value":"propositional proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126839$40EEB3B2-6F36-4866-9547-0D16A9238F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58a9af3c348dd19e1424bff779d1dfd8fb8311ca","datavalue":{"value":"system of equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126839$0A2AA1CD-8A43-40DB-AB3A-3D28EC954B83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"421a43f4b0e8832a026eaa34353c95869f115bee","datavalue":{"value":"survey","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126839$570FBC26-B805-4FD8-8F1E-4E9D2706D502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a35a8ef64fd3eadaa7183931d4270c52e08949b","datavalue":{"value":"algebraic approach to the efficiency of propositional proof systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126839$05D1E071-E46E-4008-AFBF-2AF6B4784002","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":"Q1126839$F8713AC1-4B0A-454D-A17B-98A1C2A6059A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"094d1340bd1d412900a173cb58d2895fe49ae516","datavalue":{"value":{"entity-type":"item","numeric-id":4353563,"id":"Q4353563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f79bce4c314b27941a223940cc8fd287ac767a4","datavalue":{"value":{"amount":"+0.8801252","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$E425E4EC-F004-45E4-992E-36FD1714779A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4ef7516fef19e6ad66dadf2480597f1ae72fc3d","datavalue":{"value":{"entity-type":"item","numeric-id":3081620,"id":"Q3081620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94d28121dc46c2567602b7a5d7efb61ec8fb1939","datavalue":{"value":{"amount":"+0.81587","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$90E1DDA6-D53D-46C2-B293-11A90510F44E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7b47d5008fb5444114c966ed6f511fa02db28fb","datavalue":{"value":{"entity-type":"item","numeric-id":4790400,"id":"Q4790400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8cf2d14ee800f83b0543e7aeb18a12430585fd0","datavalue":{"value":{"amount":"+0.7921903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$E5D3CE9B-7F8D-4054-B894-2BB6255E3356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6644c89e365e503e202a0eb12c3f2936cc4b499","datavalue":{"value":{"entity-type":"item","numeric-id":3569758,"id":"Q3569758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71f88285995ec229f964dc6cced3e6cf9c3992c0","datavalue":{"value":{"amount":"+0.7883563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$B367EEAB-B70F-4BD0-9A41-08E571F1EC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af0dcb9473db49242994ba849ab40d6e8309464a","datavalue":{"value":{"entity-type":"item","numeric-id":1401356,"id":"Q1401356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcccc1fbbd90f97f2ca1f8c02c12f9f871bcfd80","datavalue":{"value":{"amount":"+0.7852293","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$98AF3ED6-A150-4FB3-B9F6-DF4682BE38EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21600ebf93e0786bbeca6c785e3c9bff573c8a62","datavalue":{"value":{"entity-type":"item","numeric-id":3743300,"id":"Q3743300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6df9ffb70ccb5086f0aa875fe8ff9d1ee21337a","datavalue":{"value":{"amount":"+0.7813761","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$E6B0A636-079B-4138-991E-1325B96D3708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6aa100b29d9cd12565a71aa0ff38bd358411e57","datavalue":{"value":{"entity-type":"item","numeric-id":1014285,"id":"Q1014285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"993c5ee05a8927edc82957bdfd68e05b73d09bd6","datavalue":{"value":{"amount":"+0.77628154","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$423A3E3C-1E46-4B9A-8DB7-CDD28996FCFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad7b96b100b354f3d2aaaf468c5027db281cb541","datavalue":{"value":{"entity-type":"item","numeric-id":5290079,"id":"Q5290079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6618a183b26c1b15e42aaec6ef46f423ad60cdc4","datavalue":{"value":{"amount":"+0.7741787","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$ED0167CF-99D1-4EC6-B3AD-415AA5413B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50b0b8df70261eefcfd6c6af38e07856d6659ff7","datavalue":{"value":{"entity-type":"item","numeric-id":4273485,"id":"Q4273485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"624843764e1da7e75d162318f10b3f953dde20d7","datavalue":{"value":{"amount":"+0.76988286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$262FF881-71A9-4058-9571-FDB8E16C840C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2cccaac9b36deb25402bd0f6ccff787ac830afb","datavalue":{"value":{"entity-type":"item","numeric-id":3775553,"id":"Q3775553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85b6bd3b17ce3b66e3a1536feaa63daf82da73cb","datavalue":{"value":{"amount":"+0.7598263","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126839$22FB23E0-A3B0-4158-9EE8-310FA2DACF05","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"9ad6d7aa5cc4399980568e042288aa7a5aca0c6d","datavalue":{"value":"bafkreih2ojlnxdbfjj4ezc2u6qg3rbhm5vpi3c4zyraaf6rzv6bj5wkrw4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126839$B04DAAE0-95CA-455C-AFE9-872E2D3CCAD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Unsolvable systems of equations and proof complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Unsolvable_systems_of_equations_and_proof_complexity"}}}}}