{"entities":{"Q5941441":{"pageid":8118243,"ns":120,"title":"Item:Q5941441","lastrevid":47658898,"modified":"2026-01-02T08:55:44Z","type":"item","id":"Q5941441","labels":{"en":{"language":"en","value":"On boolean lowness and boolean highness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635634"}},"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":"Q5941441$37D022C7-1C59-4F08-8871-C2D955532EB9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f669a0bc7920a4f12361e458e1e93b074ef65fc","datavalue":{"value":{"text":"On boolean lowness and boolean highness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5941441$CF49D066-6983-497C-A559-009568C11340","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1235a87ed08c90da82b3f1fdb29f6840bb956b0b","datavalue":{"value":"0974.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941441$01FADA14-FF6D-420B-9BD4-3D78780BC315","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"912483aa0c9527808dec361675c9fc2244d70ca7","datavalue":{"value":"10.1016/S0304-3975(00)00146-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941441$E1509C13-9F03-4C51-8CC4-D707F1B192EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3159804ca6f0602b316a77f101c077975d3e09ae","datavalue":{"value":{"entity-type":"item","numeric-id":1044707,"id":"Q1044707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$EACC4A59-1355-4A93-9776-BF4C55FC2DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05ccf9363a2b93804ef06018f3f40241df688bac","datavalue":{"value":{"entity-type":"item","numeric-id":675063,"id":"Q675063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$494B5F0D-DC5B-45E1-896E-B1E530F5DE7F","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":"Q5941441$3FA23A48-FE00-4A9B-94D9-38DF53369532","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5941441$20A152BD-E457-4F06-9B12-D98AA48D03DD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d070b97779f4770da4b8bae59ee373c2f15e410a","datavalue":{"value":"The concepts of lowness and highness originate from recursion theory and were introduced into the complexity theory by \\textit{U. Sch\u00f6ning} [Lect. Notes Comput. Sci. 211 (1985; Zbl 0589.03022)]. Informally, a set is low (high resp.) for a relativizable class \\(K\\) of languages if it does not add (adds maximal resp.) power to \\(K\\) when used as an oracle. In this paper, we introduce the notions of boolean lowness and boolean highness. Informally, a set is boolean low (boolean high resp.) for a class \\(K\\) of languages if it does not add (adds maximal resp.) power to \\(K\\) when combined with \\(K\\) by boolean operations. We prove properties of boolean lowness and boolean highness which show a lot of similarities with the notions of lowness and highness. Using Kadin's technique of hard strings [see \\textit{J. Kadin}, SIAM J. Comput 17, No. 6, 1263-1282 (1988; Zbl 0664.03031); \\textit{K. W. Wagner}, Number-of-query hierachies, TR 158, University of Augsburg (1987); \\textit{R. Chang} and \\textit{J. Kadin}, SIAM J. Comput. 25, No. 2, 340-354 (1996; Zbl 0844.68048); (*) \\textit{R. Beigel, R. Chang} and \\textit{M. Ogiwara}, Math. Syst. Theory 26, No. 3, 293-310 (1993; Zbl 0776.68043)] we show that the sets which are boolean low for the classes of the boolean hierarchy are low for the boolean closure of \\(\\Sigma_{2}^{p}\\). Furthermore, we prove a result on boolean lowness which has as a corollary the best known result (*); in fact even a bit better) on the connection of the collapses of the boolean hierarchy and the polynomial-time hierarchy if \\(BH = NP(k)\\) then \\(PH = \\Sigma_{2}^{k-1}\\oplus NP(k)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$640DFACF-695C-4AF8-9108-E3526C5FE1B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941441$6B386B92-1F27-43EC-8DF6-27C4BA15542F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941441$828F2975-AD63-43FD-847D-CEF99C1F28E5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c3d317468ceb1fc2198ef3a5d683def27056fd0","datavalue":{"value":"1635634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941441$35823DDC-656D-4969-ADB7-113F9A982467","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$610FA6FA-73CD-49B0-A0AE-BD471D0A1F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"008c70e766fc4d68d17a2a73ce059b3504dee5b7","datavalue":{"value":"lowness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$7E89C48A-9EE0-4C29-AD63-855BF69F351A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e23327e0505c1f7dc40922ee44ccebbc98309229","datavalue":{"value":"highness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$D64A5807-8E7B-441F-B2DB-8EF1218B6096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10de85f0eb5242fe20ea9d3a91e834741a531348","datavalue":{"value":"Boolean lowness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$C6C16213-52B1-482F-8F6B-DD1849694F84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed63df5e84bdb85cc7c0ea14ff740f51c5c1263b","datavalue":{"value":"Boolean highness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$C2485C46-5D65-4DE2-9B51-0E00D754CBE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1e10e42df7624f4c44e25a596575282d4d3f781","datavalue":{"value":"Boolean hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$579D7B58-AA0D-4E87-A8C1-4AB7C1616A56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"319f7aef6d48907b019428ced327b73484cf6132","datavalue":{"value":"polynomial-time hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$F4013F6B-FB28-41EF-BA06-1EF4A85AA573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d46e34fee9262f2021c8dec9af668e9432a08c0f","datavalue":{"value":"hardeasy","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$A4FF2C80-DF1E-4F60-9A75-9E52456A3973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27b4bcaa7445bec056c59ce6aaf9a1f2114fd968","datavalue":{"value":"advice","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$167F1855-1D46-4A60-A44A-90C33BF5EFA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c07494b98b2fceb96b2946fa9c4e62544202cf81","datavalue":{"value":"collapse","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941441$8B4478EA-13E8-446E-BA50-E3AF85A631F6","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":"Q5941441$42302F44-0B5C-4FEB-8B77-F0AD9FFBE1AC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"63bfe07f4dda7d726618c463adce3babd3960876","datavalue":{"value":{"entity-type":"item","numeric-id":5289273,"id":"Q5289273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$B4AE5A42-3772-47C8-86DD-3F46724D45F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bcb11f0b30802ff1fa8b04ab34822dc12429034","datavalue":{"value":{"entity-type":"item","numeric-id":3832042,"id":"Q3832042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$AE36CE19-52DF-4C8D-A03B-901849A33106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d5257f71d98a6e1899a8d1ff1a09a30fa28cbba","datavalue":{"value":{"entity-type":"item","numeric-id":3751004,"id":"Q3751004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$8789F27C-13A3-485E-9BC9-E13A8329296C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e02d789c690c4ce2b5c788e44ec22ce9bffeca3","datavalue":{"value":{"entity-type":"item","numeric-id":4877522,"id":"Q4877522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$C2666A1B-B29C-40DE-9253-7635CA23FBD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"630502f4633188214eb873a5b8ff17fa97f68516","datavalue":{"value":{"entity-type":"item","numeric-id":4067085,"id":"Q4067085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$45DB66A9-F93A-476E-AB62-8C3F18481128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b2a1a71b49ec8a49d1aaa20916821b36ece12fa","datavalue":{"value":{"entity-type":"item","numeric-id":3815290,"id":"Q3815290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$9D2ACC90-3BF3-4235-804C-AEB916E24F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b832ae6038bd66626b817aa4f18e62fe9f667e","datavalue":{"value":{"entity-type":"item","numeric-id":3783278,"id":"Q3783278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$7EBC671B-EA42-4C14-B82D-673716073BE2","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":"Q5941441$53B86665-F3D8-4F5F-AFBF-B8178AE19B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85142f9eddeae15f922cda6aafc209cf0fdc25c3","datavalue":{"value":{"entity-type":"item","numeric-id":4767305,"id":"Q4767305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941441$0FAAEBF4-36B0-445E-BFFA-DE5757A4ECC0","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":"Q5941441$7F855E16-81BD-4A29-A302-0FD91FA906C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a80901a87758dbd3f6fd371476cf35508dde9d06","datavalue":{"value":{"entity-type":"item","numeric-id":4218416,"id":"Q4218416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"350f9ba431d644d7794361a3b3a4f362860a90f7","datavalue":{"value":{"amount":"+0.99716055393219","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":"Q5941441$E534D2BF-1937-47E8-A94F-086740F6B914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c52e75249860ce100ea4c494e99eead0bbaf93ac","datavalue":{"value":{"entity-type":"item","numeric-id":4336270,"id":"Q4336270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c22bb18b65f714c76c2c7b0517cc4148cc1bf14d","datavalue":{"value":{"amount":"+0.9962822794914246","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":"Q5941441$DCD454F5-5367-40ED-A7E8-FFF24C6ACA8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b120daf503015de524b80d37040131e3dd0ca34","datavalue":{"value":{"entity-type":"item","numeric-id":3832042,"id":"Q3832042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4fdea429a30dc8c40622fc5caa843f6da63a9e9","datavalue":{"value":{"amount":"+0.8187753558158875","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":"Q5941441$B48B6B9A-44E0-4CA9-A77B-BE8E7E38354D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2632ff90cec6c827b1a18967f6839eed579bbd02","datavalue":{"value":{"entity-type":"item","numeric-id":4729352,"id":"Q4729352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cead66d9687e9a6bfd4ef628ba2d10922608bc9c","datavalue":{"value":{"amount":"+0.7902190685272217","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":"Q5941441$4D33B5D8-5569-4475-A6DF-59E7A061C5FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7db37d09960acfcdc41a6a1e335152b55fc35287","datavalue":{"value":{"entity-type":"item","numeric-id":3751004,"id":"Q3751004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5796e03ab4272291b346c564cc09ce66f30d7cf0","datavalue":{"value":{"amount":"+0.7823575735092163","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":"Q5941441$7568D783-6EB9-432B-BC06-7CEF744821FC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5941441","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5941441"}}}}}