{"entities":{"Q685530":{"pageid":687379,"ns":120,"title":"Item:Q685530","lastrevid":78189578,"modified":"2026-05-06T11:00:03Z","type":"item","id":"Q685530","labels":{"en":{"language":"en","value":"On random reductions from sparse sets to tally sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417425"}},"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":"Q685530$0FA37C63-6F18-4C29-80E9-DDC8171D8693","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"653b1fd5a0c324730ab914abab5e5d98f7373c78","datavalue":{"value":{"text":"On random reductions from sparse sets to tally sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685530$24E638A7-7639-4B88-A656-F1CE76D4433A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5ec8e2028255ad67f38440032cb0318d3c8263d3","datavalue":{"value":"0780.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685530$E2EE028B-3130-4F73-A9B0-967F439709EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f4a7f0b4905c4d087904cf115ad3ba8178f7326","datavalue":{"value":"10.1016/0020-0190(93)90102-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685530$88D7A900-D854-4F59-ABB1-C85B412284B1","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":"Q685530$FA596A59-A4D3-4980-861E-428FFBD24C5D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a779a16cedab8ed14a1943c9aa1cc98db7962383","datavalue":{"value":{"time":"+1994-01-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685530$9AAD1DA2-8C51-499A-8F6E-5DAC49F44DA0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ac92d243e43cc8be4d7b04876419b6c2c034d7b","datavalue":{"value":"A set \\(S\\subseteq\\{0,1\\}^*\\) is called \\textit{sparse} if for each natural \\(n\\) it contains only a polynomial number of words of length \\(n\\). A set \\(T\\subseteq \\{1\\}^*\\) is called tally. It is shown that every sparse set \\(S\\) can be many-one reduced to an appropriate tally set \\(T\\) by a polynomial-time, randomized reduction. The proof is based on the Chinese remainder theorem. As a consequence of the main result it is proven that there exists a tally set in NP which is complete for all sparse sets in NP under polynomial randomized many-one reduction. This is a partial answer to an open problem posed by Hartmanis and Yesha in 1984.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685530$BAB99E0F-CCDE-4379-9FF6-EE81836A9083","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685530$8A82494D-49DE-4066-8FFA-9F70AA6E5A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685530$6FA55159-1935-439F-8C55-96285E53DFFA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a758fe05e863b63f2960856c7f80de437e307d73","datavalue":{"value":"417425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685530$E33C637E-5A65-4B79-9304-DB5FE3876235","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a383bdc9614437ee8b40fc8dc74a3f5c1000f31","datavalue":{"value":"random reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q685530$C082C439-2A18-4E79-9BC5-78E15AC192F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6816fdf79dd11ac09d9af4886c02baab03d2cf9","datavalue":{"value":"completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q685530$12061873-EFCC-483A-85E8-AEE9FA90BF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad43bcd34d069e6f3c71d7afa37e29d215fd1b15","datavalue":{"value":"sparse set","type":"string"},"datatype":"string"},"type":"statement","id":"Q685530$DF106CB4-1C7A-45F2-B0A8-25707B37C4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82ca389cb65564e0a01034b7aa3be9a2b610d2bb","datavalue":{"value":"tally set","type":"string"},"datatype":"string"},"type":"statement","id":"Q685530$8AD42315-C1B7-43C4-84F1-038CF7844D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q685530$3E2F9BC8-C3D3-422B-92F0-A387216BBA2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b03b9482d9fb5a4dccce7e9ae84fc4c0475ab15e","datavalue":{"value":"many-one reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q685530$D1492562-177A-4723-983F-C6AC143FEA56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98e020d336f4040f2344877fb27890751f480383","datavalue":{"value":{"entity-type":"item","numeric-id":1052096,"id":"Q1052096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$E4176C04-CE6D-4190-A89B-C48D529FD235","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"74c919ac6d2ca8ad533fb5c3eb7749c0cb730cee","datavalue":{"value":{"entity-type":"item","numeric-id":1900544,"id":"Q1900544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$ADF7F772-F9D4-41B2-BDA3-DAF5454CEC35","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":"Q685530$0EB1F68C-3D81-4551-9669-6C60EC8FAFE9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb09716bd57a1011f7c259b1047b4d21b39a969d","datavalue":{"value":{"entity-type":"item","numeric-id":4775472,"id":"Q4775472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$7F0944FD-ED7D-42D7-A325-3FCBE9736F53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2f13f8f06c19efc2d4786659ba8a959d6195810","datavalue":{"value":{"entity-type":"item","numeric-id":4852619,"id":"Q4852619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$D18D999D-B662-4602-B5A3-920F093DE472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27ae048a51566b9b30aabd668fe3c01dba8252d3","datavalue":{"value":{"entity-type":"item","numeric-id":1172386,"id":"Q1172386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$F525EEFB-F273-4C5B-A0B2-A328A3A5325A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c25925be7f5c292edb63efdcdcacb15993e69254","datavalue":{"value":{"entity-type":"item","numeric-id":1348523,"id":"Q1348523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$ABE688B2-85C1-47D2-87C1-2B9118FF478E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fb6c7b2f280ac9a7da3ecdd02cf2bac61b13632","datavalue":{"value":{"entity-type":"item","numeric-id":5580392,"id":"Q5580392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$E4972D7E-6FC3-4A3B-9F52-80EFFEC6E810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f31839dd39b2a317795aa66fa2746618a4423fa","datavalue":{"value":{"entity-type":"item","numeric-id":593778,"id":"Q593778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685530$469B6601-C1D7-40EC-8C01-6BB7DC9BDB5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1353a09a4503584f368256dfeda9f71d35170a2a","datavalue":{"value":{"entity-type":"item","numeric-id":4852619,"id":"Q4852619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fe0fa758d869d0c0d8ff5a6515f9f46d18832a9","datavalue":{"value":{"amount":"+0.8482509255409241","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":"Q685530$9FAFFB54-260E-4C81-B6D0-C136F11963FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ce60a7b12a52d81f977c6807db10402fac1fae8","datavalue":{"value":{"entity-type":"item","numeric-id":4256649,"id":"Q4256649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f784f52aa22a2012a3c8d7014ac587dbf51d351","datavalue":{"value":{"amount":"+0.8460943698883057","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":"Q685530$BDBCF59E-A2C3-490B-9D02-1061F76B7C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dd6ffb2a1cec2a4f3250ada4c9795a13d1aa594","datavalue":{"value":{"entity-type":"item","numeric-id":4853331,"id":"Q4853331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"160c0dd4b4f6b90021598b5a9217dee5070c18d0","datavalue":{"value":{"amount":"+0.8435074090957642","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":"Q685530$92370461-9E11-4138-85B5-8EE8A00510A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f7a1e358b7069c37997c7f078cf1a4e3847019a","datavalue":{"value":{"entity-type":"item","numeric-id":3809788,"id":"Q3809788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc557f39884a8a15b02813125db6cf234182cc55","datavalue":{"value":{"amount":"+0.840073823928833","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":"Q685530$539554EB-0043-4769-A1A3-67346B6185FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5e47ad9b1c4b268ecf6d907bf96f5585038df15","datavalue":{"value":{"entity-type":"item","numeric-id":4593941,"id":"Q4593941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f057bba459d92ca3feb165347d7db4a3528eebcb","datavalue":{"value":{"amount":"+0.8293063044548035","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":"Q685530$77F01183-B8DA-4DA1-A735-24A7FE024338","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On random reductions from sparse sets to tally sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_random_reductions_from_sparse_sets_to_tally_sets"}}}}}