{"entities":{"Q682219":{"pageid":684068,"ns":120,"title":"Item:Q682219","lastrevid":63555651,"modified":"2026-04-11T13:57:26Z","type":"item","id":"Q682219","labels":{"en":{"language":"en","value":"Complexity of the satisfiability problem for multilinear forms over a finite field"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6838067"}},"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":"Q682219$A92D8CB7-A6BC-41C3-A162-FE9A075DBDD4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"beda7b92f8e3468171481bad4f2d3e67791eb0b7","datavalue":{"value":{"text":"Complexity of the satisfiability problem for multilinear forms over a finite field","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q682219$BA2FE181-C29D-4D81-BB12-2CC994776BA0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2f4731d0237266ca12d93b2c204a7ee3b16d743","datavalue":{"value":"1385.65037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682219$66B941F0-701B-483B-A069-B45F10A403CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb67f9104fa753d382a2a8b0df57c3cb1ff22e0f","datavalue":{"value":"10.3103/S0278641917020066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682219$0327E865-9B81-4F40-9FFA-FEDD0479926D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"aa4e0e353121dae82cdaefca14a62dc9d4bb34af","datavalue":{"value":{"entity-type":"item","numeric-id":163582,"id":"Q163582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$03A1A1F0-5B99-4224-81FD-AB05FB625A7A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05d7846712e272ed872436847e0975767a3ed77e","datavalue":{"value":{"time":"+2018-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q682219$6FC8972E-7A21-4395-B229-5FC3B07A3AED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"94b575c45dce61cee2d04cfab173ad1fb9eca20a","datavalue":{"value":"The paper considers multilinear forms over finite fields, i.e., a product in which each factor is the sum of variables or elements of this field. The author shows that for each possible \\(q \\geq 3\\), under which restrictions of the form of factors, the corresponding satisfiability problem for multilinear forms over a finite field of \\(q\\) elements can be solved using a polynomial algorithm. In addition, it is proved that this problem is \\(NP\\)-complete in all other cases.","type":"string"},"datatype":"string"},"type":"statement","id":"Q682219$E580126F-FA22-4464-A3E8-C733A3A65E1B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7aca07346e0765309e20f807c37fbc0c5a245051","datavalue":{"value":{"entity-type":"item","numeric-id":201962,"id":"Q201962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$AA98599B-B168-44D8-BC5B-F4AE8B754FBC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682219$105A512D-C825-438D-B4E1-CA7E4CA12AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fcdcf091e8d296dbd4abc537c837748e635f0d4a","datavalue":{"value":"15A69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682219$191A5EF3-D5D6-430B-BBD5-70D1FD82D21C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bbe2dde55566c57c31463992aac9b72d0f8c104e","datavalue":{"value":"15B33","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682219$5A5275F0-55B9-4E03-8A21-36C50E9450D2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"058247f429554b4627c4ce90b1ce4039628db617","datavalue":{"value":"6838067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682219$455CA309-2378-4D3E-A6AC-D7755F90BDE6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551dcb5feed7e28ce06aed7e3e5f9ff7c511fbc2","datavalue":{"value":"function over finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q682219$DC7CD3AC-9A7B-4F06-ACB4-3B7F9C4345DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8188687443053315e00b8da6a0924aebae21a8c1","datavalue":{"value":"linear function","type":"string"},"datatype":"string"},"type":"statement","id":"Q682219$CDE7E5EC-3C9C-4D46-9DD4-338EA8172759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a60c02f00cb9b44b05a069bf7f51ec5afd557bde","datavalue":{"value":"multilinear form","type":"string"},"datatype":"string"},"type":"statement","id":"Q682219$B4925101-95EE-43B9-A65D-5C1B8D19D56A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q682219$E9355D41-48EC-4534-9077-539D1DD4E099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e33baaa9ad75f87612c7eaa10ccf86499ba643f4","datavalue":{"value":"\\(NP\\)-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q682219$6752D073-6968-496F-BC4D-BB33B2022C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q682219$F3409C77-3EDD-4A86-A8C7-48ACC44DDB47","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d13dc08b9218ee8803740f4869809fbeeec2d36b","datavalue":{"value":{"entity-type":"item","numeric-id":285505,"id":"Q285505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$2D734F58-1391-47D0-84B6-5DC6049F8754","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":"Q682219$E225B6BB-E54E-4744-A42C-A5282C60A32F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$F2ACA759-9C89-427B-AC43-16E89C1692B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$BB3173C9-DC91-45EC-BEA0-23F8EDCE117E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9d3a07608acbb8cc51d11afe6c158e7eeeff974","datavalue":{"value":{"entity-type":"item","numeric-id":2754150,"id":"Q2754150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$296097C1-DAB3-440C-BF4A-28F0FD20A445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e571e3f98073166b826f76a983987d68b90f476","datavalue":{"value":{"entity-type":"item","numeric-id":1691631,"id":"Q1691631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$CB7C4ED5-7B3B-44F5-90C2-756B86D77DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6df9df797c66e2105b650b58bb72a65315b081d","datavalue":{"value":{"entity-type":"item","numeric-id":3546290,"id":"Q3546290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$1E63E9D3-5AFF-4BBD-AAB4-45E24B3CC611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b703c6e12f827b7f6fb070d9fc732bd811f5de28","datavalue":{"value":{"entity-type":"item","numeric-id":3268312,"id":"Q3268312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$074730B2-0CC9-4B78-A38C-F60FFC45EE11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682219$CEF08023-65AD-4A03-986D-D3CA25CD25C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7763ac53fdb413ccc8b02fa4c348435e82d93462","datavalue":{"value":"https://doi.org/10.3103/s0278641917020066","type":"string"},"datatype":"url"},"type":"statement","id":"Q682219$7B57336F-9C45-47A2-8960-2B3373128756","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3b5bf0f833f6ef151b242a22c0ec6d743f65cbaf","datavalue":{"value":"W2620918030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682219$869223EC-0A46-4375-88D4-5C52515FDB8A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9af8b2a1129015656e53256f36244d303a1a089","datavalue":{"value":{"entity-type":"item","numeric-id":1103602,"id":"Q1103602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"501c58bfa5910c38840b5513e61f4284144e98e2","datavalue":{"value":{"amount":"+0.9042921","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$565239F9-3AC9-4315-9D42-43C967BE13D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"781f56dc9b9b2320d5e3e0abea9800680e601f5f","datavalue":{"value":{"entity-type":"item","numeric-id":5309685,"id":"Q5309685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c85ab98a086bf2ba7d8868014d58d6ca468effcb","datavalue":{"value":{"amount":"+0.90303504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$696DC45B-17FC-4C4A-82A4-EFBADCD76747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee9afb024e39224c0be1395ec9a94a17a985b352","datavalue":{"value":{"entity-type":"item","numeric-id":4729350,"id":"Q4729350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2b013570650c3c7cd2d90e0a5766abb8f141410","datavalue":{"value":{"amount":"+0.8979541","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$FBEF013A-5494-45A1-A22C-1D544F179B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77a7e00159c0998cc84e46c278f0342852cd31ac","datavalue":{"value":{"entity-type":"item","numeric-id":800915,"id":"Q800915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a88d6b3e58a167612178d9ac5ce2cd9f0673d631","datavalue":{"value":{"amount":"+0.8824379","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$17969EFF-5B67-4F7E-AA6D-38697BF30C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df684ab8201b649acc8d339dca420dbf8bf70615","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cdded084dc47b1e479bc169f90679a382256a00","datavalue":{"value":{"amount":"+0.8787874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$4F1CA64A-191B-448F-B871-1041E4D0E928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e107406d546a8b96befb0655f487c9c1e762277","datavalue":{"value":{"entity-type":"item","numeric-id":4344698,"id":"Q4344698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"484625eee26cad145530382ba68d0bf888331a54","datavalue":{"value":{"amount":"+0.87582225","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$13B2BB24-ADBC-4088-9836-E516CE65D739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67262a8a0a66365dd671f2201cf9795a7b4867ae","datavalue":{"value":{"entity-type":"item","numeric-id":2680709,"id":"Q2680709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd1cc9179416793dcd26ac30986d63b4a9bf1240","datavalue":{"value":{"amount":"+0.8751933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$C4357843-A208-463F-AC6B-227CB1671E89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"606f84817fbcd48e21234bebbfca47cfe90c972a","datavalue":{"value":{"entity-type":"item","numeric-id":1680241,"id":"Q1680241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34338fc93d05ce98dd1e0ad6166ff244ba60d454","datavalue":{"value":{"amount":"+0.87408996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$90AF73F7-FCEE-4B15-8342-861F83751E1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c667834e78b5c36a5fcb85623af15d281dfdafe2","datavalue":{"value":{"entity-type":"item","numeric-id":4634397,"id":"Q4634397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb58c2a1202816f2e60ada22954d0349dd756afb","datavalue":{"value":{"amount":"+0.87257934","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$3D7B7061-A770-48AE-AF4B-6CCE75533F4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"109db63ffdf79ca806ec3df728dd498092aeead6","datavalue":{"value":{"entity-type":"item","numeric-id":3365840,"id":"Q3365840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdc17a2325d7cada1906ed78791cf631b08e9311","datavalue":{"value":{"amount":"+0.87233496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q682219$4BB324E5-CDF1-4E3E-8F24-79B2C8175CE5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of the satisfiability problem for multilinear forms over a finite field","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_the_satisfiability_problem_for_multilinear_forms_over_a_finite_field"}}}}}