{"entities":{"Q7361566":{"pageid":31520237,"ns":120,"title":"Item:Q7361566","lastrevid":105368789,"modified":"2026-10-07T13:37:37Z","type":"item","id":"Q7361566","labels":{"en":{"language":"en","value":"Approximate Model Counting"}},"descriptions":{"en":{"language":"en","value":"AFP entry Approximate_Model_Counting"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"38786fddf7ed391a03e2ac146f84cd7f38c7ccfa","datavalue":{"value":"https://isa-afp.org/entries/Approximate_Model_Counting.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361566$9CCFE1BF-7288-4101-B63E-94317916DBAE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8123d5f1d57e30741d7d1b2e895b585ec3555e54","datavalue":{"value":{"time":"+2024-03-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361566$E0F623E1-4918-4E06-BD1B-380D042FF751","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"d9ef184945389dfe82f21c38f697f4e88ed3433f","datavalue":{"value":"Yong Kiam Tan","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361566$265C8EBD-D854-4009-BE87-5A95FD8F6E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"438bd279a1daa65a6d3c4c4298905cdd450555b2","datavalue":{"value":"Jiong Yang","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361566$EC24345B-CF63-4F47-B89B-D971917A46C7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a147570aa9256a93f8eae6d8b2fd335d0c544801","datavalue":{"value":{"text":"Approximate Model Counting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361566$62838A68-A476-4157-85DC-D2EECA68B345","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef43289f2815ee09b8c643aa07a74f6ddd6f854e","datavalue":{"value":"Approximate model counting is the task of approximating the number of solutions to an input formula. This entry formalizes $\\mathsf{ApproxMC}$, an algorithm due to Chakraborty et al. with a probably approximately correct (PAC) guarantee, i.e., $\\mathsf{ApproxMC}$ returns a multiplicative $(1+\\varepsilon)$-factor approximation of the model count with probability at least $1 - \\delta$, where $\\varepsilon > 0$ and $0 < \\delta \\leq 1$. The algorithmic specification is further refined to a verified certificate checker that can be used to validate the results of untrusted $\\mathsf{ApproxMC}$ implementations (assuming access to trusted randomness).","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361566$BE4D2B3C-8A13-42B3-9622-1B38A775FFAD","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361566$AA8EFF14-ED71-42ED-B194-B15D4A09129B","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"5a311f14e314261f712ad9620747a382d76a3b30","datavalue":{"value":{"entity-type":"item","numeric-id":7361435,"id":"Q7361435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361566$0A26776D-A757-464A-A2EE-55C9AA8C9B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e7518fbf10f198bc3df0e1d32caf24e0792bb693","datavalue":{"value":{"entity-type":"item","numeric-id":7361920,"id":"Q7361920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361566$29388B3D-42BB-48A3-8011-5C022131A444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"ceeec1476c044e883da5dc800851f022e7ceae8f","datavalue":{"value":{"entity-type":"item","numeric-id":7361442,"id":"Q7361442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361566$2A9B3950-94B8-4DAF-9A97-511ED4EEE2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"568df032e4fa5e393d3cafa654f178d211e1f6f1","datavalue":{"value":{"entity-type":"item","numeric-id":7361689,"id":"Q7361689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361566$A32131B5-5622-49B7-A1C6-D9AD398E70E6","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"1213e4bf209f93a0bd2b72ccadf03a45aea2311a","datavalue":{"value":{"entity-type":"item","numeric-id":7360773,"id":"Q7360773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361566$8DCC7B6D-A04A-4F49-82BB-654B8E478A52","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361566$B2CE2507-B832-4222-A7B8-35E73D68EC13","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximate Model Counting","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximate_Model_Counting"}}}}}