{"entities":{"Q2720330":{"pageid":2731069,"ns":120,"title":"Item:Q2720330","lastrevid":41927373,"modified":"2025-05-16T08:49:08Z","type":"item","id":"Q2720330","labels":{"en":{"language":"en","value":"Separations by random oracles and ``almost'' classes for generalized reducibilities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1610976"}},"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":"Q2720330$88382EC1-2F8D-426B-BCD0-ACD36D65ED24","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d06e9be26b549292be2aa739bcdc87f5309d2ea","datavalue":{"value":"0999.03036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$3EDE1011-37B6-475E-84BA-8B0464A74B47","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":"Q2720330$F37527A3-BE9D-404E-8669-731E386A097F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"54e88f2385d222d42a8b9ae8b6d3032f30d1b2e4","datavalue":{"value":{"entity-type":"item","numeric-id":181992,"id":"Q181992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2720330$017D122C-E5F9-48CE-B1E0-7E17755AF42D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ecfb7a4bc3532872a5df039a2c083f1e58c22460","datavalue":{"value":{"time":"+2002-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2720330$93968EB7-3F6A-48A2-8BAC-04B87EEECAD4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$8EBA026F-93F6-4F37-89B5-042A6491EB1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$D1D231F5-5F29-4401-9BD6-ECE1D8922CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bacc42d4ab28169bcab125a394e2c486e425337a","datavalue":{"value":"03D75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$7DFB4520-D922-48AD-982C-A319F9227D6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$55D10F44-9748-4B54-83C9-4357F07556CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$A79973AD-2AEF-41DC-8974-7DC76E53AAE8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"986be01980a96bc8eab215f0a706e4709168ef43","datavalue":{"value":"1610976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$977515A9-A867-48A3-BCE4-C4E4A349FB5A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a1adf3a4a1f6be0a2225196f1fd281a320ac58e","datavalue":{"value":"resource-bounded reducibilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720330$CB2628BF-A54F-4A7A-984A-8072439F4741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d243e060be5f8c397fa8b96e683ca1b64d47b073","datavalue":{"value":"random oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720330$A477F9A5-496F-47F0-A8EE-9C0EAAA874ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d25697d4a14aa109c7e6855e41cd649d0485aac4","datavalue":{"value":"almost classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720330$4EABCCF5-227D-442C-B7DE-9F37723DC785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c9cba8dc6c5a4042ef924613f1b41e62b651eae","datavalue":{"value":"generalized reducibilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720330$693C1334-BA0D-4372-8F81-91C99505E7C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa3a8e187528070cbf1fed8fb82e6a6b47771465","datavalue":{"value":"measurable classes of sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720330$CD060259-A607-4780-A47A-B9BB932BC454","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":"Q2720330$EC1EF2AC-C093-4F06-89E7-0C114DD3D022","rank":"normal"}],"P1643":[{"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":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$61F09D47-192A-4603-8D4E-CBEF62F1AD48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9034487ee23c7025e9ca6778b231f0704ba6526f","datavalue":{"value":{"entity-type":"item","numeric-id":1182108,"id":"Q1182108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b389e1e2cbbb4d698b6805960581fe676dbf96d7","datavalue":{"value":{"amount":"+0.9086306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$8DF56CDF-3DFF-4305-8A27-1A140686E288","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c408db0e16b2a00386c49f4c8ec14c1b9dbf9b13","datavalue":{"value":{"entity-type":"item","numeric-id":6096803,"id":"Q6096803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8711040c9d2379f5bb32ecc5b914f0bc6e613256","datavalue":{"value":{"amount":"+0.8939666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$2816954D-3584-4D2E-94ED-921981D398A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91773b0c6bb5d8ea1f4ea867b2964473bef74a64","datavalue":{"value":{"entity-type":"item","numeric-id":5061877,"id":"Q5061877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"870f9685d0bb1448f6869b384c098a456024c9ca","datavalue":{"value":{"amount":"+0.8937409","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$89267F76-27B1-41E4-A79F-B5A52A854948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d870609124acae4f1953dce0d76a889b67d4ee2f","datavalue":{"value":{"entity-type":"item","numeric-id":2639849,"id":"Q2639849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a3dda0c5d20147d4a4cdd2c0f3a189b13711ded","datavalue":{"value":{"amount":"+0.8884763","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$60A5ED9A-CC01-4B72-9597-AEC6E8631CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b8dba0ee0b7fb52ecf33f781147252a02f5f572","datavalue":{"value":{"entity-type":"item","numeric-id":4298368,"id":"Q4298368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dbc3646c1b159dd080a707ef03b0974a7b17065","datavalue":{"value":{"amount":"+0.88018656","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$E92EC216-2271-4745-BC59-735E613DCAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00b1278129d2a320590e21198e31c119e396faf0","datavalue":{"value":{"entity-type":"item","numeric-id":5901763,"id":"Q5901763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ad09e93366c8401e6e19071b7813d830d424c72","datavalue":{"value":{"amount":"+0.87948155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$475F4DBF-42B9-4D9F-8EE6-892D1F9E93ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7ad9074a1ae5a1531f07d83336b523838272254","datavalue":{"value":{"entity-type":"item","numeric-id":3992020,"id":"Q3992020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a731e3d937b170a9fa6b9c0078616c0e7c1e24ec","datavalue":{"value":{"amount":"+0.8767429","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$ABBD59E4-4159-4870-8A3C-6F6815C07859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"544db40841c358c98abf68ee3c9e5e3dcca81354","datavalue":{"value":{"entity-type":"item","numeric-id":1351504,"id":"Q1351504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2e23a93504588b5db369788988ae0e3513227cb","datavalue":{"value":{"amount":"+0.8755682","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$BE7B867F-494D-4ECC-A27E-7A0A3FFFDF94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73a0f972df71faa26d6919bdb450cbbb031b8513","datavalue":{"value":{"entity-type":"item","numeric-id":3217603,"id":"Q3217603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"144652c68887ddebad085c56bd2fbe71adfbf7fd","datavalue":{"value":{"amount":"+0.8733269","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720330$524E22AE-F063-4FC9-8847-0E85C07FB996","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e6632ba0af45421ad31de4b7a31d2f7311d46ba5","datavalue":{"value":"10.1002/1521-3870(200105)47:2%3C249::AID-MALQ249%3E3.0.CO;2-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720330$84D676F0-E23F-40EE-9FF8-626D44849286","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"af06976d690d9221f6e5caf1bee465d7986e970e","datavalue":{"value":{"text":"Separations by random oracles and ``almost'' classes for generalized reducibilities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2720330$026BFE98-76AD-4967-B04B-333A28AD9B6B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"68cefe03c91c7bc1481d1ede29225e2a54af1e4c","datavalue":{"value":{"entity-type":"item","numeric-id":6561648,"id":"Q6561648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2720330$1770B316-1F77-4CB5-A69D-37EFF612F284","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"859ba95eb03b48bef2f76cb5714cfa14eb758654","datavalue":{"value":"The authors say that a set \\(D\\) separates two binary relations \\(\\leq_r\\) and \\(\\leq_s\\) on the powerset \\(2^{{\\mathcal N}}\\) of the natural numbers iff the lower cones of \\(D\\) with respect to \\(\\leq_r\\) and \\(\\leq_s\\) are different. Considering the the class of all oracles which separate the two given relations, the authors ask for the measure of \\(D\\) in \\(2^{{\\mathcal N}}\\) under the uniform distribution on \\(2^{{\\mathcal N}}\\) which is obtained by choosing elements of \\(2^{{\\mathcal N}}\\) by independent tosses of a fair coin. The authors say that two binary relations on \\(2^{{\\mathcal N}}\\) can be separated by random oracles iff the class of separating oracles has measure one. Let Almost\\(_r\\) be the class of sets for which the upper \\(\\leq_r\\)-cone has measure \\(1\\). In this paper the authors obtain results about separations by random oracles and about Almost classes in the context of generalized reducibilities. The authors note that the concept of generalized reducibility comprises all natural resource-bounded reducibilities, but is more general. The results on generalized reducibilities yield corollaries about specific resource-bounded reducibilities.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720330$5B691C24-3D2A-47BD-86EF-EAA96A395142","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7c0f9a5de2afd25d103c132e1617d4201a3c58e4","datavalue":{"value":{"entity-type":"item","numeric-id":591972,"id":"Q591972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2720330$AEF13A45-3218-479A-90BB-CEBFA3622B59","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2720330","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2720330"}}}}}