{"entities":{"Q1382588":{"pageid":1393328,"ns":120,"title":"Item:Q1382588","lastrevid":70294302,"modified":"2026-04-13T13:48:30Z","type":"item","id":"Q1382588","labels":{"en":{"language":"en","value":"Recognition complexity for Schaefer classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1134952"}},"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":"Q1382588$C8E44C83-D741-486D-A453-A385FDA2C6ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"edcc4e212dc0e3bbb24461e73d80283be3d84df4","datavalue":{"value":{"text":"Recognition complexity for Schaefer classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382588$FDDB7E27-FB08-4867-BE64-F857FAE9F89B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"71163d55b56949284acc2705b7c06b0abb11b68a","datavalue":{"value":"1026.94555","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382588$75CDB96E-6BD9-4DF2-AD61-06D64E198025","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca6231b7b3fab19b55afefcddb74b4b29eb2a436","datavalue":{"value":{"entity-type":"item","numeric-id":1382587,"id":"Q1382587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382588$DF3231FF-1864-44DB-81AA-9010FA6FF4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de9916b031f122f334a38c9e992c74ad73fff454","datavalue":{"value":{"entity-type":"item","numeric-id":548754,"id":"Q548754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382588$578D31D3-78E7-4A49-BF96-C655C5950B98","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6c13805eb53dbd00bf0343bc22d19b4be9e16872","datavalue":{"value":{"entity-type":"item","numeric-id":187667,"id":"Q187667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382588$5AEB12A5-F640-4115-BDD7-EC02334C510A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c2c9ed8805e87613d39976a3d7f078fb3b47b839","datavalue":{"value":{"time":"+1998-03-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382588$EB29B3AB-BCE0-45F8-94C3-545A33737AF6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b5a7f7cbf751808d586e108102c7ce0a9dc695b9","datavalue":{"value":"Let \\(F = \\{f_j(x_1,x_2,\\dots,x_{k_j})\\not\\equiv 0\\mid j\\in J\\}\\) be a finite set of Boolean functions set in conjunctive normal form (CNF). The class of various systems of equations  \\[  \\{f_{j_i}(x_{i1},x_{i2},\\dots,x_{ik_{j_i}})\\} = 1,\\qquad i = \\overline{1, m}  \\]  is called the class of \\(F\\)-systems for any choice of the functions \\(f_{j_i}\\) from \\(F\\) with any finite number \\(m\\) of equations in each system and for any choice of unknown \\(x_{ij}\\) from the set \\(X = \\{x_1,x_2,\\dots\\}\\). The problem of \\(F\\)-jointness is a problem of jointness recognizing an arbitrary system of equations from the class of \\(F\\)-systems. The set of functions \\(F\\) is called \\(P\\)-set, if there exist a polynomial algorithm solving the \\(F\\)-jointness problem and an \\(NP\\)-complete set, if the problem of \\(F\\)-jointness is \\(NP\\)-complete. The author proves that the problem of recognizing multiaffinity, bijunctiveness, weak-positiveness and weak-negativeness of a Boolean function given in CNF is \\(NP\\)-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382588$62A56803-0A96-46A4-A801-894F9E8E7529","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382588$FB15B1B4-178C-4488-A33A-5B62EDB81ACB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8cb209bcae85af3f865b408a8ec17bb5abe784c8","datavalue":{"value":"1134952","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382588$940BABB5-E376-4226-850E-05DEC3166450","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce5829f792402351c9e1151b859e10832ca081e4","datavalue":{"value":"Schaefer classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382588$1DA189F3-E7A8-4EBC-8DA1-EE373A14D31B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9891227b3d7ca9f091fdc17473271d45c5e2f962","datavalue":{"value":"recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382588$40EC3F78-5EF5-4E60-BEF6-EDE730E5C2E1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c8642b90facb009fac3e5d2aeec487d0b254cbd1","datavalue":{"value":{"entity-type":"item","numeric-id":593066,"id":"Q593066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382588$5B8FE8CE-3CF8-44C2-8195-B89C1247E2DB","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":"Q1382588$55E2D118-BEF7-4F4F-90DC-75DE6BCF9D38","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28ce3401e6f4707715d6b340c2a81ab0df3db645","datavalue":{"value":{"entity-type":"item","numeric-id":5152404,"id":"Q5152404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e38d76e15216fba478b5b8c7451740488b7a749","datavalue":{"value":{"amount":"+0.8372721076011658","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":"Q1382588$0F5FFBD9-6AED-427E-8619-6DB92F2948F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"416c7150fb82d05b6c50f3fba88cb3db985a24f0","datavalue":{"value":{"entity-type":"item","numeric-id":4889745,"id":"Q4889745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27b0d51683eacf88586f7bc8a6d07b50344621bb","datavalue":{"value":{"amount":"+0.7990313768386841","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":"Q1382588$E915E8B7-4F88-4E33-A95C-D0262045D525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d7b5aa6105897002edbf9d938233d27a7139242","datavalue":{"value":{"entity-type":"item","numeric-id":4409643,"id":"Q4409643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c7321ff65f96d916b4adb73ffced00cd717ef29","datavalue":{"value":{"amount":"+0.7867121696472168","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":"Q1382588$0B73DFAE-95F4-4CC8-BE0D-B8D66D580EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a6bbb5e1a3a2447aa22aa16e34f75135c5de521","datavalue":{"value":{"entity-type":"item","numeric-id":3474280,"id":"Q3474280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9cd93c8883788ddc9526c817fec7795babe435a","datavalue":{"value":{"amount":"+0.7748500108718872","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":"Q1382588$BE561C19-3A6A-47C0-A334-68676B19C100","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":"00fa98408eeb798d4f60cd659fdb83ec2e3d64e2","datavalue":{"value":{"amount":"+0.7722386121749878","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":"Q1382588$E3E7296D-60E3-4A1E-8D46-2944B69BE9D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognition complexity for Schaefer classes","badges":[]}}}}}