{"entities":{"Q2784467":{"pageid":2795205,"ns":120,"title":"Item:Q2784467","lastrevid":83406176,"modified":"2026-05-07T07:35:32Z","type":"item","id":"Q2784467","labels":{"en":{"language":"en","value":"The global power of additional queries to \\(p\\)-random oracles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1732355"}},"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":"Q2784467$505AB485-BD94-4E35-9250-384F7A1FD3CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c06c073b7e9adde40e3b991a6aa46b35196e072a","datavalue":{"value":"0997.03039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784467$48B102FE-526D-4A19-8DE1-C302F42749D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"427b8cdc52f9e5b6da39f96bcb9c5941ae8d1c53","datavalue":{"value":"10.1137/S0097539700366711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784467$7DAC389B-1492-4BCF-B0E8-1173ED882D84","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8960505e0c34b146023a51f8925a5453d9d2c6ff","datavalue":{"value":{"entity-type":"item","numeric-id":494056,"id":"Q494056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2784467$B9125074-933D-4768-885E-AFE96BD8B014","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2784467$DAE92846-2B0C-49FC-A43B-71E6CC4E7940","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"22e17fffa644ae9f618754e26357d6dbd53b7382","datavalue":{"value":{"time":"+2002-04-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2784467$9C1330AA-34FC-45D5-8835-985CB2B3AA97","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784467$62ADBEC9-D7DD-4EA9-A02B-D8F04FBCBEFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784467$388089A9-4BC6-4262-8E0C-CEED0D2855E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784467$9F243F82-D50C-4221-9C7C-8FDE22FA4A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784467$F8728930-3E12-4509-9F9B-C2DF7E7DB8DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ad8088dc8bfac1a5b5b9eb255163557c3b16630","datavalue":{"value":"1732355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784467$73E4E6FF-098E-4F08-8894-B1A783199E37","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c39dd9430974db3def2db6705a5de4e3845bb9f","datavalue":{"value":"separation of reducibilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$EFF50529-9FB0-4258-AAAC-2FA3C307C4E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6737ee328713c8842d80023445e85704d0ab460e","datavalue":{"value":"random sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$BA7DA2BA-6F88-4965-9224-0A9A10FDE504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e36a27fa50ab0f45b19af9d143ff241b475352cb","datavalue":{"value":"effective measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$73ED089A-7A98-49C2-BDAC-5C0987C48D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a1adf3a4a1f6be0a2225196f1fd281a320ac58e","datavalue":{"value":"resource-bounded reducibilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$1885D246-75CE-435F-80CA-4FFA92B71169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"766692d6f990cd49df1d5a0f65e16847327b751b","datavalue":{"value":"effective reducibilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$07FA9C24-09D3-43DF-A4D7-3D0EDB28C2CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eda9f60512d8e02150a46e43e911af2e47469421","datavalue":{"value":"bounded truth-table reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$FA767A3F-CDAA-422A-A598-411B4D1885A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d243e060be5f8c397fa8b96e683ca1b64d47b073","datavalue":{"value":"random oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$900B2BA9-A112-4A1E-B93F-01D24BFC84BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8745712302d28813999fe70c270cd7743c07054b","datavalue":{"value":"query complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$9CE951B1-72A1-42EC-B8A3-1D1C213E6512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd1198d2714f52c951218a18774d5fe7265b2db8","datavalue":{"value":"resource bounded measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$61548AF0-AF90-48F9-98AC-09530311AF26","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":"Q2784467$4EADDC90-91D8-4C14-AEF7-5A2E6E569186","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a2e626885e819e59e10bba21d24adfa4a5343581","datavalue":{"value":{"text":"The global power of additional queries to \\(p\\)-random oracles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2784467$F3DD8F9A-BD24-4114-9D7A-9D7EDAA4D47F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dcc9645f5b7a9cb17354fb5e576b4eb14adadc92","datavalue":{"value":"In this paper several separations of reducibilities with respect to random sets are considered. For polynomial-time reducibilities that query oracle nonadaptively it is shown that for any \\(p\\)-random set \\(R\\), there is a set that is polynomial-time-bounded reducible with \\(k+1\\) queries, but is not reducible to any other \\(p\\)-random set with at most \\(k\\) queries. This result solves a question left open by a recent paper of Lutz and Mayordomo. Further, it is shown that the separation above can be transferred from the setting of polynomial-time bounds to a setting of recursively random sets and recursive reducibilities. This extends a main result of \\textit{R. V. Book}, \\textit{J. H. Lutz} and \\textit{D. M. Martin jun.} [Inf. Comput. 120, 49-54 (1995; Zbl 0835.68044)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784467$E4C21DEF-EAE3-4FF1-982E-883FD3BC0374","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5952d5747f1b757477be9b9c686a7adfc3c316e5","datavalue":{"value":{"entity-type":"item","numeric-id":2754207,"id":"Q2754207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae40972341099a53706f2dad9cd80237575d6ac2","datavalue":{"value":{"amount":"+0.9821037650108336","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":"Q2784467$571F7042-C3CD-48F6-8BCC-BE6B4C42B76E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f6d3dad519d0fc06ca7f84af678f0e27e4c5ed1","datavalue":{"value":{"entity-type":"item","numeric-id":1898477,"id":"Q1898477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb18c450366f152773a74552a37d36dd9c4ae4bf","datavalue":{"value":{"amount":"+0.8941310048103333","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":"Q2784467$8D4056B9-8A4C-4140-AEEC-475DD586CF33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b04c8d4afd4c38c6d9bf4a123a943c2ec2cd3ae","datavalue":{"value":{"entity-type":"item","numeric-id":3569010,"id":"Q3569010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb49cc09411cd2d6b6b187e06a179334d9ac2ad2","datavalue":{"value":{"amount":"+0.8936133980751038","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":"Q2784467$7E3C85D6-726D-4C9E-A9B5-1414BBD43448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfc676e7114b4b728bbf7cd0a998d80f659456a0","datavalue":{"value":{"entity-type":"item","numeric-id":4942646,"id":"Q4942646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eb4795a5a1fcebcf858d639ef32ec9391f01090","datavalue":{"value":{"amount":"+0.8920711874961853","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":"Q2784467$497CB8E0-D2DA-4B13-9EEF-98540C4A26BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32bd33f783031afec8ad8db759272ed24d51cb83","datavalue":{"value":{"entity-type":"item","numeric-id":1332664,"id":"Q1332664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e97286ac7dd6ea054b949225c3e6b6186f080d4a","datavalue":{"value":{"amount":"+0.8915261030197144","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":"Q2784467$CCBD7B73-66F1-4828-9E89-EFF77AF25D7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The global power of additional queries to \\(p\\)-random oracles","badges":[]}}}}}