{"entities":{"Q1961461":{"pageid":1972203,"ns":120,"title":"Item:Q1961461","lastrevid":72038823,"modified":"2026-04-14T02:15:20Z","type":"item","id":"Q1961461","labels":{"en":{"language":"en","value":"On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1389878"}},"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":"Q1961461$753752A6-424B-4B34-BE69-270D952E46DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"33a41bff26752987c5deeb1fecbbef7474bb1950","datavalue":{"value":{"text":"On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1961461$1F7E0472-9D1C-4DA7-AC84-A689B32ECDBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"987aabe9277a333030353628a4fcfebe1a35c30c","datavalue":{"value":"0953.06013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961461$109C136F-CF19-43F6-AF84-F46303E22BD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8954042213bbe220e9a26daa5299c51eef8b89f4","datavalue":{"value":"10.1016/S0166-218X(99)00099-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961461$C39D3D29-90E0-421F-B2A4-0A360E21D901","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":"Q1961461$3EB387F0-C364-4FF8-8599-87B67DBF906E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"71e784f7cfaa48fae228ecd4530139eb05d7e87c","datavalue":{"value":{"time":"+2000-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":"Q1961461$C7A9B020-4FEF-4EC7-BBE4-ECC0BD2D31FF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9a29f275de9841a644e713d016e573132faacc06","datavalue":{"value":"Suppose a monotone Boolean function \\(f\\) is given as a black box such that \\(f\\) for any input vector can be evaluated in polynomial time. The paper addresses the problem of constructing the set \\(C\\) of prime implicates of \\(f\\) and the set \\(D\\) of prime implicants of \\(f\\). The following result about the incremental complexity of this problem is obtained: For given sets \\(C'\\subseteq C\\), \\(D'\\subseteq D\\), an element of \\((C\\cup D)\\setminus(C'\\cup D')\\) can be produced in quasipolynomial time. On the other hand, it is proven that if uniform sampling from within \\(C\\cup D\\) can be done in quasipolynomial time, then every NP-problem has a quasipolynomial time randomized algorithm with one-sided error. Further results concern the complexity of the problem, given \\(C'\\subseteq C\\), to decide if \\(C'=C\\), and, given \\(D'\\subseteq D\\), to decide if \\(D'=D\\). Applications to monotone relay circuits and game theory are pointed out.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$3689511A-4E38-4EF5-A550-E124BCDF1076","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$01AFF686-84B2-4DDE-9EF5-26706E55FCDB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961461$F5A76EF0-E2E9-4C69-B9A7-61F0170FFA73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961461$460C68EE-F170-4221-BB06-1C227C602E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961461$4784AEBB-24A7-4F9C-A274-271BD46A3E50","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b2191990668105191ea33edd4d878e6023f6ec3b","datavalue":{"value":"1389878","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961461$233D0149-B0B2-44E1-AA73-ED6FEBD2463E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44c981e906dd6aca27c197b7f1a7dd615078a545","datavalue":{"value":"monotone Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$76C52197-9022-4AC6-A19A-5B0A4D4C32D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"828e479c39c5c64293eb95e0403dbef7bbf79066","datavalue":{"value":"conjunctive normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$C99C1D8B-48D6-4642-BF6D-757860B41996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b17f05e4289c7582cd773cdd4edb907a56b3cc","datavalue":{"value":"disjunctive normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$3CB8B035-3BC3-43A7-9D38-A355CD9F7383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f792d6af457f56decacb63c84275df692782d093","datavalue":{"value":"prime implicate","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$7F819119-FA92-4DAF-BAD9-2D7CB767A5BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"daa5a720b9303b661dc79e2ba472f49f3f1baadc","datavalue":{"value":"prime implicant","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$71183DC3-8CD5-428E-92B2-C0CB026BAA82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$FFE5F91E-9AE5-4C68-8D9D-0498FF039076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dad093387c12fdb02b8019267fd899d3a600d46a","datavalue":{"value":"quasipolynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961461$E9984DAF-DB73-4EF2-AC8B-D564B7FAB208","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4df2688b2437516b3f79c8112e320cdff04c56ca","datavalue":{"value":{"entity-type":"item","numeric-id":923675,"id":"Q923675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$3EEFB388-9FD6-4749-934B-73A689788DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1419842bb8e98ef67f2bea44989c52cd03b97a03","datavalue":{"value":{"entity-type":"item","numeric-id":1315410,"id":"Q1315410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$6A6EF568-50F3-46A1-AC36-948578A602DF","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":"Q1961461$6570259B-822B-446E-88F5-36C1520744E4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d546340ddfe5fda8eb7b2c0d584ebd8a3b4ab960","datavalue":{"value":{"entity-type":"item","numeric-id":2508337,"id":"Q2508337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$D201DF96-40CE-4957-91B7-314617FB4A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64d71127182ed5b318aeac03375272555a0745cb","datavalue":{"value":{"entity-type":"item","numeric-id":4946700,"id":"Q4946700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$7E99B693-FA11-4366-8BF4-5207C6FF0CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d480e9df94b7466b2d1a2ed0fa6cca9dbe2d90ab","datavalue":{"value":{"entity-type":"item","numeric-id":1084376,"id":"Q1084376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$AC3460D5-04B0-49E0-A50F-3841D9F51E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f2baff2b3fcd933b421c46ded9fa320ffaaebb6","datavalue":{"value":{"entity-type":"item","numeric-id":4862797,"id":"Q4862797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$6CBB460F-0E82-43E8-8079-B96D1B50FDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b733d3c598f4f60dac05c662888fe6ef36a0cf8","datavalue":{"value":{"entity-type":"item","numeric-id":3837390,"id":"Q3837390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$A9F05EE7-7BF6-4E13-80E2-B86681C69CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf4bfd1f65b22fa6864f386deb5639d93211821f","datavalue":{"value":{"entity-type":"item","numeric-id":4766839,"id":"Q4766839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$98405CAD-B21F-4B3C-A78D-ED881DAEA51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"704ba16a22bc530121d9b3ff81eb4535436473c6","datavalue":{"value":{"entity-type":"item","numeric-id":4120519,"id":"Q4120519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$03A24691-FA78-4D1A-810B-DA230D317DC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7678cadff422dc18fb5c6f9d2c4055e1ab7c4be8","datavalue":{"value":{"entity-type":"item","numeric-id":1079379,"id":"Q1079379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$862D2360-0485-4B37-BA80-962AF144664F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5ba7598a622756daa7a1a98c7ec39119480164a","datavalue":{"value":{"entity-type":"item","numeric-id":1108809,"id":"Q1108809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$2CCF5DFB-F8B9-412D-9DAD-0ABD192DE909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd71ce55d99f883144a663aae560653a67882827","datavalue":{"value":{"entity-type":"item","numeric-id":685684,"id":"Q685684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$4230E65A-05DE-454B-80DC-892E0F586A6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45558739a1380325e41235ea81c2d7698843ce9b","datavalue":{"value":{"entity-type":"item","numeric-id":1079111,"id":"Q1079111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$4584308B-48BC-447F-A4CF-805DD950880F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30c2d6a6a6363c849fcdadf43c8465316d369269","datavalue":{"value":{"entity-type":"item","numeric-id":1327236,"id":"Q1327236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961461$D27E6927-FD8E-4751-9C94-A06AA88D9695","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"137c5741ffbc15dd6339fb23ad8904bacb871b6c","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00099-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1961461$19BF9D00-1697-4E42-A332-FD2A9DFBD505","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2d7de1d543c8430f3478905f7ec9f7eb3348dc8e","datavalue":{"value":"W1996070840","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961461$2F87A732-6861-4A93-BEAB-36CF913A26C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bb0fc619e262e860126e0e4bd17eea37b06a2c1","datavalue":{"value":{"entity-type":"item","numeric-id":943839,"id":"Q943839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d5d95930bd2cc5b1e6719a3a237a8a660bbd3b7","datavalue":{"value":{"amount":"+0.8099731206893921","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":"Q1961461$2C517F5C-7A5A-4992-AB91-82C25283EA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc4f5038ed7783ddee35feb910b741ff4883c7cc","datavalue":{"value":{"entity-type":"item","numeric-id":808253,"id":"Q808253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc56604411d3b7f5bc7fe6969dc31d4a9df60cab","datavalue":{"value":{"amount":"+0.7849476337432861","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":"Q1961461$C734A6D2-168A-4F14-9A01-03745B00519F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ecac5c5c4c2ce3242aa3619590051ba9c28fbe","datavalue":{"value":{"entity-type":"item","numeric-id":1121854,"id":"Q1121854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50e7e73e7efcbc943165c6a6374928e348a124e3","datavalue":{"value":{"amount":"+0.7834282517433167","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":"Q1961461$21935DD2-9048-4718-9B3F-870BA174895D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c3f80a5671f9f7cfdbfb0b718a48226aa1070b4","datavalue":{"value":{"entity-type":"item","numeric-id":3807127,"id":"Q3807127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e10957663f8faa502917eb9bc4df42680e6aaeb","datavalue":{"value":{"amount":"+0.7832057476043701","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":"Q1961461$C50CEA2D-F04B-4144-B081-D236DE417A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a00d0f99364b03a4d62ccffd44a575b00091e21","datavalue":{"value":{"entity-type":"item","numeric-id":1099134,"id":"Q1099134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e919435ad8e3a12b343eefdebf5987196f80c4f3","datavalue":{"value":{"amount":"+0.779310405254364","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":"Q1961461$CDD8443B-809A-4E52-8789-B9A08D92CF01","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions","badges":[]}}}}}