{"entities":{"Q2639638":{"pageid":2650381,"ns":120,"title":"Item:Q2639638","lastrevid":49458232,"modified":"2026-01-07T04:57:10Z","type":"item","id":"Q2639638","labels":{"en":{"language":"en","value":"Positive relativizations for log space computability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4185030"}},"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":"Q2639638$898D3337-4EC4-40B2-A514-3FAF9A8A5776","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4cb6f161bddff1a81547a1e6c3636f1f04755f4c","datavalue":{"value":{"text":"Positive relativizations for log space computability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2639638$BA7C84C3-8EC7-4593-B8EC-BC7661D88AB6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"947527e19c610eb064f62651716c144cba25d0ea","datavalue":{"value":"0718.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639638$8C72FE20-2537-4518-8462-3110CB330971","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2e9fcdf02b2b76136ee21abe297875a2610e023c","datavalue":{"value":"10.1016/0304-3975(90)90168-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639638$0E5AB1BA-69DF-4BCB-AD6C-2AE914117AEF","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":"Q2639638$AAFAF89C-992C-4AEC-822D-C1A9CB7D0580","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":"Q2639638$B9ABDEA8-102F-4EC1-888B-35D73250A417","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff5dd6aae3b525ea38de708509a8719d621300c2","datavalue":{"value":"The open problem whether the inclusions DL \\(\\subseteq NL \\subseteq P \\subseteq NP\\) are proper or not is considered (DL resp. NL denote the class of languages accepted by log-space bounded deterministic (nondeterministic) Turing machines). The author develops positive relativizations for these questions and gives characterisations of the form:    DL \\(= NL\\) if and only if \\(DL^ T = NL^ T\\) for all tally sets T.;    DL \\(= P\\) iff \\(DL^ T = P^ T\\) for all tally sets T, etc.    Using oracle Turing machines deterministically queried \\textit{W. L. Ruzzo, J. Simon} and \\textit{M. Tompa} [J. Comput. Syst. Sci. 28, 216-230 (1984; Zbl 0573.68021)], characterisations of the form DL \\(= NL\\) if and only if \\(DL^ A = NL^ ARST\\) for all oracle A, are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639638$7F207042-AB85-48CC-BFEC-98EB76F32DFD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639638$ADED2E2C-4F28-440B-BF13-11B1D4B81246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639638$5A50E9D5-4473-4753-80EF-3260FCD99103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639638$DC126E9F-BB9E-4BCF-BC64-7376C19C00CE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cf2ed15316d52d70da4d70d4d9a43f4bae84dc39","datavalue":{"value":"4185030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639638$9903CE73-8D66-4BB4-9F90-493CE5CBC0ED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66a68612f0445fc3297b08156991ad6ffdb790a2","datavalue":{"value":"polynomial-time computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639638$448A0190-90BC-48B0-A550-ECBFA98814EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba31ec8f4d64d5db54c10d60841763da88ea5f78","datavalue":{"value":"log-space bounded Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639638$FC105CCB-CFDE-40F6-805D-29C3722BF667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"225520946587a12acb525f1ffa7edd359d56cbcc","datavalue":{"value":"positive relativizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639638$9579352C-189C-49AF-AFB9-253F80383CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80a9fafab9301c90f58754c8a296c1f5661d40fc","datavalue":{"value":"oracle Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q2639638$6E682FFE-8FE1-4B6A-AC45-9FF9E62CF640","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9c03730668db67f2f0525cd022cd794bdf73f905","datavalue":{"value":{"entity-type":"item","numeric-id":916649,"id":"Q916649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$10902897-56F8-45D6-ADBC-5648750938D7","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":"Q2639638$178D5F83-51DA-4018-92E7-CABB28FD500A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$411EC059-4FEC-4E8E-80CC-5A833E939D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"110c1e2c2af0807cf63aca7e44f16f8f618495f4","datavalue":{"value":{"entity-type":"item","numeric-id":1253656,"id":"Q1253656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$0395DB72-7867-4C19-BA52-85C1DC696D28","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":"Q2639638$FD72E4AB-DA5A-4057-A521-B43F0E8464ED","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":"Q2639638$CB99F2CF-7053-47C4-B57B-AA01C3A71F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a53f8b3e890c2663a1765dfdac7e8b3d9c5053d","datavalue":{"value":{"entity-type":"item","numeric-id":3948590,"id":"Q3948590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$C01DEEFE-721E-4468-A9B8-56E0A6BD59FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d6a6c22a928fa8dd018c35c3d3a9912036e4770","datavalue":{"value":{"entity-type":"item","numeric-id":1158752,"id":"Q1158752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$ED8F8E00-C1EC-418A-8EAC-3E0DBB1C06C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$7E51F6CA-AC6A-4362-8A97-71075F750870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10e0ec2d25eff3ed5afdd13928195836b0b8d94","datavalue":{"value":{"entity-type":"item","numeric-id":1094139,"id":"Q1094139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$E3784EE6-BE18-41AC-B8F1-3D07C85BC899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14259755a9136b7b26201f5111f10df5b52f768","datavalue":{"value":{"entity-type":"item","numeric-id":4109299,"id":"Q4109299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$CF006459-234F-4E07-9385-49DE73700D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d7e037c8a7e639db527a326c9a294060ad9104d","datavalue":{"value":{"entity-type":"item","numeric-id":3706504,"id":"Q3706504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$D81F36BB-369D-456E-9FE9-29C4E5DAED1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8194b210616a81519a29e9c197fab619e01f1c6","datavalue":{"value":{"entity-type":"item","numeric-id":1062759,"id":"Q1062759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$DB0D571B-FAA1-430B-A04C-78A823C10812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$720658A1-C3E2-4070-B6AD-FA7DF46E02A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fe382d78f0b00c10085a8c1b7559bfa56c77c82","datavalue":{"value":{"entity-type":"item","numeric-id":3036705,"id":"Q3036705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$9C8D7349-070C-4288-A9C3-A69CDF277A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"105101dba9c28fafb7b0ccbfd4eb7b9c22c79810","datavalue":{"value":{"entity-type":"item","numeric-id":3343440,"id":"Q3343440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$5145E9E0-E8D3-4C15-A15F-E28596DAF479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bf316364cd2756f2c4e6fc67ebc0fbec7faf6f2","datavalue":{"value":{"entity-type":"item","numeric-id":3763591,"id":"Q3763591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$811A3016-42EB-48DA-B4BB-935D9B0C9430","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7b81197e688b0c954761942c083edd543ee27821","datavalue":{"value":"https://doi.org/10.1016/0304-3975(90)90168-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q2639638$C9AC9B44-85CB-40F6-8F1A-DDFE91C0D533","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c910ac9923003f8f6790420cfe8911dbf6603920","datavalue":{"value":"W2071339347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2639638$F73C2D6A-36A5-4DA6-B49F-D21A96B69C05","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b46006266dfa27f78f67dac26590ca028f0108a7","datavalue":{"value":{"entity-type":"item","numeric-id":6482543,"id":"Q6482543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2639638$78B0FF96-6BFA-4D62-ADAB-2E4214DEC16B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92216762b5aa1ab5ca4eb2388959f1b7f2b75d6a","datavalue":{"value":{"entity-type":"item","numeric-id":1261484,"id":"Q1261484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2a1393709406bcaf6ec1e10c17f755651a248e3","datavalue":{"value":{"amount":"+0.8026363849639893","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":"Q2639638$EE02D0A6-ED79-42A7-B36B-C9527571FAE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b74e76aa2b7de55e84544485bd87173e9c611ed","datavalue":{"value":{"entity-type":"item","numeric-id":1094139,"id":"Q1094139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04606ec6dba0f8c63ac23b89e1918e3db1234b45","datavalue":{"value":{"amount":"+0.8006168603897095","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":"Q2639638$62FDE53F-6A0F-4788-BCEE-1B3D55FCAC1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92038af17771c1b65efc4e1f0022f3db88b419ef","datavalue":{"value":{"entity-type":"item","numeric-id":3782783,"id":"Q3782783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"489c2c707f232a21f35e5a5cf380442aaaed08bb","datavalue":{"value":{"amount":"+0.7917234897613525","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":"Q2639638$B96A8167-6DBF-4EAC-A6D1-B570280470BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b899bc52298956029314c43e05777ea9e0bd296","datavalue":{"value":{"entity-type":"item","numeric-id":1271619,"id":"Q1271619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e60de6d2159c26595daf86d9821eea3f278ee3a7","datavalue":{"value":{"amount":"+0.781398355960846","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":"Q2639638$62AA85F9-917B-4989-858C-E193BB53CB04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"878898f222338e38d5ed6038974e48ad176da3d7","datavalue":{"value":{"entity-type":"item","numeric-id":3343440,"id":"Q3343440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e87176f4fa9582d5790ce7cfd0ecb9ec1604b3fe","datavalue":{"value":{"amount":"+0.7765660285949707","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":"Q2639638$334F63DF-CFFC-4F3F-8DB8-83CD00008C00","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2639638","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2639638"}}}}}