{"entities":{"Q1070255":{"pageid":1081007,"ns":120,"title":"Item:Q1070255","lastrevid":69563958,"modified":"2026-04-13T07:52:07Z","type":"item","id":"Q1070255","labels":{"en":{"language":"en","value":"Uniquely solvable quadratic Boolean equations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3935103"}},"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":"Q1070255$36A44797-C1FE-4FBC-9967-D02B993054A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"72d1bc9811dbd93ed0717b6d48266396ab5f3757","datavalue":{"value":{"text":"Uniquely solvable quadratic Boolean equations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1070255$29CAEDFC-E30C-4862-AC38-14D5B8F6D5B8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2edd06d0e0841116c300672e201698983bf4e3c8","datavalue":{"value":"0584.06008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$AC1AA94E-EF28-4346-A33A-6A6D77E4092D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6830e208a42bdb68799798ecfa2cde8618a27639","datavalue":{"value":"10.1016/0166-218X(85)90068-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$567EA398-51E0-4ABD-BB76-A31CB7B2681B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bf47db66b00e4c421ce1e7ba44bc0c7e860c19b","datavalue":{"value":{"entity-type":"item","numeric-id":190032,"id":"Q190032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$24AF5C0A-5397-421E-B809-9A97E8D9D3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d014b1a5c53d4583e103a493ca5a114390d7213","datavalue":{"value":{"entity-type":"item","numeric-id":185380,"id":"Q185380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$6CA4CF63-E8E2-4203-939D-99C422B60396","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$07670E27-618E-43D9-82FF-34FB3A4860FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1070255$1929D541-EC17-48F7-A1E3-2C32EB5F09A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bb2a31c8e2b91e0649e0c25c21ce3ed2063ca692","datavalue":{"value":"It is known that a quadratic Boolean equation \\(f=0\\) in n unknowns \\(x_ 1,...,x_ n\\) is consistent if and only if its implication graph G has no circuit, where G has 2n vertices labelled \\(x_ 1,...,x_ n,\\bar x_ 1,...,\\bar x_ n\\) and for each term \\(x_ i^{\\alpha}x_ j^{\\beta}\\) of f, a couple of arcs linking \\(x_ i^{\\alpha}\\) to \\(x_ j^{\\beta}\\) in both directions [cf. \\textit{B. Aspvall}, \\textit{M. F. Plass} and \\textit{R. E. Tarjan}, Inform. Process. Lett. 8, 121-123 (1979; Zbl 0398.68042)].    The main theorem of this paper states that \\(f=0\\) has a unique solution if and only if for every \\(i=1,...,n\\) there is either a path from \\(x_ i\\) to \\(\\bar x_ i\\) or a path from \\(\\bar x_ i\\) to \\(x_ i\\) but not both. The authors also derive a linear-time algorithm which either finds out that \\(f=0\\) has no solution or reaches a solution, establishing simultaneously whether that solution is unique.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070255$86B3E5B1-0EA0-4028-95A7-1DBC4299333D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ff5afb9f74c3a3415ada815bc1c672499bc6e26b","datavalue":{"value":"06E99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$BC3EFA47-2F90-4E31-9CF8-5C28CA7B016C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$C3E8218E-7B87-48CF-A0CE-4BC43D977C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$CA7F661E-369F-47EA-A7FD-B4BE4C6DA716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d9a3514a89c23e0ac2c3d927db97941ff2631de6","datavalue":{"value":"06E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$04A75D01-379A-4A7B-838F-2C2DE80A024C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$CEE2E174-1F56-4A87-AE78-C5BCD6A6817E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6ddb7ebdcff906da1df6ff6bfe00907c94747745","datavalue":{"value":"3935103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070255$32317BDE-E37C-49C5-9D08-B12BAAE1C90D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa3bee3dcbbfe013d17cc2df5ab50a8fcca76d5b","datavalue":{"value":"quadratic Boolean equation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070255$A94E2C29-6866-4452-8213-174959A02DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c850b5604638748e47db6d2307bbc4739cdcc10","datavalue":{"value":"implication graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070255$FA9BA62E-00B1-4186-A416-296C056B4B15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"946d03254910cc41ad507f20e06c7f20b02d605c","datavalue":{"value":"unique solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070255$77AFB2B4-BC0B-44A2-AC3F-2FFAB4F559F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd294ef453f683b3580f78363b0fcf18795b3a31","datavalue":{"value":"linear- time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070255$0444FB3E-F309-4E61-9258-97F56D313591","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31b64c380fcc4cff66bf21399b51cdd38a2b701d","datavalue":{"value":{"entity-type":"item","numeric-id":588921,"id":"Q588921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$41662725-A641-4202-9E37-5D8BBC1BFE0A","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":"Q1070255$11899067-1BFD-489D-BD7D-D785A311C53C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$42F1AC68-2DEC-4C85-BD55-80E970B10EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$D1D2AD2D-DA81-4CBD-8EDD-1ADBECA2BF1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c317ee9b89d25866849eff84487be5a7c7991b60","datavalue":{"value":{"entity-type":"item","numeric-id":3331209,"id":"Q3331209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$E925A650-6249-4D87-B94F-2D9B63184227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70306059efc5cfdc79f64e589d6ffc1d802b2d37","datavalue":{"value":{"entity-type":"item","numeric-id":4481137,"id":"Q4481137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$9D4D3AB8-C0AC-492A-A2B5-5411B6DD0912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$66FB99FB-AAD1-41BE-B5EC-7B8511658F6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1c048b723c40fb7935338c90d19de4fa0f92c9b","datavalue":{"value":{"entity-type":"item","numeric-id":1242177,"id":"Q1242177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$D7BBD5D1-35E4-4004-B2D5-AE8958B864DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2d254ca8fb3622960c286f7a70ba1cd8e251e97","datavalue":{"value":{"entity-type":"item","numeric-id":3899820,"id":"Q3899820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$3A01B92F-2FFE-4339-88BE-ED4A791618F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"030033d07b50186b8804f9e608c60d87b820488d","datavalue":{"value":{"entity-type":"item","numeric-id":3907407,"id":"Q3907407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$775A2495-0B53-4026-BFCB-F734D5EB38FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76669984a6ac0b0c6e637a208d87de19004660b7","datavalue":{"value":{"entity-type":"item","numeric-id":3050132,"id":"Q3050132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$71FB0032-D918-4348-95B5-C49D5C39D5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9947b17f31dff2fa734150ed6f87b6dd7b94d7c3","datavalue":{"value":{"entity-type":"item","numeric-id":1226442,"id":"Q1226442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$4C257EE2-A5EE-4BBB-A397-BAFCC6C6CFA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aea16417b6b5932cc8cc24e2cd2f57dbdb5775f","datavalue":{"value":{"entity-type":"item","numeric-id":3673580,"id":"Q3673580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$A44DC46C-D301-440A-A1CA-99A59F5D6C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"789ee20fdb8192c506df7d27a9ec5729e533955b","datavalue":{"value":{"entity-type":"item","numeric-id":594910,"id":"Q594910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$3FFF2952-9F67-43AB-992F-524B0938EFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"102773d10765ac7344d721acbb33968c8260163f","datavalue":{"value":{"entity-type":"item","numeric-id":1153123,"id":"Q1153123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$015A4BF3-D2A2-4987-BAAC-43A9E2D46906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaa595c975cc96f28daa1bd7521f98f77aeacc40","datavalue":{"value":{"entity-type":"item","numeric-id":4083731,"id":"Q4083731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$BAB49AD5-6B4B-4C57-911C-B07FCC116516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95a97002b5e1356e03245a78764fba49aca08c0a","datavalue":{"value":{"entity-type":"item","numeric-id":594113,"id":"Q594113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$928B30E1-8E53-4C08-8C3D-85213A85CC72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070255$BF1F04BA-2DE5-4810-A00B-4AFA7491184D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"667a6d07c941024aae318b75076f0c0002f7e46c","datavalue":{"value":{"entity-type":"item","numeric-id":1920323,"id":"Q1920323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b3a7b47a63618e89c96b3a0c0da65dc5ed87bce","datavalue":{"value":{"amount":"+0.8570512533187866","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":"Q1070255$6A090879-D6B5-4279-AEB8-C7188E30E2FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a487076a778feddf7ab056e6e41b7e079e177967","datavalue":{"value":{"entity-type":"item","numeric-id":4542628,"id":"Q4542628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ee7ccf9e0d9e7b6070a6815a6a46374fc6ead74","datavalue":{"value":{"amount":"+0.8250164985656738","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":"Q1070255$ADC7C409-4F6D-47EA-8CDD-D3B3F191F6C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1d99c39e4a60a3272e2f4342211f082563accbf","datavalue":{"value":{"entity-type":"item","numeric-id":1353999,"id":"Q1353999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d79737c69eca0ab9fa5351b12796e8da3490c5ad","datavalue":{"value":{"amount":"+0.8207398056983948","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":"Q1070255$F9AD7E86-51CB-4CDA-854D-1B89030A1B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"902f4e253c946f60878bdcf809e3824d0e68c314","datavalue":{"value":{"entity-type":"item","numeric-id":4295376,"id":"Q4295376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afabadf5df535970f61dc22ff954506cdf1f4541","datavalue":{"value":{"amount":"+0.8197673559188843","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":"Q1070255$A5D15775-B293-4E36-A897-E7BCE68EBC4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d50a8bad94e703878221a430704e19c00edf0331","datavalue":{"value":{"entity-type":"item","numeric-id":1183343,"id":"Q1183343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe5587e65273056e6bd5949990e2a99d89d631fd","datavalue":{"value":{"amount":"+0.8173576593399048","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":"Q1070255$186231A7-0A79-4608-9E5B-F6B070328383","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Uniquely solvable quadratic Boolean equations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Uniquely_solvable_quadratic_Boolean_equations"}}}}}