{"entities":{"Q1323339":{"pageid":1334089,"ns":120,"title":"Item:Q1323339","lastrevid":68461881,"modified":"2026-04-12T23:52:13Z","type":"item","id":"Q1323339","labels":{"en":{"language":"en","value":"Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 567303"}},"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":"Q1323339$6700A917-4B10-4717-ABC5-EA43470A485C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eea46b727e6cf1a289e671653ab57a015052ab6f","datavalue":{"value":{"text":"Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1323339$B2B0D337-197A-4EB2-A934-2EA29C519632","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f5b601308cd267633bfba35ec0fbe55cd81beac","datavalue":{"value":"0790.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323339$AD693237-32B3-46FF-BE3B-BB4366149EF2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93c5635ab334d182a39871085feb9e2bc77eb129","datavalue":{"value":"10.1007/BF01179374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323339$137968F9-6302-426A-A732-3AE516EC071C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"819eac7152d9513d670c824865ff9bc565f3954c","datavalue":{"value":{"entity-type":"item","numeric-id":706628,"id":"Q706628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$5C3DEAC1-C16B-4DC1-909E-884028B5411E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0a7cd892a07fa9f2ca0f5601abe829d603ae350d","datavalue":{"value":{"entity-type":"item","numeric-id":1102115,"id":"Q1102115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$B95C20D1-DB30-4D72-8522-E064DA1D8F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf44b91f73584e67838dcd7b9766693a96abac90","datavalue":{"value":{"entity-type":"item","numeric-id":557820,"id":"Q557820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$3D2A2E2A-8A7F-4AB4-8105-57B6FE72EEEF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$B1363C75-5C2C-4F8D-95E1-564354140813","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"84bd89f27c8cb1358368760527e3f52344795b6d","datavalue":{"value":{"time":"+1993-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":"Q1323339$DE85A980-58F6-4198-BB52-F7F448AE7ED4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a196ba3fa95bc60a12f158477cb0ccf7d423fa7c","datavalue":{"value":"\\textit{W. L. Ruzzo} [Tree-size bounded alternation, J. Comput. System Sci. 21, 218-235 (1980; Zbl 0445.68034)] introduced the notion of tree-size for alternating Turing machines (ATMs) and showed that it is a reasonable measure for classification of complexity classes. We establish that computations by tree-size and space simultaneously bounded ATMs roughly correspond to computations by time and space simultaneously bounded nondeterministic TMs (NTMs).   We also show that not every polynomial time bounded and sublinear space simultaneously bounded NTM can be simulated by any deterministic TM with a slightly inceased time bound and a slightly decreased space bound simultaneously.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323339$812778A2-8BE8-4115-B7CE-67BA8334EFFC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323339$82E721FA-71BD-49D7-BB48-50A9C537B238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323339$923133E5-1215-4ACA-91D9-65AEB53677C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323339$D6851A59-7BB6-4FDD-A650-002E3B8BC360","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0116b7093ad420e6270a8bf19f631d8a64f640ee","datavalue":{"value":"567303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323339$69063FF9-A7EE-4D40-B7CF-A1A91F9C8A5D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8d7c785826a7b700aa1fe69c478f8405b925566","datavalue":{"value":"alternating Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323339$23E6F46D-A983-4A5E-9092-A6D37912DA25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a66e8830d058aa1649bdd6bd0777d085c7282371","datavalue":{"value":"measure for classification of complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323339$87DFB6F2-B66A-4CC2-AC05-EC64D5D54AEC","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":"Q1323339$77B2DDAF-BDC3-4BB5-9169-04D5BCB24855","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"98d1f99209118318c5224afcbafe9d76aa7f8425","datavalue":{"value":{"entity-type":"item","numeric-id":1155607,"id":"Q1155607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$F05F0890-5991-45D3-8CF3-5B048CE32674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd3b3d2c381d7c8921981c21e9a61ebd6f00c5e8","datavalue":{"value":{"entity-type":"item","numeric-id":5570934,"id":"Q5570934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$72D0DC60-02F9-49B1-9F4A-8116B2992740","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":"Q1323339$66298E54-9FD0-4EF2-BD50-EC309BEFBDFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"529636f514f2cf19373a9a659e09022442fc1d94","datavalue":{"value":{"entity-type":"item","numeric-id":3334987,"id":"Q3334987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$80B6756C-6B18-467A-A20E-A444FA9C2F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1f0209c662a26c652a065cc280f3e4e1081f4d","datavalue":{"value":{"entity-type":"item","numeric-id":1822500,"id":"Q1822500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$CAA88B76-C78D-457C-811D-FEA0D72A6444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1afb9d404d75d0eab6933469a53953404b1ae1c1","datavalue":{"value":{"entity-type":"item","numeric-id":3761700,"id":"Q3761700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$8C4C60F4-5113-4199-8D89-909A960100F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6de891d5a6744d6bc5da3b977613039967f9d10","datavalue":{"value":{"entity-type":"item","numeric-id":4191603,"id":"Q4191603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$A32F94AC-127F-4057-B611-DFF23742BF56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$71C070BC-CF58-4DFC-BAE4-3ABED0440F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$0651C687-9FA0-47BF-A4DA-6E7F2E3DFCF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af525ea1fd445c05898a9991b61369483b6c7c29","datavalue":{"value":{"entity-type":"item","numeric-id":4142696,"id":"Q4142696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$A29A7CCA-4FDC-411E-9065-E1A262CB4C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b61370f634c5e1b6a25deeed5692d9eccdf317d","datavalue":{"value":{"entity-type":"item","numeric-id":4080742,"id":"Q4080742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323339$9B8955A5-AD32-40F8-B462-E208D0DB7856","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2e8ee7908f141d3f6aee3356e3bf3b21486246a8","datavalue":{"value":"https://doi.org/10.1007/bf01179374","type":"string"},"datatype":"url"},"type":"statement","id":"Q1323339$DCDB0A23-C101-460B-9945-FE80591307F9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"53abc5c344289bc08664cdda9bf077d1fb2c94fe","datavalue":{"value":"W2008300589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323339$B857A1CE-87B0-466E-8B1C-A86B6018F9B7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d12bf6cdbfd275ae616191a30ffccd24f41621a7","datavalue":{"value":{"entity-type":"item","numeric-id":3768407,"id":"Q3768407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6277a1edeb21853f8787c0c8b910441a03625b87","datavalue":{"value":{"amount":"+0.7695035934448242","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":"Q1323339$55897A10-C41F-4D79-884A-592B64DB7D9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8420ddce501c3ec6a72618903fa1af7f8be7d917","datavalue":{"value":{"entity-type":"item","numeric-id":809596,"id":"Q809596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02f716ceae32b3b2945de99efd0c12f8f86072cc","datavalue":{"value":{"amount":"+0.7693492770195007","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":"Q1323339$945552C9-5503-4C58-9B7C-B44480FA72D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c15fac2dd61ff691960b7289bb7d01e16836e060","datavalue":{"value":{"entity-type":"item","numeric-id":3761700,"id":"Q3761700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d15706de5d972d56d687e0dcbcf057ca29fbd5de","datavalue":{"value":{"amount":"+0.7595232725143433","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":"Q1323339$DC7B5534-AF8B-4767-BCBE-F18BFCF67501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1680e11224a81d36b38cd30ffafdf480aa80a21","datavalue":{"value":{"entity-type":"item","numeric-id":1102114,"id":"Q1102114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41690e5a92a3c299353a315370de67ded3450a51","datavalue":{"value":{"amount":"+0.7565712332725525","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":"Q1323339$54351BCC-AC49-450A-B15B-C17C9D279637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9818464012c455ff8ca87a8e9f590a37b9ea5d9","datavalue":{"value":{"entity-type":"item","numeric-id":3692869,"id":"Q3692869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91a3e3c264b20f572f34a7872fe7aed5b5bb6774","datavalue":{"value":{"amount":"+0.7545388340950012","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":"Q1323339$7E89FCA7-DE8A-4E85-A3B5-11FC986A4CBB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Relations_among_simultaneous_complexity_classes_of_nondeterministic_and_alternating_Turing_machines"}}}}}