{"entities":{"Q5905584":{"pageid":8017736,"ns":120,"title":"Item:Q5905584","lastrevid":47111521,"modified":"2025-12-31T17:24:01Z","type":"item","id":"Q5905584","labels":{"en":{"language":"en","value":"Counting classes: Thresholds, parity, mods, and fewness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 94450"}},"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":"Q5905584$46A165CF-A588-4E60-9A4C-A785BE002A1A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"caa11c2cd5829d32c56dcd48ba5360a7ea3ff53f","datavalue":{"value":{"text":"Counting classes: Thresholds, parity, mods, and fewness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5905584$200E615B-B47B-4358-B64F-28ED98A1A45B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d959468f049dda82e0b58d24b5c290ddd83264c3","datavalue":{"value":"0760.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5905584$D3DEDA4B-A5DE-43A5-A068-03180E79DE47","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"34779df88e76731b201a5bdb430293167e946b16","datavalue":{"value":"10.1016/0304-3975(92)90084-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5905584$0BD8E5B3-2568-47B8-B1D7-E721068AF456","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0353358515be2d1b5877a1b267862980a7b952cd","datavalue":{"value":{"entity-type":"item","numeric-id":294935,"id":"Q294935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$5903BF18-45FB-4FAE-A0A2-891D221A9593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96872b92637750aeae6a2ab2dcccacffb220b6f1","datavalue":{"value":{"entity-type":"item","numeric-id":1199523,"id":"Q1199523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$279DE896-F60B-4B86-81DD-8256628B06ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$D62AA6E8-5E9B-4CA5-BF2B-71DFCEECC9BF","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":"Q5905584$8B8992F1-C14F-4566-8364-C3EB0EC54F44","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02b67662a3edd0f666ae1abe4f1ff4741e9c3447","datavalue":{"value":"Counting classes consist of languages defined in terms of the number of accepting computations of nondeterministic polynomial-time Turing machines. Well known examples of counting classes are NP, co-NP, PARITYP, and PP. Every counting class is a subset of \\(P^{\\# P[1]}\\), the class of languages computable in polynomial time using a single call to an oracle capable of determining the number of accepting paths of an NP machine.   The paper uses polynomials to obtain closure properties of \\(\\#P\\). Although some of the closure properties have been reported as folklore, especially in the circuits community, this paper presents the first systematic development of the technique, which has increased in popularity among complexity theorists studying counting classes and circuits.   Using closure properties of \\(\\#P\\), the paper develops a complexity theory for counting classes defined in terms of thresholds and moduli. One unexpected result is that \\(\\text{MOD}_{k^ i}P=\\text{MOD}_ kP\\) for prime \\(k\\). The paper also improves a result of \\textit{J. Cai} and \\textit{L. Hemachandra} [Math. Syst. Theory 23, 95-106 (1990; Zbl 0718.68038)] by showing that recognizing languages in the class Few is as easy as distinguishing uniquely satisfiable formulas from unsatisfiable formulas (or detecting unique solutions, \u00e1 la \\textit{L. Valiant} and \\textit{V. Vazirani} [Theor. Comp. Sci. 47, 85-95 (1986; Zbl 0621.68030)]).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$530E0D12-BE16-42EA-83B0-6AC2F08A402E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5905584$AD8B49CF-92EC-4382-8FB4-978E9EB39AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5905584$EA54F348-7196-472A-AAF1-A12FB5F02245","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"392ccc87511f41495f4310734e902eb16a929107","datavalue":{"value":"94450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5905584$F38C56F1-6527-4231-A5FA-6246ED02C6F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d435b6f8fa5aefb69319ed8da57a094f7d5a961","datavalue":{"value":"counting classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$4053938D-59A2-4ECD-BED2-05AF935A452B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9d4de01492ec095e06abf18647cf41f4a5c30a2","datavalue":{"value":"MOD\\(_ k P\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$2A185545-C1EC-49F5-8097-0EB007D53C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c14a443ba3b0ef24ac7d242cbbf1be108e7ec15","datavalue":{"value":"PARITYP","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$5E3A541B-B98D-4BC5-9286-BBBE8802164B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfc931c3a91f89215c7796518c4c47215a8741a0","datavalue":{"value":"PP","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$6DB8ADD2-1124-4278-BC41-128946E9065E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$5DCB26C7-8EE3-49FC-9169-754D7C5E6480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7a609ae2c21271342f267522dda74375687f014","datavalue":{"value":"polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$D4F287EF-74B0-49D9-935A-7BAF0A308318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca9721c8563dc80cdd51a074bf5c60efcd1763dc","datavalue":{"value":"\\(\\#P\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$E614E088-68EC-4549-B8C4-55DE80BBC052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74f4a6a41ab3cfce2d3866e6057e8a81c24886a7","datavalue":{"value":"Few","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$B65579F9-D4DC-4B92-9940-9F34DB160054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"459ac88544a7f524b565029b8a635538c8e2fe66","datavalue":{"value":"unique solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5905584$C455DDB7-7931-4886-ACBB-498EE5B9DB08","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":"Q5905584$BDA4D2F7-D91A-4ABA-A6E2-9115C6A029B5","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":"Q5905584$08F0ED96-170D-4D83-A85C-F2DBA532117D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6960b7484ca2e6b4844b3be0318c5da14436ba3d","datavalue":{"value":{"entity-type":"item","numeric-id":4036704,"id":"Q4036704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$5CE45F2D-A141-4FFA-83BC-952974B5AEA1","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":"Q5905584$B7F6091D-6A9D-422A-BCFF-4DF7E8F8B44F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c317ee9b89d25866849eff84487be5a7c7991b60","datavalue":{"value":{"entity-type":"item","numeric-id":3331209,"id":"Q3331209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$FF2030EF-7FC0-40C4-B337-582CFA712762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"486673ceaea3791821750647cd986822d2610503","datavalue":{"value":{"entity-type":"item","numeric-id":5750401,"id":"Q5750401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$10C341C1-6779-4EB8-8954-58D32FC0C82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$AA95B6A4-F6A2-4C70-948A-C2D222380B28","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":"Q5905584$60E460FE-2FC5-4802-A0F5-37961E760D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6690941b790d3f730c7ae6b7e325ad8391f2459","datavalue":{"value":{"entity-type":"item","numeric-id":1083204,"id":"Q1083204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$B1B55B36-297A-4E34-ACD7-EB0EE9501CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e332fcceb97a94c6d147f0d469ea0a5372e4364","datavalue":{"value":{"entity-type":"item","numeric-id":914370,"id":"Q914370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$657E16B0-4DBC-4EA9-8767-F08A258E7641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$49FDB79E-8067-4CD5-A3A5-B676A20E8D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$B09DD73E-3E16-4FA1-BA42-2E165D1FDBEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade66df427687f4ec50eb2cfe400c9165af764e9","datavalue":{"value":{"entity-type":"item","numeric-id":3935473,"id":"Q3935473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$1EE539DB-B9F7-49FF-AEC5-E2273720256A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$5E2A2ADC-DFDB-4390-BA45-1E4A9F915D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"044944b72ba88d5432d12a088837654c36df1c9f","datavalue":{"value":{"entity-type":"item","numeric-id":3210177,"id":"Q3210177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$41E4C764-CA25-492F-BC1A-01E93B75E319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a79d7e6ff87438522166be3a4baa3c6ce145a139","datavalue":{"value":{"entity-type":"item","numeric-id":4302854,"id":"Q4302854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$DC22302D-E436-442D-B51A-8866DB0D4D56","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":"Q5905584$AD12CE9F-0E3A-4C0D-AE01-8B0029884ABE","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":"Q5905584$6112BE02-F015-4D27-B580-3158EA197582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5905584$DDA7DEB8-081D-4FF9-BEB3-F4DA45CDBAA5","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":"Q5905584$CA087F97-6555-4651-B7BA-E15D7B21248B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"76659485b1e52ee589dfc2bd592d5b5805afa424","datavalue":{"value":"https://doi.org/10.1016/0304-3975(92)90084-s","type":"string"},"datatype":"url"},"type":"statement","id":"Q5905584$5E8C3A02-F8B4-435A-AAE6-BAAD4E772995","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"563f9cd3061b5ea4ac3b8caa952a834a144ceb00","datavalue":{"value":"W1736584826","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5905584$8ADBF249-DCF7-4955-A3DE-857610CAD525","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db4a30c2739a0b26d2b5fd766fc4332be5436ce1","datavalue":{"value":{"entity-type":"item","numeric-id":5896571,"id":"Q5896571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33d0bd684fe5d7a8d8840f9922a94cc874dfa79b","datavalue":{"value":{"amount":"+0.9610307812690736","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":"Q5905584$74AEAF8F-C710-4F9B-A2D0-0FEC2AB32E94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94380e8fb539b78e1d43e893fb36b268c37b3ee7","datavalue":{"value":{"entity-type":"item","numeric-id":3990656,"id":"Q3990656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1afc4fb9474ab9915ba91ecdc0728bce71fae76","datavalue":{"value":{"amount":"+0.822368323802948","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":"Q5905584$13F90319-4424-4833-9B4E-626738FEA532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c1649192456cac16910e4ce1e137d2518765cec","datavalue":{"value":{"entity-type":"item","numeric-id":5750401,"id":"Q5750401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c4cdd14033b9ab51de7d1858acd38d783d4cb49","datavalue":{"value":{"amount":"+0.8195896148681641","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":"Q5905584$BD675C5C-476E-4516-9C8B-13635A63C884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d4e23733f89d6910b515d60ae68355205ddac74","datavalue":{"value":{"entity-type":"item","numeric-id":1318473,"id":"Q1318473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b94c2afc51bde652ea7a65cd66b671ee9ed683d","datavalue":{"value":{"amount":"+0.8179237246513367","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":"Q5905584$3F4049B9-47EB-4DC4-970B-F13D53A5C5E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3f4631f012691afef050111257adef901a5427d","datavalue":{"value":{"entity-type":"item","numeric-id":2638771,"id":"Q2638771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af121a576ce19045592e448c074f66807f4c706f","datavalue":{"value":{"amount":"+0.8174217939376831","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":"Q5905584$1DE61D48-6A70-4C30-AB61-66E83DEE8C5A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5905584","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5905584"}}}}}