{"entities":{"Q1083200":{"pageid":1093952,"ns":120,"title":"Item:Q1083200","lastrevid":42864466,"modified":"2025-07-15T12:42:44Z","type":"item","id":"Q1083200","labels":{"en":{"language":"en","value":"An analysis of Monte Carlo algorithms for counting problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3976334"}},"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":"Q1083200$6F70B773-CBAF-4061-B3C5-47737D0E4145","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4d09fd410cd6987eb2b81183bf68b6286718849","datavalue":{"value":{"text":"An analysis of Monte Carlo algorithms for counting problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1083200$642AD190-1E43-4D93-B726-1DEB7B7F90ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b1037095daf5b19b2949e9d16dd04fe8e98ef942","datavalue":{"value":"0604.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083200$31432199-ABD3-4902-8C2E-9C1F77C10411","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a774ff5fef8f8615798540028333a0134f1bed6","datavalue":{"value":"10.1007/BF02575896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083200$5A36A69F-4A7A-48FE-8105-84D3A69ACB0E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$7612E79A-04C0-433C-B7BD-EA8BCC0A9F30","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa0ba58b3114d8fa3b465e5112e7eee5b47291c2","datavalue":{"value":{"entity-type":"item","numeric-id":260128,"id":"Q260128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$66D86393-6BD7-4413-B4CD-176F2ADC4DAF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1083200$AAF736AC-8FF0-4441-9DAC-538DBB36CAEB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8e6acdb908a18ee10efc51e422ef468b715f844","datavalue":{"value":"The efficiency of Monte Carlo approximations for solving {\\#}P-hard counting problems is investigated in this paper. In particular, a necessary condition is derived for a problem to admit of a Monte Carlo algorithm with polynomial time complexity and bounded relative error. Two Monte Carlo procedures are proposed for the approximate solution of the following {\\#}P-complete counting problems: given a finite set E and a collection \\(\\{S_ 1,S_ 2,...,S_ m\\}\\) of subsets of E, compute the cardinality of the union set \\(\\cup^{m}_{i=1}S_ i\\) (Union Cardinality Problem) or the intersection set \\(\\cap^{m}_{i=1}S_ i\\) (Intersection Cardinality Problem). Tight bounds on the worst-case time complexity of both algorithms are explicitly obtained. It is shown that one of the algorithms solves the union cardinality problem in polynomial time, within any specified accuracy level, provided \\(m<4| E|\\), the cardinalities of the sets \\(S_ i\\), \\(i=1,2,...,m\\), are known in advance and it is possible to select a member of \\(S_ i\\) in polynomial time. Observe that these requirements are fulfilled in all relevant applications of the union cardinality problem. Finally, a probabilistic analysis of the proposed algorithm for the intersection cardinality problem is developed, assuming a reasonable stochastic model over the instances of the problem. This allows to show that, under mild assumptions on the stochastic parameters, a substantial reduction in running time can be achieved with probability tending to one when the input size grows asymptotically large.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$B08333F6-BE04-42C6-835E-6156E5CEE559","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083200$3F769384-F2DC-473C-97F7-38301B027FE3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4d107cdaff5fd5034d166853a0b0fec11ed59af3","datavalue":{"value":"3976334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083200$ABD65021-0E6C-4EE9-A663-941B500DCFA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e569e07a49c82ee4107766a600078715f7a3daaf","datavalue":{"value":"probabilistic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$DE300257-E9CB-429B-9D1C-DA0F3CA4C4E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82865b38e19830308ae31a86d7b47ab6cf24a676","datavalue":{"value":"Monte Carlo approximations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$62583AE5-E3DD-409D-AD30-2562636C188D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3fe2b68bbbedac603bd9a43a83277abc407dfc0","datavalue":{"value":"Union Cardinality Problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$1F03E9AB-4D8B-4143-9AF7-BD2F4B39D261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecbd8964df4d61f4ca62a3bf9c64ebdcee2c8e98","datavalue":{"value":"Intersection Cardinality Problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$9278148B-1CB8-43AA-97F0-30E0798FF4FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"466c3284448d1dda53576c5d0dd6ef79f5fe9aaa","datavalue":{"value":"worst-case time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$2426C189-98D6-476A-A24C-C1A3C9ECEEA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$97E1F613-8A24-45A3-9EFC-BF627CBFC5E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083200$51C71D25-54BD-4DBF-970F-0873BBBE1C39","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":"Q1083200$1B9A865B-00FB-4835-9874-2ABA454F8329","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"613d931a22e5ff8d808af0706d38f6066abebcb1","datavalue":{"value":{"entity-type":"item","numeric-id":1151037,"id":"Q1151037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$A4C8A5B7-DD3E-4962-9A0A-C4D58FD58A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$70E739C0-EDA9-4E08-86C7-1D2ACE8C3DDE","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":"Q1083200$DC07CE49-6DD9-48E5-BE79-BB047F58797A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff90b53746deaf40f0bd975035788d645dc76ab","datavalue":{"value":{"entity-type":"item","numeric-id":5682013,"id":"Q5682013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$CA078D02-8708-4C97-B235-3FCDC06037AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2feb08de34ad3aa597fc5008850a73c3a78897ae","datavalue":{"value":{"entity-type":"item","numeric-id":3834934,"id":"Q3834934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$9101F069-90A4-4AED-A7AB-66E8F82AA200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65901429f280a265b22bd5b0ed481bf3db10c53c","datavalue":{"value":{"entity-type":"item","numeric-id":4051876,"id":"Q4051876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$CB986C60-104D-4B03-863C-8CE2CB8347C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3798f797f1d96df74883f771f001f3f714b860f0","datavalue":{"value":{"entity-type":"item","numeric-id":3036719,"id":"Q3036719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$DD6CE13D-CE1A-4EEA-A00E-E92B79EFB6C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b160bdce4c6d61627894b8b9b105fc3b11b9255b","datavalue":{"value":{"entity-type":"item","numeric-id":4740315,"id":"Q4740315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$2C520FBD-430A-45BD-9C7F-4CF10A62131A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$9D835817-C3A0-48AA-B9E1-055CE377FF88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70536879af054717c0f3d9d913a10e93c328980d","datavalue":{"value":{"entity-type":"item","numeric-id":3853129,"id":"Q3853129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$39F387E3-F2DB-4CD1-B26F-0D4F52C7DED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25cd063441f5d22ff5010bddc6b90d037ba9febb","datavalue":{"value":{"entity-type":"item","numeric-id":1836980,"id":"Q1836980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083200$0AA2D249-BA3C-4849-9A11-E40C2EC58FC9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acd1498409e4d623cbfaf8aca81dcba3220b5082","datavalue":{"value":{"entity-type":"item","numeric-id":3723576,"id":"Q3723576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a753ca319abe745c9812cab2bcd9f7735bdb0c2d","datavalue":{"value":{"amount":"+0.98114204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$698539C7-3CA3-4A7D-A0C6-9AB3233CB492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a98aca0155356b1d0698124ec2e1b4045f429425","datavalue":{"value":{"entity-type":"item","numeric-id":3834934,"id":"Q3834934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf99e2af70210a6f748349c1bdad8aadf43d8041","datavalue":{"value":{"amount":"+0.9203707","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$D0193DC3-94D3-459D-9C78-40AFC9791F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"415fa3f5651a42e3e2152b79091a547dc0fdc86e","datavalue":{"value":{"entity-type":"item","numeric-id":2911701,"id":"Q2911701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69928139c67142e55fe0bcc98aab4131012e7e78","datavalue":{"value":{"amount":"+0.919845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$6A282A6A-4268-4D35-AD5D-26A6D78B956E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"877203ba42770d80b858e755c876845eb312310b","datavalue":{"value":{"entity-type":"item","numeric-id":3489457,"id":"Q3489457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a55794a9811e77ff76b1f964a40959be1a6fa2fb","datavalue":{"value":{"amount":"+0.90853566","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$837C3DEF-34B0-4156-BF15-900D8831D416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddfc32274c2b3d55a05bca0e589058fd93716f90","datavalue":{"value":{"entity-type":"item","numeric-id":5085374,"id":"Q5085374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"118c928396a1fe2801a6afdd76bbfde31e9937b3","datavalue":{"value":{"amount":"+0.9055477","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$82E79149-193E-4E42-A458-2584780B8078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9de9026272e6ab14688e76894a91f0489200b0de","datavalue":{"value":{"entity-type":"item","numeric-id":3343437,"id":"Q3343437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de4ac4b2bf3adfeb5e54db17936337eef496cd4b","datavalue":{"value":{"amount":"+0.8913119","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$49D63256-E0B2-41D7-8BC4-451AF9FAFE8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c5032e3bbe0a8231a4821c7a55eeebb44711373","datavalue":{"value":{"entity-type":"item","numeric-id":307930,"id":"Q307930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9387172b162faba99e7d78abe5e24730ef346fa3","datavalue":{"value":{"amount":"+0.8878172","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$526A3EB8-E3F0-49D3-A83F-A1D00D3C724E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a03f7791fe60a1bd4b3e2e5b7809e4f2177e96ac","datavalue":{"value":{"entity-type":"item","numeric-id":4717946,"id":"Q4717946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33b980e636e894a18689888696755993aeb892fb","datavalue":{"value":{"amount":"+0.8844471","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$A1E53B9A-39CF-4E1F-8F52-E2F0E69724FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4a3956cd10ed6ad0a5e63bd290263ad3fc6baee","datavalue":{"value":{"entity-type":"item","numeric-id":1318435,"id":"Q1318435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16ec28675e0f28f28c5fe3fd42543522c4a70f12","datavalue":{"value":{"amount":"+0.8765063","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1083200$039770FB-B87D-497A-934F-03958FD073F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1083200","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1083200"}}}}}