{"entities":{"Q920981":{"pageid":922829,"ns":120,"title":"Item:Q920981","lastrevid":65397087,"modified":"2026-04-12T02:18:53Z","type":"item","id":"Q920981","labels":{"en":{"language":"en","value":"Bi-immunity results for cheatable sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4164823"}},"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":"Q920981$F9BF3B4E-11F5-42CB-9998-E4F8272083F0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ce0aa61740e878e28b868c36f372d478077c26d","datavalue":{"value":{"text":"Bi-immunity results for cheatable sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q920981$0FBEA2A7-62FB-4BD6-A518-1CBFD0E71331","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fdeb85ac3af0a7d19829ad3f4c88f5ef809583d2","datavalue":{"value":"0709.03032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$8F407A70-BCA7-4BCF-BA74-1B232AD3F1F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d0c30564bfc3572085d132ddb5741336e40c9cbf","datavalue":{"value":"10.1016/0304-3975(90)90177-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$F366986F-5C22-4E8B-B5BC-5FD129118B3E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0353358515be2d1b5877a1b267862980a7b952cd","datavalue":{"value":{"entity-type":"item","numeric-id":294935,"id":"Q294935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$5A46BF01-1C00-4653-ABDB-665C4097EE17","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":"Q920981$31BF47E4-FD76-4485-8355-B28919931991","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q920981$FD91B293-8B66-4A8C-B156-F4B85537ACFC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"465c97a4d2e5caebb560bdabea8f9d589eb7ca1e","datavalue":{"value":"A bounded query class contains sets and functions computable by algorithms that make a bounded number of queries to an oracle. These queries can be made in series or in parallel. A set A is called k- cheatable if there exists a set B such that \\(2^ k\\) parallel queries to A do not allow us to compute more functions than only k serial queries to B. A set A is immune for the class \\({\\mathcal C}\\) if A contains no infinite subset that belongs to \\({\\mathcal C}\\). A is bi-immune for \\({\\mathcal C}\\) if A and \\(\\bar A\\) are immune for \\({\\mathcal C}\\). The paper studies bi-immunity properties for cheatable sets. Theorem 4.4 constructs 2-cheatable sets that are bi-immune for arbitrary time complexity classes. Theorem 5.5 shows that if a recursive set A is bi-immune for P then there exists a nontrivial 1-cheatable set that is polynomial time m-reducible to A. As a consequence, Theorem 5.6 shows that if NP contains a set that is bi- immune for P then NP contains a set that is not a polynomial-time Turing- equivalent to a self-reducible set. This result provides a plausible condition under which NP intersects a non-self-reducible polynomial time Turing degree and hence gives a partial answer to a question of Selman. In the last section it is proven that there exists a set that is k- cheatable but not (k-1)-cheatable, for each \\(k\\geq 1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q920981$4FED7591-E4DE-4827-ABDA-47C919FF026C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$8E82905C-B294-423F-B097-0EC99B72E256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$C27D4773-E9D0-40D7-AFEB-AC31C08D991D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$EC268C6C-9B10-4EFB-835C-332883FD2C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$8E610251-4173-4086-B8A4-AE69D0FE342F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5556003850f872a5ea1cce13b11cf9350357f77","datavalue":{"value":"4164823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$F9B30C3A-1B5E-415B-8F5A-85E772F595C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q920981$10C65101-AFF3-4DBB-9407-DC8362A31478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d00c7ace5c762c0e9b4707947ca4fec465dcc340","datavalue":{"value":"bi-immune sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q920981$84C014B5-A7D2-40F9-A7B8-73769543B102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ce85c4e56ba944f6d9d4825d8d9366b7630acad","datavalue":{"value":"bounded query class","type":"string"},"datatype":"string"},"type":"statement","id":"Q920981$4330409C-EB93-4DE3-B10E-F5B572F33AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac873341ab34d6db98676ef037e18583cae25841","datavalue":{"value":"oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q920981$83801DCC-E259-44EC-AF62-FB095237219C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73d7f8328c3292b8b044503ace50287014ee62e4","datavalue":{"value":"cheatable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q920981$F7380DED-BB8A-476D-B428-4879BDCEA414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"948cc8cdb885a280b485e2da2b71f5dbbc318ce4","datavalue":{"value":"Turing degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q920981$DADC499A-22F4-488A-A0FC-0D3278B15908","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$837E63BC-D23D-4FD7-81C6-9144C7AE7C55","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":"Q920981$4FF9D4B9-9CA2-4263-8552-1CE3A6FCE478","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"90e1bb1cb44d6c5f0b383e96f621c2bb23767aac","datavalue":{"value":{"entity-type":"item","numeric-id":1104077,"id":"Q1104077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$85FA9308-4533-4C66-8CB4-A59BD3833ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$009A74C9-3A06-4311-B3D0-38FC43B0D491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0f95a774381c0a85c6c478f1cfa3c8eacecfc93","datavalue":{"value":{"entity-type":"item","numeric-id":1178690,"id":"Q1178690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$9E935BB8-4B72-472E-9532-71F49375ED71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"018038fb101d8ec315a3c155690ad0c57968b1f9","datavalue":{"value":{"entity-type":"item","numeric-id":1803657,"id":"Q1803657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$9C73A6D9-616D-4941-A16D-E999BE440774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec53d3b2bd50d99bc1ad2d6f00f6523e5d308248","datavalue":{"value":{"entity-type":"item","numeric-id":1114678,"id":"Q1114678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$56855C7C-4F96-4DC2-ABA1-9B17722B2FEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$877BF5C4-83EF-4B29-A1D8-D82706F4242F","rank":"normal"},{"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":"Q920981$7A54DDB5-D777-4BD5-9D5A-8236BC16A7C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3737257493e45989645a4ef4e506cbef38d9e9e","datavalue":{"value":{"entity-type":"item","numeric-id":3816983,"id":"Q3816983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$F6ACF2CE-81E9-45CA-AB9C-2C3FB31E380C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73e0fbe81e379776e1e2a5d75481d222ad0e52a7","datavalue":{"value":{"entity-type":"item","numeric-id":4852904,"id":"Q4852904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$305CAEA6-73EE-4DC4-9A68-28EEFCF8285E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37339a07f524bcda76ba9abd764c0c40fbeccfcc","datavalue":{"value":{"entity-type":"item","numeric-id":4205078,"id":"Q4205078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$C4B64A1C-F6D2-4E49-B990-0C11F3A414F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df5f2db7f566151b52a61a66c4ae324de1e95ea0","datavalue":{"value":{"entity-type":"item","numeric-id":3760533,"id":"Q3760533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$AE393E85-6D36-4BD5-B5E7-11101F8C3F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8a85dafc6120ebd9cff857c23c970d64f2baaf0","datavalue":{"value":{"entity-type":"item","numeric-id":2366689,"id":"Q2366689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$48244820-1423-41A6-88E4-AA6DD3A0E9EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4360fb17af7ffff93385595ddc049810e9169f73","datavalue":{"value":{"entity-type":"item","numeric-id":2366567,"id":"Q2366567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$649068C0-696E-4ABD-9B26-78BD4E77874A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91437bc3f5649edc6a7acb3095e2cdec844eb2e9","datavalue":{"value":{"entity-type":"item","numeric-id":3711749,"id":"Q3711749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$D4AE2928-88F7-4126-A066-EBE2D1A9A85C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2bcba6abf24137e5ea317e56b32f617a34d2b1e","datavalue":{"value":{"entity-type":"item","numeric-id":795829,"id":"Q795829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$09EECC2C-39A9-4397-8DBB-3DB42861467B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$4E673010-2684-425A-8A0E-3B20DB23C0D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ec7ac9d1de9d25b673182dfb0ae85dd0acb605f","datavalue":{"value":{"entity-type":"item","numeric-id":1097695,"id":"Q1097695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$E9DBE31D-D6AB-42F5-AC00-0CE77A879E9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30f6e432ce9e9ae75031144ac1199e0b83ca0d7","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$ABA6A47F-1B55-4177-BAC5-F55C2B88587D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$57565EA7-07EF-4AEC-BA02-6561625FA200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cacefeedbc112be8dbe48f89e8cd3c176bb87a52","datavalue":{"value":{"entity-type":"item","numeric-id":3816974,"id":"Q3816974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920981$35E9538A-20E7-42C4-B533-6248BF3D5355","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e2f957fab4260188d11e44f0d71128cb659458db","datavalue":{"value":"https://doi.org/10.1016/0304-3975(90)90177-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q920981$C27F2E23-EA45-4F1C-A8BD-2E9AE6935AED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1b9eb4c3ef8880a4d6f7eebc3cf554dcd400bd0b","datavalue":{"value":"W2006337101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920981$87EFAD85-1322-4F26-9359-F798A66AB4DF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"351e81c37f71c7a11aabe5c952105f3e97a4bbdf","datavalue":{"value":{"entity-type":"item","numeric-id":2366689,"id":"Q2366689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17b30ac05265583bc72df00b59578d4388f3d195","datavalue":{"value":{"amount":"+0.8378589749336243","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":"Q920981$2FD6BC36-6B32-41D9-87E0-BC05CE516DB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d92e8b8ec28bb6879a80878ab5b486dab6dc6e5","datavalue":{"value":{"entity-type":"item","numeric-id":4736858,"id":"Q4736858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e13587a64b262199d4404d192bfe6401d91cc4c","datavalue":{"value":{"amount":"+0.8304221034049988","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":"Q920981$946A267C-544B-4168-B08A-F7A36FC8FFCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bc120d84c531a58f8777b29b4610d43fe4840ac","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"087ae08a47b5e22cc6bd362be62da9d563789b42","datavalue":{"value":{"amount":"+0.8045821785926819","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":"Q920981$F3CFC8E2-FB8A-4228-8021-13549ED0C0CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80d91cc9821c6725823c2d63fcff39dc4e81373f","datavalue":{"value":{"entity-type":"item","numeric-id":4895818,"id":"Q4895818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b8ea2385b9111ce4a11744e08baff01e4ad01e2","datavalue":{"value":{"amount":"+0.7787317037582397","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":"Q920981$86AF3A74-51AE-4EC3-8304-3AF82466E249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1a873700fe5eddf2a8a9143f906333837112e4d","datavalue":{"value":{"entity-type":"item","numeric-id":3347296,"id":"Q3347296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b742db6ae62040d64cf784c1329c4ec76b1c413","datavalue":{"value":{"amount":"+0.7727741599082947","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":"Q920981$7280F163-3C6A-4DEC-9622-581FB8476D7F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bi-immunity results for cheatable sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bi-immunity_results_for_cheatable_sets"}}}}}