{"entities":{"Q809598":{"pageid":811446,"ns":120,"title":"Item:Q809598","lastrevid":49539310,"modified":"2026-01-07T14:35:26Z","type":"item","id":"Q809598","labels":{"en":{"language":"en","value":"A note on enumerative counting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4213441"}},"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":"Q809598$CCCF0F00-6032-4655-B7CF-3E7CB285CCB3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e3f6a8c243bda6a2655785dca92bfe68b7a3fa0a","datavalue":{"value":{"text":"A note on enumerative counting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809598$E8C71E0F-EB38-4406-AEA4-FC0EB2EE8082","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4bbabd53f9b38513582c8b80e1d4a8359949e3ee","datavalue":{"value":"0733.68030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809598$48C3393B-CF6C-45D5-ACEE-CDC1920CDE76","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0afcef1ad78ad1939a6a0ed29496204ab03a03f1","datavalue":{"value":"10.1016/0020-0190(91)90103-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809598$81D1B47E-EF6E-4AC5-A97D-EFBECD869654","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":"Q809598$7E37EBDE-4865-471C-BDBD-839D19A3B342","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q809598$8645EC05-B285-4D87-A881-EDE7D6C5EB78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0c8c3b55b76ed75d619cc9fc0f682bd2962483d0","datavalue":{"value":"The authors show that {\\#}P cannot be enumeratively approximated unless every {\\#}P-function is computable in polynomial time. An enumerative approximation of a function f is a polynomial time computable function g such that g(x) computes a list of numbers containing f(x) as one of its members. In their proof the authors show how to construct from any given enumerative approximation of {\\#}SAT a polynomial-time algorithm for {\\#}SAT. This algorithm uses manipulations of permanents exploiting the fundamental result of \\textit{L. G. Valiant} [Theor. Comput. Sci. 8, 189-201 (1979; Zbl 0415.68008)] that permanent evaluation is {\\#}P-hard. As the authors remark a different proof of their result has been given independently by \\textit{S. Toda} building upon an approach of \\textit{R. Amir, R. Beigel} and \\textit{W. Gasarch} [Structure in Complexity Theory, IEEE Computer Society Press, 232-243 (1990)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q809598$5321A653-5F75-49A9-8039-1087FCD1F941","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809598$AC431F89-869B-4215-ADA5-F02E46CABDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809598$D29DCBB7-51A0-45DE-AAD3-00C5BD767DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809598$A2B30158-B1B0-438C-AB8D-A9960836D234","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b467a2e11c4feeed8553fc3c4014f0f8bebdc9a5","datavalue":{"value":"4213441","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809598$D5DB02DB-E282-4585-A761-F7DE9768542F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bba624ba9c8730f00c74fd035d6c60071f1c1834","datavalue":{"value":"relations among complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q809598$5074E9EE-803F-40AA-A40A-EDDD3C0DAE9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"153f087410d6445d3ecf9b2f61b070cffa67488f","datavalue":{"value":{"entity-type":"item","numeric-id":269464,"id":"Q269464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$CD013455-E16B-4606-B6D4-9BCE3516B5C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95d207a16ce6533a2e03f4685944467ead41f45c","datavalue":{"value":{"entity-type":"item","numeric-id":161382,"id":"Q161382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$20D22611-66C8-48D3-881C-6EB36442A897","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9c446a25cf0b963435717eedcea7753bd22a49ba","datavalue":{"value":{"entity-type":"item","numeric-id":960465,"id":"Q960465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$D294885D-6F87-467B-92E2-D7F6AD8EBE2E","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":"Q809598$AB88C2EC-0E5D-491F-8B63-FABE4FCD2AA9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"99ab74cdfcab5dc4bad64905b863388aefc5a4ab","datavalue":{"value":{"entity-type":"item","numeric-id":3999199,"id":"Q3999199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$35A2CE81-4CC9-405D-BC70-F669CC508884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8d154393ad0afc2810aee62966ec1a7a0324acf","datavalue":{"value":{"entity-type":"item","numeric-id":1210334,"id":"Q1210334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$6BCFE7ED-41D7-42B4-B1DD-1D7B0091EF4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0f95a774381c0a85c6c478f1cfa3c8eacecfc93","datavalue":{"value":{"entity-type":"item","numeric-id":1178690,"id":"Q1178690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$C569D675-BE70-464F-89F8-D1E9EC877E07","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":"Q809598$8213BD64-7F65-4CC6-889B-FA16E9A1A4E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$67276A79-2AC7-4482-A750-7F255C74B58C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1f6aa5a7dbb8eced91175201c5b61a84466f7ef","datavalue":{"value":{"entity-type":"item","numeric-id":3259107,"id":"Q3259107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$84892CE8-C5DD-4616-91F9-67F293FA4261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4e61defeb465b4f4171017644769b93d87f61e5","datavalue":{"value":{"entity-type":"item","numeric-id":5056087,"id":"Q5056087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$C5E56805-1A91-46FB-9855-2CF07946E157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6b8e182f563da53f2fde28722314c75f4a9c3fe","datavalue":{"value":{"entity-type":"item","numeric-id":3798240,"id":"Q3798240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$1884D37C-862B-40A9-B6A4-8235FB677824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c72aba4f754fb3aee58df56c633c6e4b5ddbcd5","datavalue":{"value":{"entity-type":"item","numeric-id":3718150,"id":"Q3718150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809598$28531AE6-9B1C-4589-B44E-D01D5F3C326E","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":"Q809598$C6BA612E-40DA-4603-8D65-67011836DE42","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":"Q809598$3AD8FC04-2051-425A-A0EC-45934A794656","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d53faa7014ed457c5bc7e245e44ead40f274fd74","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90103-o","type":"string"},"datatype":"url"},"type":"statement","id":"Q809598$9F94E8B5-C84B-4ECD-9B2F-FD9B00A7145D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d6ec206e73aeaaa6d23387a522a669e30c47fe5e","datavalue":{"value":"W1982547542","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809598$A5D665C3-F7E6-4E47-B2F4-D0427209D1E3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a8dda217a2dc80d5954956f7dab0cd935a4eab6","datavalue":{"value":{"entity-type":"item","numeric-id":1822963,"id":"Q1822963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cce95412d835da47d6fb030b8e68307a335eee7","datavalue":{"value":{"amount":"+0.8501554131507874","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":"Q809598$375189E5-26D2-451A-9B00-43186C445A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45bfbd0453cf7b48d9491b4811ec739ec60088f2","datavalue":{"value":{"entity-type":"item","numeric-id":1199550,"id":"Q1199550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd03f350bc195c2e81fbf4b3e235cadd18e3ce43","datavalue":{"value":{"amount":"+0.8370187878608704","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":"Q809598$13FC71D6-787E-49AF-920A-38F942D19909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c54969b9fc2d8cf9f4fd9d08be239ce1990a7b9","datavalue":{"value":{"entity-type":"item","numeric-id":3718150,"id":"Q3718150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3afd34686ac3f4f90e7fb1170d7a354e0b56e92f","datavalue":{"value":{"amount":"+0.8228060603141785","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":"Q809598$DC59F07D-E4D9-4637-A7D8-A12C1051A6C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a25bd6cad9fb2eac922649fbf9d3976dfee8ef69","datavalue":{"value":{"entity-type":"item","numeric-id":3800016,"id":"Q3800016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26554158a0cc01a9fd9a47b6013cc96f3c8933d2","datavalue":{"value":{"amount":"+0.797235906124115","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":"Q809598$6E1188FE-F20C-44F6-97BF-3D764405CC92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"404f42d77497a35434e66b015049beb91f8e54ed","datavalue":{"value":{"entity-type":"item","numeric-id":4352952,"id":"Q4352952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebbc35150e1fe18a0334a7fbf79cb2f816d93293","datavalue":{"value":{"amount":"+0.7717747688293457","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":"Q809598$1D56DFAB-F413-41E4-BA71-E62838651192","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:809598","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:809598"}}}}}