{"entities":{"Q4375799":{"pageid":6405398,"ns":120,"title":"Item:Q4375799","lastrevid":108320513,"modified":"2026-11-05T22:02:07Z","type":"item","id":"Q4375799","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1114028"}},"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":"Q4375799$3A2C7634-437A-4FAE-8C1A-8480776F9FA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8245b3d8cf31abc21464d62be8ee12e324e7fdd","datavalue":{"value":"0901.03033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375799$E2667A0B-81D8-4F78-842C-A6E34392950F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"318018faae3560d6874b4d183002bf8aee67c872","datavalue":{"value":{"entity-type":"item","numeric-id":185618,"id":"Q185618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4375799$D1C23631-917E-44EF-8D75-727DECCD3713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"68410c8b701a5d2353de4ef8d65f833c0ac3784e","datavalue":{"value":{"entity-type":"item","numeric-id":170016,"id":"Q170016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4375799$732B869D-18AC-425F-A7CD-EF44005DC165","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"77cf8e62a6baff735cf6cec74a92b930b6767f10","datavalue":{"value":{"time":"+1998-03-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4375799$E7F7E9EB-7289-4898-B5FB-51AD638F6FFF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375799$6A032EF9-B747-4FC7-9DAE-4B2E3B376BF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375799$4543A5B1-63C2-46B3-B605-493D4B245028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375799$9A549F02-7C4E-4A87-A306-7F172E09A0A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375799$599D01E5-8D2E-428A-B421-131E263FE2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"419d6f2b09c39920e34f63114ff159a2f0a01812","datavalue":{"value":"03B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375799$646D7BD5-EE49-4F62-85F3-7E4DA0E4734D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"215ba618bf4d1ff7b31b95446c71c4b6eec2b093","datavalue":{"value":"1114028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375799$45141041-6CF3-4324-8B46-DE3118EDE491","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bd3ffc9cdc691ffdea813c071eb1d3921762ee9","datavalue":{"value":"span program","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375799$59F59CC7-8A3F-44CA-B61D-720353A0C82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d91f10fa873b05a17b2cd8eb55da393f86e8ed1","datavalue":{"value":"interpolation of polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375799$D6CE1CEF-9C65-4C5C-BD7A-47AF77E95503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98de6929508fa5da5a6d2066472fa217b0329cd8","datavalue":{"value":"Nullstellen refutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375799$7BD5AF28-A58F-4964-8C7D-B0053277DC32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375799$DAA6C649-3F01-4EBB-8C2E-5C076B251238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"930f8eaa3d0fc649e190ecc5438cd1861f43bc88","datavalue":{"value":"algebraic models of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375799$525511EE-BD27-42BB-B1C4-7FC8D957BF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375799$83BF0172-C1C2-43D0-9A9D-947E4A582064","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":"Q4375799$F77384C0-E0AC-429A-99B7-322C71E5C1FA","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":"49cff384db5ca5288d50691e4a384a4ff48899ec","datavalue":{"value":{"amount":"+0.7724424600601196","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":"Q4375799$55A61031-44B4-4F83-8EFD-E5F556381D4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea21238cf6740281b3d4e70b853899669d81abf3","datavalue":{"value":{"entity-type":"item","numeric-id":5748889,"id":"Q5748889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c062eded70ac0d06167de9bbe3311b64312c550","datavalue":{"value":{"amount":"+0.7672255635261536","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":"Q4375799$0DA97BF1-5937-4487-9A17-2B5E31611EAB","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":"6a3b2056b531a301a42ed3a04741537b4d48281b","datavalue":{"value":{"amount":"+0.7546350359916687","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":"Q4375799$9A44B447-5303-44B3-B1BB-0A57E23C116F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa2cb18e0a7bb7c64f1a812c8b3208432104866a","datavalue":{"value":{"entity-type":"item","numeric-id":451113,"id":"Q451113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57ad6a18ae60357de56d81b06a03cf2c92f0fee3","datavalue":{"value":{"amount":"+0.7540153861045837","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":"Q4375799$6450A182-B362-486C-8733-4586E35659A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f83f581432b57072142a2b10a16a91cec6bc7328","datavalue":{"value":{"entity-type":"item","numeric-id":1977413,"id":"Q1977413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69eff07907ede019365c04e33d8f3e6492a230a5","datavalue":{"value":{"amount":"+0.7516171336174011","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":"Q4375799$0CC573DE-E9B4-44E0-921D-9E89C931297C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ff6279b9f95851873d693cd6d43e5ba1995adff","datavalue":{"value":"The authors consider the algebraic models of computation: dependency, span, and polynomial programs (abbreviated DP, SP, and PP, respectively). The first two are about labelled matrices over a field \\(K\\), where \\(K\\) is \\(\\text{GF}(p)\\), \\(\\mathbb{Q}\\) or \\(\\mathbb{R}\\). Their rows are labelled by \\(x_i\\), \\(1-x_i\\), or 1. Under a truth value assignment to \\(x\\)'s (1 for truth, and 0 for falsity), those row vectors are selected whose labels become 1. The DP [SP] takes the value 1 if the selected vectors [together with \\(e=\\langle 1,0, \\dots, 0\\rangle]\\) are linearly dependent. A PP is given by a set of labelled polynomials in \\(K[{\\mathbf y}]\\). Under a truth value assigment to \\(x\\)'s, the program takes the value 1 when there is polynomial refutation of the selected polynomials, namely a non-zero constant polynomial can be obtained from them by linear combinations and the operation \\(q \\mapsto {\\mathbf y} q\\). The first half of the paper is about the relative strengths of those and other computation devices. A simple Boolean function \\(f_0\\) is exhibited whose \\(\\text{mDP} (f_0)\\), the minimum size of monotone DP, is exponential. The authors show that \\(\\text{SP}(\\neg f)\\leq n-\\text{SP} (f)\\) where \\(n\\) is the arity of \\(f\\), relations between \\(\\text{DP}(f)\\) and \\(\\text{SP}(f)\\), and mutual simulations of PP's and Boolean circuits. The second half of the paper is about interpolation theorems of polynomials. When a set of polynomials \\(p_i ({\\mathbf x}, {\\mathbf y})\\) and \\(q_j ({\\mathbf x}, {\\mathbf z})\\), where \\({\\mathbf y}\\) and \\({\\mathbf z}\\) are disjoint, has a Nullstellen refutation, then there is an SP \\(C\\) on \\({\\mathbf x}\\) with the property that if \\(C\\) accepts \\({\\mathbf u}\\in\\{0,1\\}^n\\), then \\(p_i ({\\mathbf x}, {\\mathbf y}) =0\\) are not satisfiable, and if \\(C\\) does not accept, then \\(q_j ({\\mathbf x}, {\\mathbf z}) =0\\) is not satisfiable. And conversely, an SP is described by a Nullstellen system. Besides these definite results, the authors comment on how to use interpolation theorems to determine lower bounds, on what happens when the base field is changed, and on recent achievements. The paper closes with a section on open problems. For the entire collection see [Zbl 0881.00033].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375799$DB2B69CD-B0D1-489A-9E41-D9F65706E056","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4375799","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4375799"}}}}}