{"entities":{"Q809596":{"pageid":811444,"ns":120,"title":"Item:Q809596","lastrevid":64539009,"modified":"2026-04-11T20:34:01Z","type":"item","id":"Q809596","labels":{"en":{"language":"en","value":"Separation of deterministic, nondeterministic and alternating complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4213440"}},"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":"Q809596$15543FC2-7FF5-4F05-840D-3D0E63A872BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e0574b4580f5e8904b87d32abd5b4128c61b5f19","datavalue":{"value":{"text":"Separation of deterministic, nondeterministic and alternating complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809596$22146A9D-CDF2-4FB7-A236-A46BCD6F6A13","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26ab2ac72641f3eccd131d0797b975bb5f852b8a","datavalue":{"value":"0733.68029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809596$BFD916F0-415B-4C70-822A-95CA1045D71D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3947bc9f5b3821bb12546dcb02fad605f8720402","datavalue":{"value":"10.1016/0304-3975(91)90379-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809596$A05D3000-0F51-4C18-A6BC-F4CB5FF7F8CB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"20964b1ae5a6c963a65c801eb047c8d14e92ebcd","datavalue":{"value":{"entity-type":"item","numeric-id":809593,"id":"Q809593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$8CF8E096-AD9A-4B21-9371-596D34C64619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"683c75677bb04b2f3b10e7e51bfc2f72673c21f5","datavalue":{"value":{"entity-type":"item","numeric-id":809594,"id":"Q809594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$B654D26D-CAD6-40A3-8FC7-63B624DCBE37","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":"Q809596$1BC9D1DD-D032-433F-A589-742496AE8CD5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q809596$93AFB280-ACE2-4ABB-8AB1-AD873C6329A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"191ec8908cebe6f87ea08f43a3f015d685226148","datavalue":{"value":"The paper deals with some classical questions like whether nondeterminism is more powerful than determinism, or whether alternation is more powerful than nondeterminism. Modifying the lower bound techniques from \\textit{\\`P. \u010euri\u0161}, and \\textit{Z. Galil} [Math. Syst. Theory 17, 3-12 (1984; Zbl 0533.68047)] and \\textit{J. Hromkovi\u010d} [Theor. Comput. Sci. 67, 99-110 (1989; Zbl 0679.68085)] it is shown that alternating (nondeterministic) off-line Turing machines working in \\(TIME\\times SPACE=0(n \\log n)\\) accept a language which cannot be accepted by any nondeterministic (deterministic) off-line Turing machine working in \\(TIME\\times SPACE=0(n^ 2)\\). These results are extended also for off- line Turing machines with several heads on the input tape. Finally, some low hierarchies for TIME\\(\\times SPACE\\) deterministic (nondeterministic) complexity classes, and for TIME\\(\\times SPACE\\times PARALLELISM\\) alternating complexity classes are established.","type":"string"},"datatype":"string"},"type":"statement","id":"Q809596$1456212B-B4A2-4875-948D-F5A99A3E2333","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809596$D20E85F7-CDDB-4CBE-B5CC-D2D5A4CC4EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809596$A23EE33A-6ACD-499D-875C-67E3DBAA7510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809596$30DCBDDA-975C-4968-B7B1-0A5A163D1204","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"faeb9a7e15d233ec6ad4a173ba06fbcc557dd169","datavalue":{"value":"4213440","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809596$A8F1B85C-B0BA-4EC4-8F33-47660FC7099B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q809596$DBECDC4E-8BDE-477D-9933-33DBABFFC6B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8248a1dce4178bcbdf50d1b921f9653b658d3d1b","datavalue":{"value":"alternation","type":"string"},"datatype":"string"},"type":"statement","id":"Q809596$79977525-D19A-4349-BAA4-57D4C780CDFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q809596$3F8B02C5-B352-44FF-AFBC-39D6F0155180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q809596$3D1F4E27-EB69-4F7C-A53C-A8AF5965543E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$8EF68EE2-1FC0-42A3-AF0B-74A87BB17F6B","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":"Q809596$E37F4288-8955-4CF2-A0D5-DA5046A5FE63","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"44c3aa1f109b7982536744b5c71615445bc3e192","datavalue":{"value":{"entity-type":"item","numeric-id":3316594,"id":"Q3316594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$37D611EB-7F07-42A2-81A9-77B5BB337E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654da187d4372cd016f5d177803660f8d9e36d8f","datavalue":{"value":{"entity-type":"item","numeric-id":1836312,"id":"Q1836312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$7D891D6C-BBFC-4757-A7AC-ED730034D29B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2125d23285b42025489c119f78f60c43fe39833e","datavalue":{"value":{"entity-type":"item","numeric-id":1068537,"id":"Q1068537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$103CA83C-85A1-4B9B-A763-62E1158C6CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36600beb8620ad90203a7922dafc15a7d1747a1a","datavalue":{"value":{"entity-type":"item","numeric-id":3725549,"id":"Q3725549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$E2087B92-CCC4-45F8-93ED-E67F6B52D9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a5d3a3f555b2cc70bb79f9e6a58a5a42a76d684","datavalue":{"value":{"entity-type":"item","numeric-id":3048298,"id":"Q3048298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$B04B8618-2AE2-44F3-9353-8C192C98847D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8b46364e633fd6e8829251e5ac30abfc60735d8","datavalue":{"value":{"entity-type":"item","numeric-id":4148951,"id":"Q4148951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809596$D44CCBA9-9C28-46C2-A8C5-474B10462F81","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"42711e26cf4bde9488e4a22b9bdfeeba24b22058","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90379-g","type":"string"},"datatype":"url"},"type":"statement","id":"Q809596$7E6A44B1-BD38-45AB-8103-FBBA977AAFD2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f1231156815a7fd8dee51c8a75d573404f2973d6","datavalue":{"value":"W1981385397","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809596$5F6CF8CF-7979-429F-8ADD-3A1401B76EA2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"383224785ba73532254677b4330d754b1fd5ef39","datavalue":{"value":{"entity-type":"item","numeric-id":4218136,"id":"Q4218136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db2db193cede0aa935e789c4fe102bd345f2b220","datavalue":{"value":{"amount":"+0.8456009030342102","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":"Q809596$19F2ACA4-2C65-45F9-8B8D-372E2FF50A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b1ebc1a6d982b40884609b9ae130ceb396c6b1a","datavalue":{"value":{"entity-type":"item","numeric-id":3334987,"id":"Q3334987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"117d749e173ea8519b7708d4b3fde760142ca62c","datavalue":{"value":{"amount":"+0.8289291858673096","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":"Q809596$E114DA46-466D-4E13-87BD-60433B558BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d6be0a755e2b37fdf855f4c1e99b66ea5360b81","datavalue":{"value":{"entity-type":"item","numeric-id":4717057,"id":"Q4717057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cc2264d4659d8c9eaa2d76d0b648ebfb6739112","datavalue":{"value":{"amount":"+0.7977463006973267","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":"Q809596$E7DF983C-449E-429F-9CE4-AE9101DAA074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc83ad55f47d32fd544c12c26f56900c074d680c","datavalue":{"value":{"entity-type":"item","numeric-id":4818851,"id":"Q4818851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b16480e9f0cebd605d6034a462c07e4a7850bd3f","datavalue":{"value":{"amount":"+0.7972999811172485","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":"Q809596$81FB330C-80A6-43E1-BAAB-8DBD5E097611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a6b968885497755d64a8a67a1ce4520f12d94cd","datavalue":{"value":{"entity-type":"item","numeric-id":1323339,"id":"Q1323339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63238fa0563e0d97252345d20a2bef0c83ad43a6","datavalue":{"value":{"amount":"+0.7971110939979553","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":"Q809596$D74D4826-00C9-4B52-81E8-C440AA6947DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Separation of deterministic, nondeterministic and alternating complexity classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Separation_of_deterministic,_nondeterministic_and_alternating_complexity_classes"}}}}}