{"entities":{"Q1118407":{"pageid":1129156,"ns":120,"title":"Item:Q1118407","lastrevid":49262812,"modified":"2026-01-06T21:06:43Z","type":"item","id":"Q1118407","labels":{"en":{"language":"en","value":"The logarithmic alternation hierarchy collapses: \\(A\\Sigma _ 2^{{\\mathcal L}}=A\\Pi_ 2^{{\\mathcal L}}\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4094817"}},"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":"Q1118407$ADD4F797-5C94-49AC-9FAB-91796C031323","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b42f264563dfc3b0ab2e501f3f333aeeee342597","datavalue":{"value":{"text":"The logarithmic alternation hierarchy collapses: \\(A\\Sigma _ 2^{{\\mathcal L}}=A\\Pi_ 2^{{\\mathcal L}}\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1118407$C749C557-E5FB-4887-B01F-D61233A7D03E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"465fce57adff6b738297426b3363a3281e7d4174","datavalue":{"value":"0668.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118407$F8D30A21-45B8-4A4D-9FA4-6D806439C82D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8d403481344a5979105a50043052b23a2efd0ce4","datavalue":{"value":"10.1016/0890-5401(89)90012-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118407$31957C3D-AEFE-442F-973B-923381F15F2D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a27874dd27bebc42c1492fa6e86ea62a823b910b","datavalue":{"value":{"entity-type":"item","numeric-id":672321,"id":"Q672321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$EA79D5AC-F0CB-4BDA-9F6A-5FDC474F4853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c722fd6566e2fc27d92e4b5c47b98a548fdf4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1094138,"id":"Q1094138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$2C5AA23D-FC71-4153-B338-641F48B883B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"506f0ce7bc6c0b7f9b3af2721fc1bde2eff5db2d","datavalue":{"value":{"entity-type":"item","numeric-id":1163379,"id":"Q1163379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$86C9482A-0190-4396-85FB-B59780DB2884","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$9AB05910-8D42-4B21-871C-836F15AA1D60","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":"Q1118407$EF84EF52-B729-4D4A-B284-043B693C04BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cbb275512735b80286d2f6a961d7353044dc2a24","datavalue":{"value":"It is shown that the second level of the logarithmic space hierarchy is closed under complementation, i.e., this hierarchy ``collapses'' to its second level. The result is proved by considering the Hausdorff closure of NL, and also the Boolean NL and NP hierarchy.    A more recent result by Immerman shows that the results reported in the present paper are not the strongest possible ones: Actually, NL is closed under complementation, i.e. the logarithmic alternation hierarchy collapses to its first level.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118407$B0309724-ACEA-4FF6-B77C-301EA0E0D031","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118407$169A47D3-EB86-4235-B961-F1551116F193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118407$1A90BCA5-2696-4B29-9FE1-3EACD31996A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118407$64C474DC-8FA2-4352-A523-32FD4574CCDD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"04e79e9fc793e3f798e08730a266a45df159a81f","datavalue":{"value":"4094817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118407$5F3C6201-C361-4658-A60F-26D5FBB85F77","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0eb41bef4f95010ffe7ecae9642a3a5dca3e09e6","datavalue":{"value":"logspace","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118407$41183A07-5050-464F-B3BE-8E0553129A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118407$E6FEC65F-734D-4BBB-83E3-D23EC2866DE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b4251d5631b56e90b5680163204fbd1a6ac93d","datavalue":{"value":"logarithmic space hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118407$3C50EE49-4ED0-4F44-8AD4-BEF74F1DFEB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"045158f0cd5d70468e5b59b989c58725b87a1563","datavalue":{"value":"NL","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118407$CA21C1B0-049B-46F4-ACE2-6E6668AD47D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8248a1dce4178bcbdf50d1b921f9653b658d3d1b","datavalue":{"value":"alternation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118407$CC15BC73-C5AD-4B8C-9316-CC1035CA55FB","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":"Q1118407$E8653301-2A5E-45D4-9F5A-CCAE311B69A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6274d395307f5befdae195277e2c51ebcf382fb4","datavalue":{"value":"https://doi.org/10.1016/0890-5401(89)90012-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1118407$1FAABF5E-D4A8-43EA-BAB3-F980D5C08A54","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2c790b810027d56775b358e2e31f74b47d3a52d2","datavalue":{"value":"W1997449252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118407$61E20CA9-3B32-40DA-A8C3-17AEA4ADB056","rank":"normal"}],"P223":[{"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":"Q1118407$176C054B-7296-4249-834E-E19ED7D6ED91","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":"Q1118407$6C8EF5D5-AFFE-4678-AEE3-B2383D8E4130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$AB2D8AFF-B947-4310-BA46-DA842A0DE658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd898582b3042cd9f98f55a99a55f26af0712fb","datavalue":{"value":{"entity-type":"item","numeric-id":4128417,"id":"Q4128417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$4782AF6F-5FA6-493F-A798-E1BDF86318E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$EE129E26-0EEF-494F-B7B1-B4F3D639A397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4618ed8d781b5887246f050c706fe66b398bd574","datavalue":{"value":{"entity-type":"item","numeric-id":3787475,"id":"Q3787475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$C3F9AA0E-116C-46A2-B196-784BE74D385C","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":"Q1118407$94313E10-2B1A-4653-8211-44A8727C58BA","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":"Q1118407$F6B1CFC3-A83A-457C-8EEC-79D8D8063815","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":"Q1118407$F5FC5E92-5F20-4698-A670-3EBCED0D109D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e18e5b33c42a975e0ea884a76c83c33d5e131617","datavalue":{"value":{"entity-type":"item","numeric-id":4725752,"id":"Q4725752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$5A62F40A-190A-4D30-B46A-E0B000ADC720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97eb49eec0b8f24d85d3dbef951186a76c1d39bd","datavalue":{"value":{"entity-type":"item","numeric-id":3766852,"id":"Q3766852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$A772926A-7FD5-45ED-9F20-0D6146BDAD36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800321fe9f6efe205a2eb283e0da5841a2b5eaad","datavalue":{"value":{"entity-type":"item","numeric-id":1061485,"id":"Q1061485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$E04509FC-D70C-405D-998D-705C5A6575B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40f5134eaa4297cc6ad992072c543aec6eb8f762","datavalue":{"value":{"entity-type":"item","numeric-id":4723306,"id":"Q4723306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$4FC73E2D-BC44-455E-920A-3E5526EDA769","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":"Q1118407$A6DF19FC-DEDC-4EFF-A022-5CE0E5614DDC","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":"Q1118407$6D5E66C6-70D6-425B-B999-300D4F2A8135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad5d43e58020977f5420eb7b8ec7095ce17d3134","datavalue":{"value":{"entity-type":"item","numeric-id":3793733,"id":"Q3793733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$38335BC9-68E5-47E4-B392-ED4E0A5B6071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$68DCAA42-65E7-4C09-8F47-8AF4F5421802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67ed33de7061de4d7d8391bea59c71fda756b59c","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$FBA11FD3-6348-44F7-BBCE-3F3357733AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0f47102b22ffb26cb24eeae198f4c2bd495bdbb","datavalue":{"value":{"entity-type":"item","numeric-id":1108795,"id":"Q1108795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$2278572F-7BCD-4808-B8EC-AFB5471AFBD5","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":"Q1118407$BA37310C-B72F-4E9F-AA3C-69D0DD1CA4D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e1c59b20b978e8e0de5a32fdeb6c212dbd6e1a","datavalue":{"value":{"entity-type":"item","numeric-id":1090455,"id":"Q1090455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118407$5CAAD56C-DCB8-438E-80D8-5B1313DF73C1","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":"Q1118407$18EC9FB1-937A-4945-AE36-4C12E4E7E7CD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66f3a035ae2b8ebaa39df2aca6969f6194641e35","datavalue":{"value":{"entity-type":"item","numeric-id":3766852,"id":"Q3766852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ce722e72c065ab1b3cab90abefd6d57f47d0644","datavalue":{"value":{"amount":"+0.894628643989563","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":"Q1118407$0CE7083F-1F27-43A0-AC52-B84B75A4F785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c9c34a3370ceb1706e75c56a745dee57266e678","datavalue":{"value":{"entity-type":"item","numeric-id":3995641,"id":"Q3995641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f233e14747fc2b90b537943b771a952f50733e25","datavalue":{"value":{"amount":"+0.8624259829521179","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":"Q1118407$E6962395-0DEB-44BA-A47A-F58336AAC192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"460db9665a1b64858fc7bffd171fdb6a8bf14e8c","datavalue":{"value":{"entity-type":"item","numeric-id":1108795,"id":"Q1108795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19a3dbff0e107f878626d0617708d1a5babd2784","datavalue":{"value":{"amount":"+0.8601559400558472","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":"Q1118407$98A8CB2C-10C6-4832-A487-FD81D9E7FB81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e88174857e11c73fba0dbcc04bdfa4680f61b3fe","datavalue":{"value":{"entity-type":"item","numeric-id":1825656,"id":"Q1825656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"639ea7f3ba0b61257b92a48c0f82651271b7149b","datavalue":{"value":{"amount":"+0.8432217836380005","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":"Q1118407$F9454130-C4DD-4082-B213-CD9B879CEFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dba0a3c53740ddf35fe53dfbe0ca4b018fe4a9f","datavalue":{"value":{"entity-type":"item","numeric-id":4365021,"id":"Q4365021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97b4225b53cb80ecb2b8600cc4abbbf145d3a6ad","datavalue":{"value":{"amount":"+0.8333067297935486","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":"Q1118407$68C608D3-95C8-4AC5-BE03-44917CEB732F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1118407","badges":[]}}}}}