{"entities":{"Q688445":{"pageid":690294,"ns":120,"title":"Item:Q688445","lastrevid":47204251,"modified":"2026-01-01T00:10:14Z","type":"item","id":"Q688445","labels":{"en":{"language":"en","value":"Linear speed-up does not hold on Turing machines with tree storages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 444833"}},"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":"Q688445$F16A0262-7439-4372-A5D3-8AB41C746D78","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9baf9b8a9e28b2ad1ff2df00d3c7243b20449763","datavalue":{"value":{"text":"Linear speed-up does not hold on Turing machines with tree storages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688445$F09A4540-D431-48D0-9C06-1DBFCED81B6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0fcb759c3f117a718031efac0f5a08dc88a57f69","datavalue":{"value":"0788.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688445$A6BCA0F6-EC6E-41D2-BEB7-E7120DF4F469","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"29f01c902251f338e3e4105967f66a148d116965","datavalue":{"value":"10.1016/0020-0190(93)90078-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688445$B6A8EA48-ECDB-44AB-BA59-8E45172E9856","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9973e2447e160626aae94a4573883ce5cc94efb","datavalue":{"value":{"entity-type":"item","numeric-id":685435,"id":"Q685435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$A807D2E6-36A2-4657-BE14-4F6446A1710D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$BCF78878-20E0-4743-A71D-C61870639EFF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"92112234a474f78049341bfb55637019f67e54ac","datavalue":{"value":{"time":"+1993-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688445$B6E77A63-7D32-4253-8BC9-C8E4B9416457","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1445e9e948968206dad83bea72fc3502e84019c8","datavalue":{"value":"One of the basic results in computational complexity is the linear speed- up theorem by \\textit{J. Hartmanis} and \\textit{R. E. Stearns} [Trans. AMS 117, 285-306 (1965; Zbl 0131.154)]: On Turing machines accessing tapes as storage constant factors in the computation time are not significant, since any computation can be increased in speed by any constant factor.   In this paper Turing machines accessing storage devices with a tree-like structure are studied. It is shown that on tree storage machines constant factors are significant. For any \\(k\\), power of two, there is a modification of the Storage-Retrieval Problem which can be solved in time \\(kn\\) on a machine with two binary tree storages. On the other hand, any binary tree storage machine (even if it is equipped with more storages) requires time \\(kn-O(n/ \\log n)\\) to solve this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$252A1918-3FE9-4FAB-819B-A1D1A4EEFA52","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688445$B866FD15-B6ED-4FE0-A07F-834A16C34BBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688445$A8B9D3A8-0AB0-46EC-83C1-D7830DEE3269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688445$9BFE712F-044F-424A-95AA-EF42D3468163","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c4a0af2c9ac3d18fba97b5448aa084b49b6c2809","datavalue":{"value":"444833","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688445$DC5920EF-1D6F-4A98-99A5-8E0712272E15","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$25E1B97B-43C0-48E5-B88B-D7D16B9BF76C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"167e6609e044ac60f0193dfc741a4e87f38fe9fe","datavalue":{"value":"online simulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$8E678D60-A19F-4B8D-A9EC-17BB96290D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$4255DE33-7B02-4B1F-A43F-6A73A72AEEB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$9BF82620-4E1E-4B5B-A4D8-6D195BC2A2AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7849cf4967868e1682e85fd08af647be01332b1a","datavalue":{"value":"speed-up","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$768D0AC8-B9D8-40BB-812B-D86D76844D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$3DB78BFB-E608-430C-B666-CC3FFCF8DE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38631f0c0538fcf62401482dd19bd25e393fde9e","datavalue":{"value":"tree storage","type":"string"},"datatype":"string"},"type":"statement","id":"Q688445$EEEDAA49-498B-4471-8EE3-AF0C95AB0B86","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":"Q688445$3E60589E-8980-4122-98BE-775889AF3F7A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"de1226518f6234cb515843a172beeb3ee5f693f0","datavalue":{"value":{"entity-type":"item","numeric-id":5582354,"id":"Q5582354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$B9A0BAF4-6B82-445D-B1A1-6738638938FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e67c0bd6517a1b1f5370c72313fcafdfca0c7438","datavalue":{"value":{"entity-type":"item","numeric-id":3359748,"id":"Q3359748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$48ADEB22-7B68-4275-B859-5494BA696470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ed8c1c9b5cf85c3067f46e271b605235d5e997","datavalue":{"value":{"entity-type":"item","numeric-id":5339741,"id":"Q5339741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$16DCEA27-2F6B-4A31-802E-1C258F56CAF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2f2c1c6a244ec91c908090027016ec71e3411b2","datavalue":{"value":{"entity-type":"item","numeric-id":5518364,"id":"Q5518364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$CBC1A692-81B0-4462-B210-BAB385F767CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"accb3332cc2099d0b2a0ffd4c035aeea89f6722c","datavalue":{"value":{"entity-type":"item","numeric-id":4385509,"id":"Q4385509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$00A5EAEB-17DC-405E-B184-45CB1E8DA4BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55441fcfcec00635e4ea4f80f64402f439cd915a","datavalue":{"value":{"entity-type":"item","numeric-id":3040491,"id":"Q3040491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$EE6371E1-E14C-4812-A914-8425BF3DFA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cca9f86bd8f5367b8ad246c0f4d0890c88697437","datavalue":{"value":{"entity-type":"item","numeric-id":795505,"id":"Q795505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$B649AAF4-35B2-4F1D-867D-3A35961EEDFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"575767c202367822fb49b9fb9613b181c9e61dbf","datavalue":{"value":{"entity-type":"item","numeric-id":4015977,"id":"Q4015977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$1A43A681-DC1F-435F-9E3A-29978262322F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d576f2c4009976628e3d23d58af4decef38eafd","datavalue":{"value":{"entity-type":"item","numeric-id":1152954,"id":"Q1152954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$286F3B60-F237-4B92-9046-A48880163AF1","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":"Q688445$72635166-272B-4EAF-A58C-9D21033F2714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8b0effc062fd0b5749cb5cf7f342c7ece2cafe1","datavalue":{"value":{"entity-type":"item","numeric-id":1166931,"id":"Q1166931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$FF7FEE3E-4711-4F48-8497-EA755146ACAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"135117a7894f62f0fd84fa8ca4cf2176d8e3df26","datavalue":{"value":{"entity-type":"item","numeric-id":3993545,"id":"Q3993545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$CA25A61F-1874-43AC-8467-E97D57F3EC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b9731ee57d5c7bf2962ad3ab321d70650581272","datavalue":{"value":{"entity-type":"item","numeric-id":1193594,"id":"Q1193594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$E6A0EE7D-9D65-49E7-828C-6F5345C5BAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dab107e270539e08732f99ceb4b022a863c9a7e2","datavalue":{"value":{"entity-type":"item","numeric-id":3707408,"id":"Q3707408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688445$671D955F-0CFE-4412-BA4E-578F141FF548","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"510f9b7328cd0a89ffbd5995f19d092434fd7acd","datavalue":{"value":{"entity-type":"item","numeric-id":5414602,"id":"Q5414602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a63ef524c100b68462ae63d1a669e537f234faa","datavalue":{"value":{"amount":"+0.7636297941207886","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":"Q688445$A49A4236-BA10-4139-B754-F5CB72A9A564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7875bb14ac6c3e88982e22a33dc971dade4534d2","datavalue":{"value":{"entity-type":"item","numeric-id":688718,"id":"Q688718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a28f0d4ef3f0dad172908a040f13fe584541013","datavalue":{"value":{"amount":"+0.755928635597229","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":"Q688445$17DBDD09-8DAA-4EBB-9011-DDC965148EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"895c9ff3c57dd4bc7db63a9c50be2f82ec38a48d","datavalue":{"value":{"entity-type":"item","numeric-id":3805901,"id":"Q3805901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9416ce4b5aece58c8ca8a4d5303734fc5d24468c","datavalue":{"value":{"amount":"+0.7524080276489258","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":"Q688445$755D283F-3FBE-474C-AFDC-76AE91F113B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87d92ee77534778a34b2f339234a6cbb3bd80d14","datavalue":{"value":{"entity-type":"item","numeric-id":3359748,"id":"Q3359748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2692f979585e0538b83f4c8e78025f9c799eac29","datavalue":{"value":{"amount":"+0.7375556826591492","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":"Q688445$734606CE-C3E1-4A49-9C88-AE60F22ED073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26e0f160643500d0c53f11a147cab3caa7c56492","datavalue":{"value":{"entity-type":"item","numeric-id":3569016,"id":"Q3569016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7d9ba86235be8c6e7f5f36680ae5d9374f251e7","datavalue":{"value":{"amount":"+0.7270953059196472","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":"Q688445$6D295473-7D7F-489E-9629-61387CDAB53A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:688445","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:688445"}}}}}