{"entities":{"Q1108795":{"pageid":1119544,"ns":120,"title":"Item:Q1108795","lastrevid":66734928,"modified":"2026-04-12T12:30:58Z","type":"item","id":"Q1108795","labels":{"en":{"language":"en","value":"\\(\\Sigma_ 2SPACE(n)\\) is closed under complement"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068283"}},"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":"Q1108795$611BDF99-3729-4785-BCD9-91F9294A2A67","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"17cf10e6a74e0a2fa73cfa618a0469f9bb22c231","datavalue":{"value":{"text":"\\(\\Sigma_ 2SPACE(n)\\) is closed under complement","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108795$A96F3CD3-7874-4F36-A476-6EA067EE79AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b5d6a65441c2bffc03e60c8c2613206dede37eff","datavalue":{"value":"0654.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$0383DA45-BE19-4C8E-9846-6559A5057A16","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2b7a81cdb21b045540d7cb4c2cd7d36724575862","datavalue":{"value":"10.1016/0022-0000(87)90009-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$FFFDB797-0F63-469E-AF7C-2E066EE4B262","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108795$2C1C65FC-527F-40C4-AE3E-FD941D318621","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1108795$72AD1EA4-510F-43FD-8918-72B1931B1BF3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8f2179be2f9216f7941af0023a0e5c554cd9e37","datavalue":{"value":"A number of results on the collapsing of complexity hierarchies have been obtained in recent years. This paper is concerned with the \\(\\Sigma_ k\\)SPACE\\((n)\\)-hierarchy of languages accepted by linear space bounded alternating Turing machines. It is shown that the hierarchy collapses to \\(\\Sigma_ 2\\)SPACE\\((n)\\) by proving that \\(\\Sigma_ k\\)SPACE\\((n)\\supseteq \\Pi_ k\\)SPACE\\((n).\\)    However, since this paper was published, an improvement to this result has been obtained by Immerman, who has proved that \\(N\\)SPACE\\((n)=\\)co-\\(N\\)SPACE\\((n)\\). Since \\(\\Sigma_ 1\\)SPACE\\((n)=N\\)SPACE\\((n)\\) we see that the hierarchy actually collapses to \\(\\Sigma_ 1\\)SPACE\\((n)=\\Pi_ 1\\)SPACE\\((n)\\). Details of this improved result, which has quite a short proof, can be found in the article by \\textit{J. Hartmanis} [The collapsing hierarchies - the structural complexity column, Bull. EATCS 33, 26-39 (1987)].    Although the author proves a much weaker result, it is interesting to note the use of census functions, (which tell us how many strings are shorter than a given integer). This technique has been used to prove a number of interesting results in complexity theory recently.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108795$6251221E-BF5E-4178-83F4-99959CF4F87C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$12EAF074-0E26-4E27-AF82-824737F06CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$278559C1-A01A-4014-9372-A0CA4C0AD490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$0A3E2002-6607-443F-8D19-9F3215991882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$36F89264-D07C-4913-A24B-008B4B4326CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2df57f8172b95eda227241af691348aab5276d0d","datavalue":{"value":"4068283","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$209D45DD-6EF6-4CC5-A8E0-F8EE8BE63CCA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa73db42e95f803d5b40f20005e5c758a8ac8d32","datavalue":{"value":"collapsing of complexity hierarchies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108795$DE8C47F8-E7E5-4BD6-98B7-D883D865C8F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8d7c785826a7b700aa1fe69c478f8405b925566","datavalue":{"value":"alternating Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108795$8450630F-B90A-4EFC-B89C-22B1D92D2AC1","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":"Q1108795$8FED7C81-C286-404C-9509-E180B3770419","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3c7d99c1d201a8f21799ebd4349b145d4a14f180","datavalue":{"value":"https://doi.org/10.1016/0022-0000(87)90009-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108795$949B7310-A103-438A-8C7D-1948A840F940","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d0500d4f21d681a0c2ef2bffaacd5884a691f6c3","datavalue":{"value":"W1968785579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108795$2513FEFD-9CFC-40AB-A5F7-A7212FC588A9","rank":"normal"}],"P223":[{"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":"Q1108795$6F6B0A91-D788-46F9-AC6A-DCB2D665611B","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":"Q1108795$10179E16-8802-4D9A-87EC-2390FD0AC5D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6926e920f34ad943bbe1de8ce4a6882fa67a950c","datavalue":{"value":{"entity-type":"item","numeric-id":5596812,"id":"Q5596812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108795$D3F39CD9-28DF-42E2-88A1-BBB306F06BBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108795$59FC0A0F-E819-4756-AC58-EC4FEBDE5BC6","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":"Q1108795$4C76A796-D8B7-4C33-A350-A2E1D78D2760","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":"Q1108795$E9DCEBDC-71D3-4E7D-A6EF-E6C5BF862ED1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8852a05ed5f0e152b25fcc37bf64149d79bf927","datavalue":{"value":{"entity-type":"item","numeric-id":3142269,"id":"Q3142269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acad515392e64c20497dd84a53724b8876ea6c09","datavalue":{"value":{"amount":"+0.845953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$50422898-36E7-405F-9BBA-2B5279F67635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c02d442955fde10f0f04634a90f7138bc2d94ace","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5bb79cd2bd8aba6e026da557b6d81e4bc229bcd","datavalue":{"value":{"amount":"+0.8302759","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$72D7A76C-4337-415C-BB1D-25AFCFCA845C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0c3c9873af83d1eb41d9d179a6fc05aeca94866","datavalue":{"value":{"entity-type":"item","numeric-id":5223878,"id":"Q5223878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7745d9e79ce6f532dd808ca87310c722a28c3a1b","datavalue":{"value":{"amount":"+0.8266432","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$4B579A43-47FC-4DD0-8AF3-2E394D30C185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"556299e94ae68206a00bc8d1d5169a93bc5c4c88","datavalue":{"value":{"entity-type":"item","numeric-id":5932706,"id":"Q5932706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"893ebb9f73e1495370b4d48f0208e4793c8cd94e","datavalue":{"value":{"amount":"+0.82510215","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$9A6AB768-FD02-4D5C-8E63-4D972C1AB665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02df14ca61348e13cdd4f218c9e376117700cad4","datavalue":{"value":{"entity-type":"item","numeric-id":1111192,"id":"Q1111192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a490b974a59483b25554b1815637ad558de53f3a","datavalue":{"value":{"amount":"+0.8237326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$7FA20CC2-F497-4F31-A8A4-B19FFE8D157B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"331954397588bf4f932f5972a84c1c0ff64fb041","datavalue":{"value":{"entity-type":"item","numeric-id":4526943,"id":"Q4526943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39b697d2127a5cbae396fdc1b112960dcba672cb","datavalue":{"value":{"amount":"+0.82136714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$70D1B386-6222-4F0A-AA77-0DE775760B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1db51092579d41d117664470247495c6466c221","datavalue":{"value":{"entity-type":"item","numeric-id":4507875,"id":"Q4507875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39b697d2127a5cbae396fdc1b112960dcba672cb","datavalue":{"value":{"amount":"+0.82136714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$CE2A3896-16F8-4A8F-B5BA-16EE6E9BA37B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39072dd8477d23a5645880f2fe53492038501b75","datavalue":{"value":{"entity-type":"item","numeric-id":343224,"id":"Q343224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d0b22eb377232e07ea4fb28b23c01c0159569e4","datavalue":{"value":{"amount":"+0.8187116","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$D63FB06D-309C-44AF-8D94-C9955BE43884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c49bf7f9611a174ec4d4e3ad4d7c5c1d9f8dd35c","datavalue":{"value":{"entity-type":"item","numeric-id":2710261,"id":"Q2710261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0ddd260ed54abb8bf24f4086ddac1a1bf941f1e","datavalue":{"value":{"amount":"+0.8177599","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$F405267B-A24D-4DE9-AB62-D00065D52B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"678cee5a6c7fce165081bdf54e765ff77443e545","datavalue":{"value":{"entity-type":"item","numeric-id":1710636,"id":"Q1710636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ee0316d4a60b0d6144697e920370758cb3e2f07","datavalue":{"value":{"amount":"+0.8176111","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1108795$6FC7C006-FA56-4FCD-B91E-5C7F180A4B38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(\\Sigma 2SPACE(n)\\) is closed under complement","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(%5CSigma_2SPACE(n)%5C)_is_closed_under_complement"}}}}}