{"entities":{"Q1114402":{"pageid":1125151,"ns":120,"title":"Item:Q1114402","lastrevid":49238329,"modified":"2026-01-06T20:11:25Z","type":"item","id":"Q1114402","labels":{"en":{"language":"en","value":"On a complexity hierarchy between L and NL"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4082977"}},"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":"Q1114402$6E03DFD9-2D70-41D0-A481-1FC77C23FA17","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"acf51ba72991e8ad7d57b5bb72ba207a6fdda1d3","datavalue":{"value":{"text":"On a complexity hierarchy between L and NL","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114402$6BCE159F-8D0F-44DC-BFEB-C2C0AD7C0D7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2b5837a415a80db8ea092c552422fe55743ab68","datavalue":{"value":"0662.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114402$8A453BB8-AA55-4E64-80D2-733674A8E71D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"24ba86565ee68ec095ee3b8556ac7486237ef0c7","datavalue":{"value":"10.1016/0020-0190(88)90057-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114402$E64B965E-538A-4DB4-872C-A423A077E3FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"77ffddd258152338da5cc01c34750ffd5ad04d31","datavalue":{"value":{"entity-type":"item","numeric-id":809607,"id":"Q809607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114402$EC6541C2-3821-4CC2-88EE-E935FC1412A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f11d29d2cbdb03c4d5ff90d92cbc2f1d658ba97d","datavalue":{"value":{"entity-type":"item","numeric-id":391197,"id":"Q391197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114402$B5675AC8-6332-4B3C-8D3E-7F83AFF9A81E","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":"Q1114402$D370C700-2AE1-46D3-8C81-48EB23A9A1E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1114402$7DA1A3E3-1C53-4386-878D-EC4ADE3EA1C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0c3e3638571e8c7d6bdcc70784f5a52aa8c4c3fb","datavalue":{"value":"This paper attempts to explain the complexity of the unary 0-1 knapsack problem which lies between L and NL. We introduce a new complexity class of languages log-space reducible to languages accepted by the family of one-way one-turn nondeterministic auxiliary counter machines whose auxiliary worktapes are O(\\(\\sqrt{\\log n})\\) bounded. This complexity class is denoted by \\(LOG(1-1-NAuxCM(\\sqrt{\\log n})).\\) We show that the modified unary knapsack problem with bandwidth \\(2^{O(\\sqrt{\\log n})}\\) is log- space complete for \\(LOG(1-1-NAuxCM(\\sqrt{\\log n})).\\) By varying the space bound on the auxiliary worktape, we obtain a hierarchy of complexity classes between L and NL.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114402$69D4FEFE-C674-48D9-A956-9542ECE73AFE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114402$F6842033-331F-425B-9875-86DBAE9FCC9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114402$1689CC89-5E92-4448-B52C-3E30C3F744D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0706208fb83a45bab9274a8c487fce2a6b5dbcd6","datavalue":{"value":"4082977","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114402$C5DE2C3A-C638-42F8-BE15-289CC6A5C85D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee50863332ef94524d130e789a7a00d20a0693b4","datavalue":{"value":"one-way nondeterministic counter machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114402$986051DF-9EEA-435A-A0F2-06A07EC4DE35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75ee5716e7913ae6486b66c18df6b7f17e93656b","datavalue":{"value":"complexity class of languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114402$7F5DCAE6-0549-4460-8C10-F9451CE04D0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f539d5beb768fe8f0dde9bb922df254e086f9f0d","datavalue":{"value":"unary knapsack","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114402$44B7A23F-CBF6-47C1-A5F8-28FF14C5E4CD","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":"Q1114402$E808EECE-1683-4FED-8D01-8E3589C4A377","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"977a2efb7b98762ab75bafd40e360859723fd0f6","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90057-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114402$A8063853-631A-4B44-91A9-E577B77DF3E0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"efa7db7d014fc2679d1a055538ecc90ab748dd05","datavalue":{"value":"W2018791466","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114402$E5E84488-FE27-4019-9C27-F59450143A91","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114402$3AB2F7C3-20F6-4A99-96F3-3A54C1707241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4cda73737862ae25acf95e82a813fd5a18542be","datavalue":{"value":{"entity-type":"item","numeric-id":5525346,"id":"Q5525346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114402$3C3F9329-7D8D-4CE0-BCA6-59F86EFB03ED","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":"Q1114402$40968F5C-D782-4C87-AE0B-F3AE6C531760","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":"Q1114402$CC276220-1D45-4161-B005-10CE9DC92F03","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed45fb2bcb99c79e9878248f8e998a6955aa9d67","datavalue":{"value":{"entity-type":"item","numeric-id":673615,"id":"Q673615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12fa54c2006cd206b673cf6ad4bf6ac1b8f8fff9","datavalue":{"value":{"amount":"+0.772523820400238","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":"Q1114402$723F7F56-3BF9-4EF1-BC90-0A4DEDD6E31C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"154b89faec943f9298778c3c83d98374bbeedffe","datavalue":{"value":{"entity-type":"item","numeric-id":4281504,"id":"Q4281504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12fa54c2006cd206b673cf6ad4bf6ac1b8f8fff9","datavalue":{"value":{"amount":"+0.772523820400238","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":"Q1114402$7FCC72EA-E67B-44D7-8567-E35141FB26CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90d99242d0f11833b629678665e5bb79df6af538","datavalue":{"value":{"entity-type":"item","numeric-id":1401238,"id":"Q1401238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ab41d786a217f9e01032434968c418917db01f6","datavalue":{"value":{"amount":"+0.75064617395401","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":"Q1114402$49D6ABC8-77F3-4109-9D68-EAF87B9F63CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78a3f4ac3780d9faf2688a0fc6afef75bb83fd28","datavalue":{"value":{"entity-type":"item","numeric-id":4785461,"id":"Q4785461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edf72a3ecd892569441c53c77e8289053ea2c0a4","datavalue":{"value":{"amount":"+0.7365776300430298","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":"Q1114402$06BA776C-DBBE-4A78-98C1-7603C668539F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6f2049529fd0fe05f677273f563d14bda792ad1","datavalue":{"value":{"entity-type":"item","numeric-id":4943854,"id":"Q4943854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edf72a3ecd892569441c53c77e8289053ea2c0a4","datavalue":{"value":{"amount":"+0.7365776300430298","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":"Q1114402$898B090C-E4F1-47F7-9897-E953214A972B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114402","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1114402"}}}}}