{"entities":{"Q685336":{"pageid":687185,"ns":120,"title":"Item:Q685336","lastrevid":47188717,"modified":"2025-12-31T23:08:57Z","type":"item","id":"Q685336","labels":{"en":{"language":"en","value":"Approximating probabilistic inference in Bayesian belief networks is NP- hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417255"}},"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":"Q685336$F4BC1BF7-B8D9-4141-B82E-AA4C9B6643AF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ceb7705218ef7bf1a3fa01b6ff4a127f94d44f2b","datavalue":{"value":{"text":"Approximating probabilistic inference in Bayesian belief networks is NP- hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685336$4F7F2D80-94B6-4418-AB9A-1A9814078370","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78e7ab8c9fe6239cf6fd4add6e2402a8eee181a3","datavalue":{"value":"0781.68105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$7E500FCD-479C-4148-BA2A-EF9B1DD99B5E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fee0c8e5341ea445fabc6e9561ee9f999ecc4bbd","datavalue":{"value":"10.1016/0004-3702(93)90036-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$A313C611-43F2-4F20-ADDA-2DABEB69388E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2dac9fe503c757deee8a22f6ceeb841281474d7","datavalue":{"value":{"entity-type":"item","numeric-id":685334,"id":"Q685334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$505D8918-D08D-40B5-8E1F-2A8D73206EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d5a2f70848f5f6284f8ed2480b6f2c9e1c6ebac","datavalue":{"value":{"entity-type":"item","numeric-id":685335,"id":"Q685335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$D47C12AD-2B99-4900-92E1-3EC9C6D4DE4C","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":"Q685336$F8915E86-4194-4DED-8902-CC3A07EA7973","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8ece7c460c78874e314a441f2bb630645a5e7532","datavalue":{"value":{"time":"+1994-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685336$6D35CC37-23E8-48DF-BCE4-0697F4881CC6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ed4fb8ca0c92089fe6e5b2126a4b9e5702883fd6","datavalue":{"value":"Using the reduction method of \\textit{G. F. Cooper} [The computational complexity of probabilistic inference using Bayesian belief networks, Artif. Intell. 42, 393-405 (1990; Zbl 0717.68080)], the authors show that the problem of approximating conditional probabilities with belief networks is NP-complete. In particular, the problem is shown to depend on the ration \\(\\lambda\\) of a priori bounds given for the probabilities. If all probabilities between \\(n\\) events are in an interval \\([1,u]\\subset[0,1]\\) and \\(\\lambda=u/1<1+(c\\log n)/n\\) then the problem is known to have a polynomial time solution. If \\(\\lambda\\geq e^{cn}\\) then the problem is hard. The problem therefore is to find a best and a practical upper bound for \\(\\lambda\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q685336$BB7D8B4E-F147-405B-813D-818B5A407BE7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c6e71133293256880be082f6af9aa793c57d433","datavalue":{"value":"68T30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$F6CFB400-C25A-4E93-8FB8-0768414CB0F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$59209841-E8A4-4813-8B1F-257FBDFB64A6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b05591d30af2dd3cfadcaa694f9f11b6b382069f","datavalue":{"value":"417255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$418DF1C7-0B43-4710-A2EA-814B079ECAAB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9dc9b73fc444cc1b38555253b38658bd6af84570","datavalue":{"value":"conditional probabilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q685336$AE06F607-65AB-4245-AABE-8DE2B53678DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c63c64eec4ee7c55386f1b08fedb7432f70cc8f9","datavalue":{"value":"belief networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q685336$114D246A-0540-45E7-8597-E55B7A48D98A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q685336$6FF51606-11EA-4E54-90E2-891A338DFD96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q685336$8B5ABA2A-5F4B-45C3-A1A8-68DF2E019041","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"751d755f11ace2ea1831b76816176f760c177666","datavalue":{"value":"Q56158129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$BEED0B19-B2D2-4053-B5AE-BA13675C0CD7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0bc1ba0153f6b56c7993aa16e6cc67921cafc2a4","datavalue":{"value":{"entity-type":"item","numeric-id":590887,"id":"Q590887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$781B7908-97F1-4232-A5C2-43F2E5CA60E0","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"a61cf74f87999e3dc646a8cf7f71b2fcd1f0160e","datavalue":{"value":{"entity-type":"item","numeric-id":33892,"id":"Q33892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$B7CB6E80-5406-4727-8056-F24FBFE28192","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":"Q685336$BFDA6DE6-1AD4-4C4A-A0C1-52E4B5192911","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"683a0223762aa76320d24ba17e826f24166361e6","datavalue":{"value":{"entity-type":"item","numeric-id":5751997,"id":"Q5751997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$87B01F9B-5BCD-4607-A642-43FDEEB3D3DC","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":"Q685336$E3163504-6516-41E4-A9F8-234423A5425B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9928b24473c7613de1beeb7a565c359330129f90","datavalue":{"value":{"entity-type":"item","numeric-id":5753554,"id":"Q5753554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$E18B77A5-0A36-4D2D-8090-111FC7B299B2","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":"Q685336$27E519CD-4215-4861-9C07-8A3CBBB5B6A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88a2664c1b3e1960e78dde90130ce037f486590e","datavalue":{"value":{"entity-type":"item","numeric-id":3795276,"id":"Q3795276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$73BDFE19-F4B3-4E3A-AEA3-92DE5E2E1F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42e0bb807cb1e76125bd2bd84d948ce5d029bcee","datavalue":{"value":{"entity-type":"item","numeric-id":3200590,"id":"Q3200590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$E9AB36F7-0AB9-4645-A413-F6248339B122","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":"Q685336$EA0C1566-C33E-4106-94D5-61CD1B92672C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0c77e2c400c2b614ebb25c1389526a66495e490","datavalue":{"value":{"entity-type":"item","numeric-id":1101266,"id":"Q1101266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$19E17419-577C-40B8-AC05-069F5C1F914D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a8a6275b23ecd525d85490cb57f6d8c8d3bd4b8","datavalue":{"value":{"entity-type":"item","numeric-id":3775000,"id":"Q3775000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$6B55F3D9-5812-499B-82AA-C8F95EA4211C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cddb6ac6ea10c04636addd1e306a08742a3ae37d","datavalue":{"value":{"entity-type":"item","numeric-id":3775001,"id":"Q3775001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$312BA6D8-8CE5-4AE4-9969-4393CB2B95A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43b0cdf24108b31610aa50c186f9af0e7ff5a96a","datavalue":{"value":{"entity-type":"item","numeric-id":5753569,"id":"Q5753569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685336$A26CF87B-C121-4564-AA2D-1E7E15FF2F32","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4744a9bf54eef1e4a7d91f6d6c61a0e5126cefb9","datavalue":{"value":"https://doi.org/10.1016/0004-3702(93)90036-b","type":"string"},"datatype":"url"},"type":"statement","id":"Q685336$30735B73-EBEC-42EE-96C9-CFB4A7E53F17","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51f641f060e36b84abefe203b05f5595e90c73ac","datavalue":{"value":"W1999432334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$C5766153-6641-4165-BB2B-F753FB3BA27F","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"ca98ae6a10a8d5b8a8d5a407f9389f823f92e18e","datavalue":{"value":"journals/ai/DagumL93","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685336$2D04D177-916A-41CF-9792-04381F59BE16","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"023b5654d12740bbd4b5ac3343f08f71540ff9ea","datavalue":{"value":{"entity-type":"item","numeric-id":1402716,"id":"Q1402716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c51e336c756c7b407c01770583b429a1a08c4e1","datavalue":{"value":{"amount":"+0.884024441242218","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":"Q685336$D5D32B63-4418-40B5-BA91-EB1E7B255EC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"946232f2a24aad5a96af56cf8f55226eebd4080c","datavalue":{"value":{"entity-type":"item","numeric-id":2638807,"id":"Q2638807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c51e336c756c7b407c01770583b429a1a08c4e1","datavalue":{"value":{"amount":"+0.884024441242218","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":"Q685336$9E9A4DAB-8001-4158-A840-A494B99A38DA","rank":"normal"},{"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":"fca21b68fe98a188bd0fd23a1e6d146092c843c0","datavalue":{"value":{"amount":"+0.8755589723587036","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":"Q685336$BC952D6B-2F34-4DC5-A3C7-3869ED690DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41d4172f26822dc61e0ad112f1474bc54791ef3a","datavalue":{"value":{"entity-type":"item","numeric-id":1589640,"id":"Q1589640"},"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":"Q685336$63C1053A-9A19-47EB-999F-8A2524205107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3db8f0921dd697be56bcc7608ef0a067675f2255","datavalue":{"value":{"entity-type":"item","numeric-id":840823,"id":"Q840823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da8e7a46441c5371f69d85dca7c4f5c71d3548d1","datavalue":{"value":{"amount":"+0.8720372319221497","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":"Q685336$385E210A-9704-4DEB-96D0-D529A91D1497","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685336","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685336"}}}}}