{"entities":{"Q1097695":{"pageid":1108447,"ns":120,"title":"Item:Q1097695","lastrevid":69635157,"modified":"2026-04-13T08:21:22Z","type":"item","id":"Q1097695","labels":{"en":{"language":"en","value":"On helping by robust oracle machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035140"}},"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":"Q1097695$8B502DFA-8487-4634-820C-56FDAAD5E6A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d5d767ab024714a934c9781c65bcc382cb6daa79","datavalue":{"value":{"text":"On helping by robust oracle machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097695$AA658019-5C2A-4FBC-9F9D-9D34E4B6ECBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"53ca3bb0d1538efec6d325fd329a7094a79eed05","datavalue":{"value":"0635.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097695$85AF0E56-ABC8-4E4F-B7A5-C6925E382C1A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f1518a979332b3090aa8288ee3ed0331b4359f3","datavalue":{"value":"10.1016/0304-3975(87)90078-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097695$D70936FE-1150-41CE-8B0B-2BFE08646876","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":"Q1097695$B9CE737C-EE16-4C54-9505-6679A091D318","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1097695$86BFF06F-1294-401E-97D3-64C8F2C2EE12","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cdedfb0f8ffe6294c7124785db6c39bd1e95e286","datavalue":{"value":"The concept of helping using robust oracle Turing machines (TM) was first introduced by \\textit{U. Sch\u00f6ning} [Theor. Comput. Sci. 40, 57--66 (1985; Zbl 0574.68041)]. An oracle TM is robust if its output on an input \\(x\\) does not change when oracle changes its answers to the queries made by the TM. Thus, an oracle can only affect the computation time used by the machine. An oracle is said to help a robust TM if the machine runs in polynomial time using this oracle. Certain interesting structural properties about helping sets in NP have been observed by Sch\u00f6ning.    Some more are observed in this paper. For example, the class \\(\\mathrm{UP}\\cap \\mathrm{co-UP}\\) helps exactly sets in the same class, where UP is the class of sets computable by unambiguous NP machines [\\textit{L. G. Valiant}, Inf. Process. Lett. 5, 20--23 (1976; Zbl 0342.68028)]. New notions of helping such as one-sided helping, self-helping are studied and compared with other standard notions of complexity theory such as self-reducibility and sparseness. Several known properties of these standard complexity notions are reproved from the viewpoint of helping.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097695$1CBBAFE1-B486-470D-819B-5979DFBAF751","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097695$535BCEFB-F0E1-43C6-97CA-9E7801CC6649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097695$71BDE35B-8EC1-4AA3-BE63-0149601DC318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097695$5BDA06BA-0638-433E-B1EC-48FB889CB62F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3857a4a83284a88802479fd71060d90442fd624","datavalue":{"value":"4035140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097695$82A6C2A6-9AAB-41A4-A416-DACC3FC72EE6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a42ae7db49f21df66cabed7b99ae4ab9573687e3","datavalue":{"value":"helping","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097695$B5D42FC3-F010-4E12-A029-0D8A261E2698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bca7b5d336afb6a49ba0586a47a156d325fe25e","datavalue":{"value":"robust oracle Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097695$42617E89-EE60-426B-9326-AF1E69346E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097695$A8B892C7-24A9-4466-8AEC-18A532BBC0DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11acd2fb6ad6c566c252aa4b6fd795400412f6ca","datavalue":{"value":"complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097695$0015FA13-D798-4B3A-9A74-29E4E027D67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bf39ff67c734ccef72308ae15736ee44ba84c0c","datavalue":{"value":"self-reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097695$6FA5CB4F-8A3D-417E-B9DE-1EC1C6BFC683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6fb3908bc773a3c8dcab1b40a40883840b18de8","datavalue":{"value":"sparseness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097695$B1764DE3-78CE-4B34-9461-B520D980196E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"13bc86079a0769c5ab1c6f28dc4e52a39f4a573a","datavalue":{"value":{"entity-type":"item","numeric-id":1295380,"id":"Q1295380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$41F0D8DB-6ADF-4DE5-946D-3E31A7C56AEC","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":"Q1097695$A6E0ADB2-5296-47AC-B9DA-124FD6F1E8DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"197e7e46cd5b925071cc741f48cdeeb62936af37","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90078-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097695$3A298205-0EF2-4BCB-8A75-AC8C6C3B8E48","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"37b6803869319db3c44be243e0bf0c2c28990d59","datavalue":{"value":"W1982143949","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097695$F260F5E1-2294-442B-A675-FE252612FB01","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$D56DEE77-7945-4A78-A336-6D6997599A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$90A41E07-827E-46F1-8C7B-AA57CA1D00E8","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":"Q1097695$78BC1749-BBC0-4A27-8996-8FB9708CE64C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6bef531e3c54b91b631aa952c0ca63f0ac7db19","datavalue":{"value":{"entity-type":"item","numeric-id":1054475,"id":"Q1054475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$FFDD216C-921D-4300-B2D0-43204E55C4BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b543b24a2524e76130d5c1525baa40aa9abdeef","datavalue":{"value":{"entity-type":"item","numeric-id":3675520,"id":"Q3675520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$22C307E4-8113-462F-9DDB-62CC7F7B9BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$BBAB89DD-AE93-40C6-B016-C0D184054115","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":"Q1097695$F97D499C-2085-419E-A34C-93C420DA2FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e593adf34f4d5518c8bccfbcb13428e1fbf4411","datavalue":{"value":{"entity-type":"item","numeric-id":1063417,"id":"Q1063417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$DDAC0475-46C7-47FB-AA38-0B3FDCF68477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ff2c269b97a88de0fe652e2add75347876b7e3","datavalue":{"value":{"entity-type":"item","numeric-id":1361890,"id":"Q1361890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$1F4900F3-AF73-4DAF-80C8-87A623AA0619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d18e4b439adfecff09b2cf1367d09302baaa3617","datavalue":{"value":{"entity-type":"item","numeric-id":4739905,"id":"Q4739905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$298511CE-9E10-4F27-AE9E-2C949B65C63B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$3F59DDBC-0F38-4B96-A00A-648E1E7DC773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$E358B63D-382A-4C3A-AFF8-BE2F85621BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3380ff6f4b5d07929c4c395a1faa8794b1c8021f","datavalue":{"value":{"entity-type":"item","numeric-id":3768891,"id":"Q3768891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097695$DE42F60C-6327-4760-ABD3-30121177FBC9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0f740496bf4dc5da008e74201a2d86a2f4ad3a4","datavalue":{"value":{"entity-type":"item","numeric-id":4967176,"id":"Q4967176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cc6e8c2ca6711dced3d1aa727864986fbcc66a0","datavalue":{"value":{"amount":"+0.8778950572013855","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":"Q1097695$05E11387-3B02-4C95-A3AA-2D6835088E94","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":"ed562d2ee4389298dcf410634c4e8840e1e2c7d2","datavalue":{"value":{"amount":"+0.8614755868911743","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":"Q1097695$7C33F4E8-627A-4AC0-B3A6-E3C9E1D01563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56a1235ea67e059e30396bc69e0301823dbb56b7","datavalue":{"value":{"entity-type":"item","numeric-id":3217606,"id":"Q3217606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be7072ba3eaf8926f324da6094a7dadeea6bb60b","datavalue":{"value":{"amount":"+0.8417282104492188","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":"Q1097695$308AD739-94FE-45C3-A0C5-4583A5305252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0f0132151f6f27bd6cc5ffb410ea35eea8315a3","datavalue":{"value":{"entity-type":"item","numeric-id":1349740,"id":"Q1349740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4245f83177a55bfd58cabea7043f2e3e9f8fcd6","datavalue":{"value":{"amount":"+0.8323577642440796","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":"Q1097695$7BCE7D99-9B5F-4C7B-BE74-8B4FE0C3978F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"680a1df87692e166430862efcb0c638c7dc6f080","datavalue":{"value":{"entity-type":"item","numeric-id":4525694,"id":"Q4525694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cc5e2e354c3dae2b3815a4dee4f77d68216286f","datavalue":{"value":{"amount":"+0.8317806720733643","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":"Q1097695$B4DE3CC8-5CCE-4F47-9DCD-B5C8526123F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On helping by robust oracle machines","badges":[]}}}}}