{"entities":{"Q1199550":{"pageid":1210299,"ns":120,"title":"Item:Q1199550","lastrevid":66465117,"modified":"2026-04-12T10:15:40Z","type":"item","id":"Q1199550","labels":{"en":{"language":"en","value":"On the power of enumerative counting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 94470"}},"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":"Q1199550$2A93AAFF-F5C3-43FE-AC90-4BC0DA6F7B7D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"725ce32127837cefab49ecb8b3d92228e67f0a88","datavalue":{"value":{"text":"On the power of enumerative counting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1199550$FB8BF4DB-C151-4A3C-AE35-427A6ECF2E5B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ee3f0d0dba5f1d582e474beeff287a3e518ab8ea","datavalue":{"value":"0754.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199550$A6D57CCA-DBC1-477C-A566-509B1DC546FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d36e5fc7ef6ee35c21a0b486da531cb22b534280","datavalue":{"value":"10.1016/0020-0190(92)90002-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199550$E21E3899-B16F-4F2D-AC7D-63483F81C330","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b19dcdfa93d1790d31a6afcd38ce9d50a059ecda","datavalue":{"value":{"entity-type":"item","numeric-id":686140,"id":"Q686140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$68FC328F-8AE5-49E9-A876-B34A368C4ABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c05b40e09f364094e4e58ba81f893c33ea19726","datavalue":{"value":{"entity-type":"item","numeric-id":441307,"id":"Q441307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$E681EE9F-D227-49FE-890C-131BF05D8E04","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$17F75685-6A96-44AC-BA50-3D9E79645D46","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1199550$7FB8DDB6-988C-4881-93A6-97E08296864D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"90cf9cd10bbd9a56638ffe33e9755a39bc236eb9","datavalue":{"value":"We study the functions in \\(\\#P\\), which have polynomial time enumerators. We show that functions in \\(\\#P\\), which have polynomial time enumerators are low for the counting class \\(PP\\). As a corollary, it follows that functions hard for \\(\\#P\\) under polynomial time reductions do not have enumerators unless the counting hierarchy collapses in \\(PP\\). We also construct relativisations in which for any polynomial \\(p(n)\\), there are functions in \\(\\#P\\), which have enumerators with output size \\(p(n)+1\\), but not enumerators with output size \\(p(n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199550$0B3A757D-6AAC-4167-915E-98C8FD554493","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199550$823F3586-2682-4ECD-A43F-4939304421B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34179179a8473da2d38b22cb867b1186a8fec2ab","datavalue":{"value":"94470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199550$7514CEDC-8C91-4160-B287-CB9E3F541AC6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d435b6f8fa5aefb69319ed8da57a094f7d5a961","datavalue":{"value":"counting classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199550$DFBF85CB-3810-45F1-9639-50580F3DA5EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47f2e8a1773817153b4680713f0a57a6ffae636d","datavalue":{"value":"enumerators","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199550$AFD5729B-FB64-47E3-A96E-89049649EAD1","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":"Q1199550$1AE8C26D-A8D7-43D6-BCC3-46FA0B4BCD94","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"560bf61b4d356df20b0e62b14b1ce453301159dc","datavalue":{"value":{"entity-type":"item","numeric-id":3747725,"id":"Q3747725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$9080900E-7D37-4B7B-BB72-4F92DC4435C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f2e67cd825384f75f58cadbdfbdbecdf2cf1178","datavalue":{"value":{"entity-type":"item","numeric-id":2638771,"id":"Q2638771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$4C13AF9C-C2B8-49A9-A7F5-E0AD5ACADB0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74331aa2934cdd9e8c484261246c0bdd0397b260","datavalue":{"value":{"entity-type":"item","numeric-id":1822963,"id":"Q1822963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$7EBE082E-CBC8-4577-9315-10CA267B1CE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51e8ca4fe98e898ca79eea259b27eebc5567af3b","datavalue":{"value":{"entity-type":"item","numeric-id":5096157,"id":"Q5096157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$98289300-D40B-45A1-A52A-C88F7EFD4959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d655e053e7c2a627e1e06beda58d9e6c0a1eaf43","datavalue":{"value":{"entity-type":"item","numeric-id":809598,"id":"Q809598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$6B6D0223-DA38-4B8C-9078-8C9B46E65D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a830cafef1f2c438cb7e2286bda476de992419e","datavalue":{"value":{"entity-type":"item","numeric-id":1052097,"id":"Q1052097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$66A9371C-E56D-44E1-80D0-0A3CD0E931EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$49784497-7E06-47F8-A153-2E7C4557D6DD","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":"Q1199550$ECADD03F-0009-47EE-BF96-347B96D15B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e1c59b20b978e8e0de5a32fdeb6c212dbd6e1a","datavalue":{"value":{"entity-type":"item","numeric-id":1090455,"id":"Q1090455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199550$C147F6F1-6E97-45E1-94D0-845DAC93DA7B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"af199fea2f1e15efaecab6c47b1c945987b2e83c","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90002-d","type":"string"},"datatype":"url"},"type":"statement","id":"Q1199550$E4A096B0-AB74-4FB9-BE20-21C03E54A39F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0766703321a75a585cf3ec9ef70b51a4e880ffc8","datavalue":{"value":"W2069237346","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199550$D860FDA3-3544-4974-A838-D85EC07AC50E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62267cc504c4f0be602515d1d6ae79b5d6a84ffa","datavalue":{"value":{"entity-type":"item","numeric-id":672336,"id":"Q672336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"839631972497da5753aac44406032c1a95be29dd","datavalue":{"value":{"amount":"+0.9248969","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":"Q1199550$7B3F45D0-4048-4627-BC2F-F1A9D1C109F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8abbe0fc890cd73a4587e461a6e8fdcad3584f1c","datavalue":{"value":{"entity-type":"item","numeric-id":809598,"id":"Q809598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8aabe541e395d1a3c23abd4fab23bb57f6bcb698","datavalue":{"value":{"amount":"+0.9239023","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":"Q1199550$9433884E-0A16-4AC4-9365-D82828FDEF92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3c2c14f4e8da08f4d7e27605009054d7215af68","datavalue":{"value":{"entity-type":"item","numeric-id":3798240,"id":"Q3798240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe262fd9e99af846bb2a35d9456d1e73f0b68cc5","datavalue":{"value":{"amount":"+0.90483725","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":"Q1199550$6D512539-3095-4A1E-A727-168D73B188E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff5be2825e9caa9e513730eab3b80fcf6e9375a4","datavalue":{"value":{"entity-type":"item","numeric-id":5585416,"id":"Q5585416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdee7b80de80a7f136dc59267b56523930860e3f","datavalue":{"value":{"amount":"+0.8899364","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":"Q1199550$127D4197-6832-41E0-8DFC-0394EA37A68E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d32fd5cf91dacafa10c0d11cd34aba7fcc239678","datavalue":{"value":{"entity-type":"item","numeric-id":2776272,"id":"Q2776272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03968ee4c64c89127d63d3ce8c9ef5e1d2031c22","datavalue":{"value":{"amount":"+0.8889408","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":"Q1199550$948F1FE1-7407-4E72-9E59-34CE7C7FBD78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6501bc7e1ff1a5474109c484afb0fdc80f341000","datavalue":{"value":{"entity-type":"item","numeric-id":1824618,"id":"Q1824618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7412b860152433bee59c49069a5573fcc9d6b080","datavalue":{"value":{"amount":"+0.88782513","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":"Q1199550$8FCED6E8-7EC7-4181-9EA2-CFDCE7C484B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16bd7900dfaba5f46096d2595ede285e11bc2106","datavalue":{"value":{"entity-type":"item","numeric-id":3539937,"id":"Q3539937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4074dd45bd083510e91e22b06eb7131e70dcf802","datavalue":{"value":{"amount":"+0.88610864","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":"Q1199550$00623965-3725-4DF1-96C6-D6C7BD7825B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"338f318897d3507dbf365d33fa3e6fa9ab32e26d","datavalue":{"value":{"entity-type":"item","numeric-id":3804682,"id":"Q3804682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5b74b0c95082347da30173305758dc99813219b","datavalue":{"value":{"amount":"+0.88550305","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":"Q1199550$5ABDC598-80AD-45C0-A9B1-25D45135F954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e93670eb8a61e3e2ddc84856e16255d74a292022","datavalue":{"value":{"entity-type":"item","numeric-id":2941987,"id":"Q2941987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96050a4db29eb39507c9a83f0d016a96077e6aed","datavalue":{"value":{"amount":"+0.8852128","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":"Q1199550$FCADFBA3-0FAE-4DBA-A196-85B23877770C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the power of enumerative counting","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_power_of_enumerative_counting"}}}}}