{"entities":{"Q1177170":{"pageid":1187919,"ns":120,"title":"Item:Q1177170","lastrevid":66768993,"modified":"2026-04-12T12:43:41Z","type":"item","id":"Q1177170","labels":{"en":{"language":"en","value":"Strong and robustly strong polynomial-time reducibilities to sparse sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 20022"}},"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":"Q1177170$BDD2A9F2-123A-49F6-8C3B-899752547379","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"858b013a35af180816f514023a118bf06f8387b5","datavalue":{"value":{"text":"Strong and robustly strong polynomial-time reducibilities to sparse sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177170$16B3215C-C2DC-468E-9029-A1B866236688","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b5e0f4c750e33ecc5c5741d0e6950a6d86ab85d2","datavalue":{"value":"0735.68032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177170$23997E1E-68E6-4965-B775-6550847A0DD5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a7f99f88c40ec4154abc71b2e16a9a9fdb5adbda","datavalue":{"value":"10.1016/0304-3975(91)90070-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177170$573305AB-C4EE-4DDE-B070-A0BD15193D84","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"571859cb8670c4008117d3f5904f654c99cfaef3","datavalue":{"value":{"entity-type":"item","numeric-id":479462,"id":"Q479462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$67743CCE-60C1-4737-B543-B1FE7183147C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"387251027f7a6e047be71bdb6ddf8e33740cddeb","datavalue":{"value":{"entity-type":"item","numeric-id":415620,"id":"Q415620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$3D6B7AA3-1DBD-4405-97CE-8ACD91DB2EEC","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":"Q1177170$70E5AD6A-FF37-4C9E-B9C8-79B1F3886A9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1177170$76EFA1F8-5632-4BE9-A61A-77A8D7274BB2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c493f971a0f43ec551af3720bd40c7328bd02bcc","datavalue":{"value":"Strong nondeterministic machines are those types of Turing machines that define the class \\(\\text{NP}\\cap\\text{co-NP}\\). When equipped with the additional feature of an ''advice'', as studied by Karp and Lipton, two different definitions are possible: a robust and non-robust version. Both versions are studied in this paper and compared. Related to this research, an oracle-restricted positive relativization of the probabilistic class ZPP is developed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177170$C0D59258-36EF-4B4E-96D9-B782138C7B20","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177170$EC2E4014-A208-4E7F-AFC5-E544537F2038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177170$DCC10B52-A142-490D-842C-54A4EB68B58D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"65264ffb26b12e50a4d98cd441d87eff7f728f61","datavalue":{"value":"20022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177170$E4A0EEFF-9E50-4F2E-A765-0E8EB6BCD1D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177170$3D29776E-03F9-4B47-B556-C3926B4F0716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f779e682d27b3fa25927137c754e8a03ed2ae5c","datavalue":{"value":"robust reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177170$D92E1F66-9AB3-4BC4-824F-56EAEBC61274","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":"Q1177170$F3EF353C-C115-4DB2-80CC-59CFCB52271D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2442cd304ca15e12b5f8ba51add5ed8113be4889","datavalue":{"value":{"entity-type":"item","numeric-id":1821559,"id":"Q1821559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$CDD0816B-80DA-4D55-A4CB-8C4BD7D93C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20dbb88399b28648dc9d78bc8b7f00777d16b9fd","datavalue":{"value":{"entity-type":"item","numeric-id":3028343,"id":"Q3028343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$DF7D9150-3C00-4597-B12F-E53748057700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4f9b219f54da4cc88e481211745b7b70548f30","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$559A7656-7F0A-40FD-B091-5B36D701A293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab0bbeb503b6269a452e86ee83e6a8c71fdfdfd0","datavalue":{"value":{"entity-type":"item","numeric-id":3734382,"id":"Q3734382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$7147CF5E-D74C-4BE0-8FB0-17C4C6B90EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37c3ecf6bbb80d30a5d10d29d6b817116fc55217","datavalue":{"value":{"entity-type":"item","numeric-id":1061119,"id":"Q1061119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$3699EF03-59A2-4930-988D-460D82B0963C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$145ACE3B-0676-4E9E-B6EE-98EEAD07CAAB","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":"Q1177170$297C74B0-8511-4305-87E1-07C357A3CACE","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":"Q1177170$C21FB1CA-6966-4EA3-8532-A83C20CFD1DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$84FDC006-DB6F-45F7-8CE4-90E9F1696AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0925a637dc2e06957900592b461ef761dc5daaf","datavalue":{"value":{"entity-type":"item","numeric-id":3817612,"id":"Q3817612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$2259D1E6-C18F-47E9-AEDE-0AA899125209","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":"Q1177170$E2116A9D-6DD0-487A-B002-AE9DE27F1E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a830cafef1f2c438cb7e2286bda476de992419e","datavalue":{"value":{"entity-type":"item","numeric-id":1052097,"id":"Q1052097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$5DCA3A38-D429-4E79-9E18-559EEB61AF40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63543c709dbc0dad9af888025f0c28158a4c2594","datavalue":{"value":{"entity-type":"item","numeric-id":802309,"id":"Q802309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$C542633D-7575-48CB-AC5F-9E775BF35F09","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":"Q1177170$0C8E384E-47D1-40E3-A3CE-BFAB15806B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ef86d27229f88234625ab5cf631770a7bacc164","datavalue":{"value":{"entity-type":"item","numeric-id":794427,"id":"Q794427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177170$9E20A16B-B1B8-45B3-8559-168E4D078AB3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"564c44b25bbacc5c6e880b167cb086d600349a15","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90070-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q1177170$CC8FE7B2-D4C0-491D-9E79-823F0C9ECA7C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"af46e0ed530ebcb3a5e24c743c18d22481655f78","datavalue":{"value":"W2523974492","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177170$1C9D1632-8FED-4A20-93C4-07AF08B37997","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d99b28e01d90fb9e4a8b0ef44d9dc319ef37024","datavalue":{"value":{"entity-type":"item","numeric-id":3812229,"id":"Q3812229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7a7355e281df338f64bf70614140ef310cc9a2d","datavalue":{"value":{"amount":"+0.8515504002571106","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":"Q1177170$F9FDE862-19F4-4592-ADFC-D22AE19E0243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8e85e69c97abfeb1a1b7ede13608a12658b9b4a","datavalue":{"value":{"entity-type":"item","numeric-id":4733404,"id":"Q4733404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d268b63634d6c41017be67f0137d294c62f17716","datavalue":{"value":{"amount":"+0.7715080976486206","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":"Q1177170$9F1CDF16-0D2F-47AA-B03C-67B45378201D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7b83dcd0ec3a841309057ad35159422a98b2d2a","datavalue":{"value":{"entity-type":"item","numeric-id":3798241,"id":"Q3798241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd2e3178a961abb9a82b15167161f2b89b32263a","datavalue":{"value":{"amount":"+0.7712560892105103","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":"Q1177170$A90A4283-DAB0-4F4B-BCDE-6C9D66BD7A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c03664d744382b13a8a312dc37c8028e4435991","datavalue":{"value":{"entity-type":"item","numeric-id":3197314,"id":"Q3197314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d59edd7d3ba530ca9eca76875d52ff46b1191354","datavalue":{"value":{"amount":"+0.7667185664176941","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":"Q1177170$9AD4FF0C-8D16-49CB-9C6B-0A0B8F08C475","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":"abc168dffe140aabdb03e191d4c8aab11a70e848","datavalue":{"value":{"amount":"+0.7612807750701904","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":"Q1177170$71586C2F-76E5-4C3E-962C-8EC929791995","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong and robustly strong polynomial-time reducibilities to sparse sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_and_robustly_strong_polynomial-time_reducibilities_to_sparse_sets"}}}}}