{"entities":{"Q1190989":{"pageid":1201738,"ns":120,"title":"Item:Q1190989","lastrevid":46265413,"modified":"2025-12-24T10:46:57Z","type":"item","id":"Q1190989","labels":{"en":{"language":"en","value":"The complexity of circuit value and network stability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 58811"}},"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":"Q1190989$76367B30-7DA2-46A0-84EB-93CDAC673568","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a175de6cb1670588bf14b2eea1555c35237f0f6e","datavalue":{"value":{"text":"The complexity of circuit value and network stability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190989$D7B95E62-4F7E-4F9C-88E7-66992E154CDA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f9e1105a6b0ddcedd6597be5c1afdbd93d6f6900","datavalue":{"value":"0762.68024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$C7AF6E96-360B-44A6-AB9C-C5C9BAED5B87","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b7a825dbbbcd6ab5fcd5bec60d0f20b3dedfdf50","datavalue":{"value":"10.1016/0022-0000(92)90024-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$0A30F20C-0BDC-4E5D-84D1-7D9DEC13B1C4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"68c4b94b0ca0db950e9a6edb7d9f702fbbaf834c","datavalue":{"value":{"entity-type":"item","numeric-id":169355,"id":"Q169355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$D2F3D5A6-84C4-4653-8B44-761B22E8B78B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"75208198a96ae3d913f60f67f3a3d926578644d3","datavalue":{"value":{"entity-type":"item","numeric-id":674175,"id":"Q674175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$B626A050-1320-4C28-9912-FB2044B373CD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$881A4058-DDE4-4578-9841-6874E833D046","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1190989$EAB74C25-A6C6-478C-8AA1-28D5112DAE6F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f6db25a2188755141ee5b5575a65d3f24838f842","datavalue":{"value":"The circuit value problem over the basis \\(\\Omega\\) (\\(\\Omega-CV\\) for short) is the following: given a circuit \\(C\\) over the basis \\(\\Omega\\) and an input vector \\(x\\), decide if \\(C(x)=1\\). The network stability problem, \\(\\Omega-NS\\), is: given a circuit \\(C\\) over \\(\\Omega\\), an input vector \\(x\\) and an assignment of values to the edges of \\(C\\), decide if this assignment is consistent with the computation of \\(C\\) on \\(x\\). The paper deals with the complexity of these two problems for various bases \\(\\Omega\\). When fanout of the gates in \\(\\Omega\\) are appropriately limited, some positive results are obtained: a parallel algorithm for \\(\\Omega-CV\\) which runs in time about square root of the number of gates and a linear- time sequential algorithm for \\(\\Omega-NS\\). Next, so called ``scatter- free'' bases are considered. These are bases all the gates in which have the following property: if we assign constants to any \\(k\\) inputs of the gate \\(g(0\\leq k\\leq fanin(g))\\), the new gate computes at most \\(k\\) different functions. It is proved that if \\(\\Omega\\) is a scatter-free basis that can simulate the function \\(\\neg x\\lor\\neg y\\) then \\(\\Omega-NS\\) is equivalent to \\(\\Omega-CV\\). The class \\(CC\\) of problems which are reducible to \\(\\Omega-CV\\) when \\(\\Omega\\) is the monotone scatter-free basis is considered. Obviously, \\(CC\\subseteq P\\). It is proved that \\(NL\\subseteq CC\\) and that a restricted version of the Maximal Matching problem is \\(CC\\)-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190989$01264334-7BA9-4AC6-AF44-F9E6194A4A0B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$1A875263-0C93-4D5C-A05F-D21579A286EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$DCD61D64-4A5E-48AF-B353-FD2AC63A7595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$5585720B-CADA-4AF7-B2EC-E2352747CC30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$CF5BFE6D-C97C-47A7-8CAC-ED956162D4D8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b9bafd2ac0d1c2c614233b03d61cd03861339da","datavalue":{"value":"58811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$1683096C-98B4-42E7-9CBE-0F4B83243804","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bc1cc50e8d4b517f651118878724606a4faacd","datavalue":{"value":"reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190989$4839B3B2-1B62-44ED-B3EA-C0FE6D81F56A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8e6f852240922023371bb799d78cb9166df9587","datavalue":{"value":"circuit value problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190989$677C9F01-CAAB-4727-8ECF-B66FCA684310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"822eb7a6220b58cf96fa6d8a7da7093e5a26d994","datavalue":{"value":"network stability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190989$6AE4E7C2-F052-4611-8F2C-3B02186D3C64","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1833d190eb6492ca84e0c93a6ff12de5694705d3","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$8E9198B2-8373-4348-8517-5AE4A87266A0","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":"Q1190989$531B215D-0F9A-4C6F-B015-CC950FC8D8D3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e86a79bfcfca810fb7601492bd0551fae9de8408","datavalue":{"value":{"entity-type":"item","numeric-id":4142697,"id":"Q4142697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$FF29EDAE-B295-448E-8191-1678AE3E81BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6b13b2ba37a9810801d8784e6422607a5338cc","datavalue":{"value":{"entity-type":"item","numeric-id":4745254,"id":"Q4745254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$69E37D53-3691-4C19-85EE-5A1F2F2D6746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$92F4C048-4924-4A74-8C25-AFB8CB4798B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b23a99da8df474d603cdef7b4c76229f6a312c3","datavalue":{"value":{"entity-type":"item","numeric-id":3787477,"id":"Q3787477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$B661892D-B440-4386-9E3C-78EE9480335D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd41a3d3ffce78a856861213ff6553c14d782cc0","datavalue":{"value":{"entity-type":"item","numeric-id":5904119,"id":"Q5904119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$BC904B4E-E2E6-400D-B86C-F418D7FB69C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd898582b3042cd9f98f55a99a55f26af0712fb","datavalue":{"value":{"entity-type":"item","numeric-id":4128417,"id":"Q4128417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$C3847380-0DD2-422D-8F7C-C3BCFA3A31A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6690941b790d3f730c7ae6b7e325ad8391f2459","datavalue":{"value":{"entity-type":"item","numeric-id":1083204,"id":"Q1083204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$BF656EA6-49AE-4831-9419-1FBE2D358214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$B159B514-6AAF-4FB4-92B9-AEF5AAFAAF88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$F2A3C445-E084-42BF-8296-0881B5A2C691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$DCF5A049-B802-4F61-8448-AD5510DBEB3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84bbca1bd52a8b705768d2a03b4b5b5c1b7c0d27","datavalue":{"value":{"entity-type":"item","numeric-id":4385522,"id":"Q4385522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$92E96369-4F73-4D11-ADA1-689546D0495A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$D14ED6F4-72DF-45C3-9D00-78B318E2B718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92fa191d3fd93af0064a83ecf8434b6e5b925636","datavalue":{"value":{"entity-type":"item","numeric-id":4130997,"id":"Q4130997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$314F8F4D-F04D-4617-9D12-FD29ADAC496E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ef47a738eba0b33c21d022be5c49b064d45ce78","datavalue":{"value":{"entity-type":"item","numeric-id":3783600,"id":"Q3783600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$88EB080E-ECA7-4E63-B790-5F3C71601C06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b32bc7767be82b7f69c4a3a7574a2b39f4609fb","datavalue":{"value":{"entity-type":"item","numeric-id":1097640,"id":"Q1097640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$FFEE0904-14DB-421A-BF2B-68F1D066FD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd5291d4aaf0fe56994abe4132f5cb7c329d4895","datavalue":{"value":{"entity-type":"item","numeric-id":3768905,"id":"Q3768905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$2D9855A1-D3F6-4E88-BA11-D0D7E23E4E63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$716245DE-7A84-45E8-B234-24CC1B0488AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91e1d10e0c77de9812f317b0ff0d8727dd2dd83c","datavalue":{"value":{"entity-type":"item","numeric-id":3781088,"id":"Q3781088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$5370ED79-9A58-4657-BA93-BAF9CBBEB365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ec3127756c281caa855af31bc2faef43fe5d990","datavalue":{"value":{"entity-type":"item","numeric-id":4305353,"id":"Q4305353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$5F62BC1C-4D13-4F15-B19D-3A07FDE7A9AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186efa9cbcaad91d0d4ad1f36de56ca7d39bfe2e","datavalue":{"value":{"entity-type":"item","numeric-id":1099620,"id":"Q1099620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190989$ECD59752-40E8-476D-AE92-B50D0AFF8539","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"209a40c863f2eddbec5d6199b4b1e0090bd5e900","datavalue":{"value":"https://doi.org/10.1016/0022-0000(92)90024-d","type":"string"},"datatype":"url"},"type":"statement","id":"Q1190989$6985BCCB-816C-4D71-8F7C-73FFAC1F5C42","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8ee57d09a73dbaa9483560accec55017127e26bb","datavalue":{"value":"W2173502887","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190989$FF417A4D-A3BE-4A76-92AC-8E315472E6EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3f2c8fb6ad5a8690335febbe51dbad5530686a8","datavalue":{"value":{"entity-type":"item","numeric-id":2828221,"id":"Q2828221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7c93968780215b2b6976f98a7ef73c48ec84cc9","datavalue":{"value":{"amount":"+0.7618570327758789","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":"Q1190989$02E733FC-4393-4BDE-B4DE-128855AE9AA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a13b6460276e6589b65fc53a5ddbab3da4ab92e","datavalue":{"value":{"entity-type":"item","numeric-id":1083204,"id":"Q1083204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"039d7f304e11037470df4ae7c79e4f724c810507","datavalue":{"value":{"amount":"+0.7600156664848328","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":"Q1190989$D7DA646C-8681-4147-AE25-413F159F1726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a83b895d31fa24a83ac7f27f4abd5e9c81b33f5f","datavalue":{"value":{"entity-type":"item","numeric-id":626664,"id":"Q626664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca9f66be039d3b0cd4a23afe70d4b0b2ac324cf0","datavalue":{"value":{"amount":"+0.7348535656929016","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":"Q1190989$017661A1-E57A-4970-AD43-6885AC82E04A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"512c73ce13926c645c264f8d9af53c1f5b82b034","datavalue":{"value":{"entity-type":"item","numeric-id":4834386,"id":"Q4834386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07277bd187fe3cbfe26a7a90fb2cc4d2b341a376","datavalue":{"value":{"amount":"+0.7330725193023682","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":"Q1190989$2963080A-F477-4F97-850B-A3E239046271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf5f21ced0e92f1f2f603afbc2cb8f8004c7425c","datavalue":{"value":{"entity-type":"item","numeric-id":1384691,"id":"Q1384691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"807e39029d8718fa69b18ee7b73ae8eca7c60751","datavalue":{"value":{"amount":"+0.7190536856651306","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":"Q1190989$7C865F77-3D8B-4059-B69A-6343D055C054","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1190989","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1190989"}}}}}