{"entities":{"Q1589640":{"pageid":1600380,"ns":120,"title":"Item:Q1589640","lastrevid":74067753,"modified":"2026-04-14T18:14:52Z","type":"item","id":"Q1589640","labels":{"en":{"language":"en","value":"The complexity of approximating MAPs for belief networks with bounded probabilities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1542380"}},"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":"Q1589640$390B8DC5-DC1E-4A68-AB23-78885CF9CC2F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"560b5ea2c6783d220477a2e6c162f1fc9e0184dd","datavalue":{"value":{"text":"The complexity of approximating MAPs for belief networks with bounded probabilities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1589640$A9EF62F5-F3A0-4E72-A4A4-C27DCDE6EBC9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"12c5055cdae9954ca8b42445fc0952d464d6a6bf","datavalue":{"value":"0952.68137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589640$E719ADA1-3922-4327-8B4C-D0ED456D644F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c3a637c9021e504a8dabba779b2c17b6895fc257","datavalue":{"value":"10.1016/S0004-3702(00)00076-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589640$C10AA015-3443-4663-81D3-9F9D29FE21EA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$5DD1DA9A-197A-4CB1-B56F-07669D2D8908","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1589640$9CF76561-46FB-4B44-9BC3-DBA01D3525EA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"583255ec309f220a327228cb0b849275bf44994f","datavalue":{"value":"Probabilistic inference and Maximum A Posteriori (MAP) explanation are two important and related problems on Bayesian belief networks. Both problems are known to be NP-hard for both approximation and exact solution. In 1997, Dagum and Luby showed that efficiently approximating probabilistic inference is possible for belief networks in which all probabilities are bounded away from \\(0.\\) In this paper, we show that the corresponding result for MAP explanation does not hold: finding, or approximating, MAPs for belief networks remains NP-hard for belief networks with probabilities bounded within the range \\([l,u]\\) for any \\(0<l<0.5<u<1.\\) Our results cover both deterministic and randomized approximation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589640$54C75D8A-0834-46ED-89A2-BCADF33AA79F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"73dccdfb072fb026a86af92d74fe625efeb2b023","datavalue":{"value":"68T35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589640$A5A3B6E1-8B2F-4E17-9E8B-1A7E30DAFC77","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c436b5dda6bff31fd7b3ea3dfd343b462e4dddb7","datavalue":{"value":"1542380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589640$DE88EDC0-1E97-43EB-8745-9183F0C8E74E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d3e15248c5f657d472cfba9628c110a4f8eb4bf","datavalue":{"value":"Bayesian belief networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589640$ED2139F4-0864-40F1-812A-B9150A6BE158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589640$A5B8D975-17B9-4DB7-A924-AFEACE7489AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e30b6d1c583f669dd21c5544d26c9cefa30e9b6f","datavalue":{"value":"local variance bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589640$AD100E86-939A-494F-A313-57DDC06A1276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589640$B2186AEC-ACD0-4ABB-AD90-84330D88BCEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1c826d014febccd145f8df62027c93a945024fd","datavalue":{"value":"bipartite networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589640$A23B5AFF-098A-4F8A-82DD-9C517EF6B6FD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37f31913a07bc5886526ba84fc7c778cfbe9c93d","datavalue":{"value":{"entity-type":"item","numeric-id":814634,"id":"Q814634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$F2DF3A91-7640-4825-B028-FA16A2D042AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c9d1c9ba6bd3f4aa96f0d37d0211dfaad48b281","datavalue":{"value":{"entity-type":"item","numeric-id":251500,"id":"Q251500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$34280861-AA07-44B1-BAC8-27280A96625A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"02fe7a3dd95d4f575fdd1e87792efc404d271632","datavalue":{"value":{"entity-type":"item","numeric-id":251499,"id":"Q251499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$800C3A03-1604-4AB6-AE26-38A47E405E34","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":"Q1589640$5338E8C3-E716-4D91-A50B-F901132C5EFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"974915c5b75867256e6e8d9689abfb88012c9871","datavalue":{"value":{"entity-type":"item","numeric-id":1274288,"id":"Q1274288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$27898212-C41E-4F30-AD1D-E613AE66C260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4bf152ea9e9f5bb6248f2fb9d697fe65f43d7b0","datavalue":{"value":{"entity-type":"item","numeric-id":2638807,"id":"Q2638807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$D82851A8-5DEB-4472-B969-FAE34F53CF41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"534ff8b5a77e26210ff19ce11ff3c166c43b18fa","datavalue":{"value":{"entity-type":"item","numeric-id":685336,"id":"Q685336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$C8A451C2-9981-4C0B-8A5A-6AAD2F79B34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa2f0a71ae44c25d40a6b230efaf9d4a4bdb8f3","datavalue":{"value":{"entity-type":"item","numeric-id":1402716,"id":"Q1402716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$FADAA0FC-05E1-4AC4-A353-3E50A4D50288","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":"Q1589640$58B87E96-320B-466D-8109-C44FFDAD8FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$16400F1D-7FFC-4A34-95F6-061FA0FF034A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d8f9f7d907e8c287ef5ce0badd00f75247aa15f","datavalue":{"value":{"entity-type":"item","numeric-id":578932,"id":"Q578932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$B8684719-9E50-4EE8-B69B-817EE7D030D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6a368b6605ae7cdaf487148afccbd67173ce3ec","datavalue":{"value":{"entity-type":"item","numeric-id":1332845,"id":"Q1332845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589640$B102856C-A518-43D0-B509-199E85B7EBE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdd49ee82daf4ebea4c5beb37f0d8bb56aa1a202","datavalue":{"value":{"entity-type":"item","numeric-id":1274288,"id":"Q1274288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"479d55de0289dc49c4f30e785027aed9105cd6db","datavalue":{"value":{"amount":"+0.9291019439697266","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":"Q1589640$9CB609B9-B0EA-4927-911C-22D351188975","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73ed062e2cd292e6fd3a11e207e94cca5b5f69ad","datavalue":{"value":{"entity-type":"item","numeric-id":5715665,"id":"Q5715665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bad5612fbe165db964a16616d5470917ad3054f9","datavalue":{"value":{"amount":"+0.8956424593925476","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":"Q1589640$333B8A89-407A-47B5-BC66-61DAA09C427D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d99e18726d80a6992d92649435c7d604e5e205f","datavalue":{"value":{"entity-type":"item","numeric-id":685336,"id":"Q685336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67fb5a3a288fc1c5497309119cbeb584a6026a51","datavalue":{"value":{"amount":"+0.8720378279685974","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":"Q1589640$269D7206-CBEF-4A59-BAF5-7DFAEAE6B31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcd747ef2d35dc623f69eb8728a0a40c6508399d","datavalue":{"value":{"entity-type":"item","numeric-id":2938412,"id":"Q2938412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67fb5a3a288fc1c5497309119cbeb584a6026a51","datavalue":{"value":{"amount":"+0.8720378279685974","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":"Q1589640$96661035-A136-4939-B6B9-90F37BC24A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a60f9dbbf7fe5f89c61587ecb129b188a6d138c","datavalue":{"value":{"entity-type":"item","numeric-id":1332845,"id":"Q1332845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5895640184df5cc172b4d609761a411a93235f22","datavalue":{"value":{"amount":"+0.8663727641105652","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":"Q1589640$9D989D6B-27AB-4C95-A7D1-381775629E03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of approximating MAPs for belief networks with bounded probabilities","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_approximating_MAPs_for_belief_networks_with_bounded_probabilities"}}}}}