{"entities":{"Q4364508":{"pageid":6394107,"ns":120,"title":"Item:Q4364508","lastrevid":108297944,"modified":"2026-11-05T19:53:48Z","type":"item","id":"Q4364508","labels":{"en":{"language":"en","value":"Looking for an analogue of Rice's theorem in circuit complexity theory"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1088195"}},"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":"Q4364508$BE639B85-DD0F-48A2-89C3-210F7DC014FF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d26bba6a665c127ab61f2bbbfec526d24d642699","datavalue":{"value":"0894.03020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364508$3B387BD2-77DE-4D24-860D-C2F88F62C648","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aa1149445dbfd9f2ca7dd0bddef406ecc8c892dc","datavalue":{"value":{"time":"+1998-08-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4364508$CD77E2B1-9B5B-4680-BC68-5269E2FC43C0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364508$B7F78B6D-47D0-447F-B91D-1C17A6719EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364508$D4C5FFFA-E0E1-4D7C-ADFA-A07CEC62196E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364508$8E401AAE-B1C5-4F04-8BF3-6711C6840213","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c7cb395b3336e5f6304b3cba09f48f508fa8846a","datavalue":{"value":"1088195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364508$893F5005-D5BD-495D-9371-01D11714BF82","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d74016b3171ed5f255980a6a82049735c83eeee","datavalue":{"value":"Rice's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$BB3990AE-3E01-47A6-8D3B-9B0DEA845FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d463b247e815798d799459507ebd3bcfc87bfad","datavalue":{"value":"Boolean circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$0CB896AF-7DA8-430B-9573-507398EED6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$BD3D0604-F725-4D75-984E-3716EAE55A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d3fe981daed39bacbf28035a1f34999938cf409","datavalue":{"value":"absolute counting problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$E9723DAE-1D90-4C3C-8CE6-CFC5548AF241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46d2c510c824babb82cfcb80cd7e60e30fbb21cb","datavalue":{"value":"gap counting problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$0091D33E-9CC6-4F42-828F-3C647E300DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"525131000077a8e88401c3fa811f55f1e7e5e03b","datavalue":{"value":"relative counting problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$5E6B1C05-C693-45C6-8AE8-15E9051A96B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91dd02b59dc9ae2e3e331a3fa5f933b42d47db67","datavalue":{"value":"UP-hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$64BFC65D-C604-4D93-8D34-CE6900AD29D8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5843c7c493d4706c03532f63f307f44c46bc641b","datavalue":{"value":{"entity-type":"item","numeric-id":590547,"id":"Q590547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364508$A5B05898-3906-44BB-BBDF-A759BF1AD95E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a56bc7b07f95b5885e3133c205b9456af5cfa030","datavalue":{"value":{"entity-type":"item","numeric-id":324251,"id":"Q324251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364508$B64EA1FB-79C1-4427-8793-5145ACDC039F","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":"Q4364508$3676B97A-6E0C-42E6-AE66-0017AA5A7825","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ffebd38905d01d7f65c2a04607c13e3b2505b82","datavalue":{"value":{"entity-type":"item","numeric-id":4521124,"id":"Q4521124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0000b07fbfb8cbdf1f57b5ac7d575ee4a8cb0000","datavalue":{"value":{"amount":"+0.9157178997993468","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":"Q4364508$D72DD499-0789-467A-8AB1-884C56B83B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1f94c9be951ddc0fe411362f91d7b38e9a1652d","datavalue":{"value":{"entity-type":"item","numeric-id":4218116,"id":"Q4218116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"791f6191a2cb07c8d389fdc93ba614fce88a39b6","datavalue":{"value":{"amount":"+0.8685813546180725","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":"Q4364508$7F0314FE-3519-4CD9-90F5-1DC6587D8AFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4545fdf82a5c0fca70c2d4ec605f114bf6a85208","datavalue":{"value":{"entity-type":"item","numeric-id":1575716,"id":"Q1575716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17898362344b60fdfea93df3bc204f747afc7b44","datavalue":{"value":{"amount":"+0.8512954711914062","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":"Q4364508$6093D766-3546-4212-9AC4-4C0FB42D3DC3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1048bc2209506f57f2c14c0d1d6eb710a38b1ba3","datavalue":{"value":{"text":"Looking for an analogue of Rice's theorem in circuit complexity theory","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4364508$5D87B1B8-4792-400D-8700-4A75F1CB5681","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e3bae40fbd43d46a916aab2959892218e7e3e6f4","datavalue":{"value":"The paper under review is motivated by the search for an analogue of Rice's theorem in complexity theory. An approach the authors chose is that of Boolean functions. They begin by observing that the following, most `natural', analogue of Rice's theorem is wrong (assuming P \\(\\neq\\) NP): Let \\(A\\) be a nonempty proper subset of the set of all Boolean functions. Then the following problem is NP-hard: Given a circuit \\(c\\), does it compute a function from \\(A\\)? In view of this observation, one has to satisfy oneself with more restrictive and less intuitive Rice-style theorems. Of them, the present note contains several, each of which deals with problems from one of the three categories: the so-called absolute counting problems, gap counting problems, and relative counting problems. The general structure of every Rice-style theorem is this: any nontrivial \\{absolute, gap, relative\\} counting property of Boolean circuits is UP-hard with respect to polynomial time Turing reductions. Some applications to randomized computations are deduced, and open problems discussed. For the entire collection see [Zbl 0870.00023].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364508$DF8FFDE7-D732-4F8B-84A8-647ECF763559","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Looking for an analogue of Rice's theorem in circuit complexity theory","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Looking_for_an_analogue_of_Rice%27s_theorem_in_circuit_complexity_theory"}}}}}