{"entities":{"Q1120564":{"pageid":1131313,"ns":120,"title":"Item:Q1120564","lastrevid":66170739,"modified":"2026-04-12T08:01:26Z","type":"item","id":"Q1120564","labels":{"en":{"language":"en","value":"Nondeterministic bounded query reducibilities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4101156"}},"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":"Q1120564$FF186766-5F0E-4C46-BCA6-FB595D2605FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aed9eb8fe788b8f111b077a761cf973c7acf7127","datavalue":{"value":{"text":"Nondeterministic bounded query reducibilities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1120564$E56E9431-5FAD-4624-B05A-C6D1B1A897E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"499795275ac79af8fe575709773d5601186373b8","datavalue":{"value":"0673.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$3FC7D348-6B92-4B73-B424-8CC529F13C3E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4b06b75159c6f7eeabc6b838e22df3b8b84611f5","datavalue":{"value":"10.1016/0168-0072(89)90010-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$A8225F94-0644-4BEB-A380-2914ADE77B7C","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":"Q1120564$7631AA21-6ADB-4086-88EA-74F6906E3230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d63fb644043f68eec80a16990f4f5c12af2bb809","datavalue":{"value":{"entity-type":"item","numeric-id":811135,"id":"Q811135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$968F03FC-3687-4FED-952E-09E77ACF65DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7fd561545deec8fab09cfc2c54c772a4bf11dda2","datavalue":{"value":{"entity-type":"item","numeric-id":1053726,"id":"Q1053726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$D1206EB4-50BD-47B7-9FC9-AA4D8BCD6BEE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$849DE033-C28E-4A06-B3A9-97ACF63A56F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1120564$6070ECCA-4BFB-42A1-B5EA-DCEB9501A244","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84441fce128e6000668334b43d1c42f2a09992e1","datavalue":{"value":"The behavior of nondeterministic oracle machines with a bounded number of calls to the oracle is considered. For any set A of natural numbers we define \\(F^ A_ n(x_ 1,...,x_ n)=<\\chi_ A(x_ 1),...,\\chi_ A(x_ n)>\\). Denote by FQ(n,B) (NFQ(n,B)) the class of functions computable by a deterministic (nondeterministic) machine with the oracle B and with at most n calls to B for each (branch of its) computation. A set a is called n-subjective if \\(F^ A_ m\\in NFQ(n,A)\\) for all \\(m\\in N\\); it is called objective if, for all \\(n>0\\), \\(F^ A_ n\\not\\in NFQ(n- 1,A).\\)    In the paper the authors give a series of interesting results on the classes NFQ(n,A), some of them are the following: 1) Each truth-table degree contains a 1-subjective set. 2) If A is any set, then A' is 1- subjective. 3) There exist 1-subjective sets A such that for all n and all sets X, \\(F^ A_ n\\) is not in \\(FQ(n-1,X);\\) 4) If A is 1-generic, then a is objective; 5) Each non-zero r.e. Turing degree contains an r.e. objective set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120564$5D5E864A-F84A-473C-BCBE-A5D78A050225","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$F904DDA7-A634-4D92-B5F2-060BF7694907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$E3BE06DC-9912-42DF-B570-079DF80FA606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$E6E77B38-E409-4422-B8A9-C415E01E86E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$C5D42C09-77C0-4615-9C06-8EB872B08785","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f15d37cdcce4720c35972866302a2e74e3fea554","datavalue":{"value":"4101156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$4E257F7A-45C8-4AB4-8CA7-B3BA0F367695","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61dd4b8baccafeac84da9f92320b68785c2e4efd","datavalue":{"value":"nondeterministic oracle machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120564$5C009229-38E1-446F-BCCE-2C0801EFE6D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"896b0cf48c10bf6ed097f0bcf4ff75c106efa95b","datavalue":{"value":"bounded number of calls to the oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120564$B39FA524-3D2A-48B5-BF93-610A63A8A6DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d51e3ba22437282e4bac88a1af8e42b6f9a006c","datavalue":{"value":"truth-table degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120564$BE8AD5BE-D4E3-4A6A-9227-A4FF1FBFAAA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea9876f73b7408e5e134d97d9e4f5c1e29f4ba1e","datavalue":{"value":"subjective set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120564$2AD9E9F8-F9F8-4DBC-8E58-F2A369661553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"948cc8cdb885a280b485e2da2b71f5dbbc318ce4","datavalue":{"value":"Turing degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120564$A99DBACB-3EFC-48C9-92C6-1FE676F6092A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51feb12b9af6f1b9ae5bf04a6cb5b139a1845df3","datavalue":{"value":"objective set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120564$3278DA16-FC5B-41C6-BBE9-13BAEE5DDFC0","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":"Q1120564$8CA3504D-8642-4FBD-BA29-0CE7E119B06A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ed77be0b4b94dddeceb9b5c32c63d92d97a45a1","datavalue":{"value":"https://doi.org/10.1016/0168-0072(89)90010-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1120564$11CF6185-0B28-448C-B08B-8D58AD7384B6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"356652ad31cf74c1d1261d60032ef2466bd9098e","datavalue":{"value":"W1987375835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120564$DDAB3214-771B-4063-9C2C-B4B678AE84D2","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":"Q1120564$BCCC15BD-DAC0-4E3E-83E6-E522831AC118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26a009c8d67c6a95c6e0e4c2c5ad56812751488c","datavalue":{"value":{"entity-type":"item","numeric-id":922525,"id":"Q922525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$2D073F5D-DF24-40DB-A98D-834428601557","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":"Q1120564$7C324E0C-82BF-4B4E-940D-4DC5130C0A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ce84a7b1c7ab92c6703d5ab4009b1868b2001c8","datavalue":{"value":{"entity-type":"item","numeric-id":5829026,"id":"Q5829026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$12310A20-2CB6-4505-AC4C-BA1867CEA100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbef6bbbe60bfce0721481461ecfc4b8834e00f9","datavalue":{"value":{"entity-type":"item","numeric-id":5595155,"id":"Q5595155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$1E02F91A-3D33-4485-AD22-B2D5A727C1EB","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":"Q1120564$0D13A6A7-D5E9-4A42-966B-F19F31C6365D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c9cf122d104d7332be7d6610d7ce2681b03b64","datavalue":{"value":{"entity-type":"item","numeric-id":3768398,"id":"Q3768398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$C2A5CE13-9B07-4EF3-9F75-F83C70CB5D6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$E0262544-9157-41D9-AED8-4CE3BDA900DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74c96627f7e03b86be9aa1e5ea2faf1f15b9779e","datavalue":{"value":{"entity-type":"item","numeric-id":3779740,"id":"Q3779740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$89E0CA36-27F9-489E-9C8F-B806E7D9BED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6be2378be9ef718165d6decb820a8d040ba744","datavalue":{"value":{"entity-type":"item","numeric-id":3766851,"id":"Q3766851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$F13213BE-4C76-4E4E-A9D6-5D5FEBB4EFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f83662ae316121ea72100b37e1d7f310700b0f0a","datavalue":{"value":{"entity-type":"item","numeric-id":3703297,"id":"Q3703297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120564$67297552-5F42-4F07-8640-FE22F631598A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fa064bfbe170202376466e09df6e88da3c0381f","datavalue":{"value":{"entity-type":"item","numeric-id":4953205,"id":"Q4953205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f50660da94be70af1c7e6b39c1753002922760","datavalue":{"value":{"amount":"+0.7773596048355103","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":"Q1120564$8AB343B0-0EFC-435A-AA9E-20716822C698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f03620465fe12ccaa024596240620d9be60a2953","datavalue":{"value":{"entity-type":"item","numeric-id":3347297,"id":"Q3347297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f50660da94be70af1c7e6b39c1753002922760","datavalue":{"value":{"amount":"+0.7773596048355103","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":"Q1120564$0704B17C-DC36-43F8-9395-8E1CF3DC5A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45c9bee22fa096653731920c7e5a0174751a05b0","datavalue":{"value":{"entity-type":"item","numeric-id":808242,"id":"Q808242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c28bbd15a725c01a1a844cf68634b344c2ae839e","datavalue":{"value":{"amount":"+0.7759467363357544","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":"Q1120564$F61FF4FC-B7D8-48F5-A07F-3DC67150D178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1413bc63ede83fc1dd3e9430ddb04778c3d00d2","datavalue":{"value":{"entity-type":"item","numeric-id":1114678,"id":"Q1114678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e8ce374cbb9c25cc688fa19f1853f126ab64a20","datavalue":{"value":{"amount":"+0.7651338577270508","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":"Q1120564$ED1F41AC-30FB-43C6-9D7A-FA4E8A464EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ad67e0d0f7606665242f0946a2f02dffe1a8a5d","datavalue":{"value":{"entity-type":"item","numeric-id":1178690,"id":"Q1178690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c158f3018e11696767f267f52a745721e5fd2f66","datavalue":{"value":{"amount":"+0.7626847624778748","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":"Q1120564$A7EC7CB8-7592-4518-8C64-BC35643A56EB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nondeterministic bounded query reducibilities","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nondeterministic_bounded_query_reducibilities"}}}}}