{"entities":{"Q3477959":{"pageid":5499681,"ns":120,"title":"Item:Q3477959","lastrevid":49379227,"modified":"2026-01-07T01:42:21Z","type":"item","id":"Q3477959","labels":{"en":{"language":"en","value":"Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4147510"}},"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":"Q3477959$74BC6932-A68F-4F9B-A7E9-FB4744A944A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"22a03153669a469c17921ed9a4f5944e93bcc75c","datavalue":{"value":{"text":"Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3477959$FB2D6340-CBD8-482B-AAF9-E50D0241A957","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d436fa3b6a16702420c141bf5e8908a86b3e9243","datavalue":{"value":"0699.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$0F196CED-01BF-4692-9F5A-9E6B409C812D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"27f2e2905eb2136495b873053cb6db4ba215f27f","datavalue":{"value":"10.1145/79147.214070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$810A50B6-8DFE-4F22-8207-7E3F72434DC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8259050cd83ce3945f173c3e3c741cd5ddddec01","datavalue":{"value":{"entity-type":"item","numeric-id":169248,"id":"Q169248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3477959$F63E3740-CDA4-4CEF-8EFA-E7E9167E6017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aee4d3ee1c41565a5a83b17f16adc6668f5bedeb","datavalue":{"value":{"entity-type":"item","numeric-id":293302,"id":"Q293302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3477959$F0295FDC-895D-4097-8179-5E785C919205","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f12bfc80fe4a431c556e028f5134a217234a7cc4","datavalue":{"value":{"entity-type":"item","numeric-id":63915,"id":"Q63915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3477959$0641BCC3-46D9-4C38-BCD0-40128FD8A76F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q3477959$38E9CC89-F520-495D-AA64-75EB10C4AA0B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$16C56239-D908-42DA-A40D-FF672D87548F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$6B135645-CEC5-426F-94C1-BB92523C0A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$21AB6BFA-9F1C-414B-B98C-83EEB7CD0171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$DBE6FBC9-25FB-4E3E-A5E9-F37D7DF22D2E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"679e87c056ae0045386d24bb95cb48e7e45bdf56","datavalue":{"value":"4147510","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$C3ABF041-BA3A-4AB3-B759-7B468DA4944A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c86725be6c22fb548f2958ecde75687da57ab37b","datavalue":{"value":"computation by abstract devices","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$376857BD-EA8E-4AAA-8380-D38874B90539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"974222f1c86ce9641dcb0544ffe602914464de8d","datavalue":{"value":"bounded-action devices","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$27B5324E-C838-48C5-AFDF-12DF97F49EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$861369CD-2C5A-4489-96FC-992C225BD6EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02d4cb9949d1e0e1b52bcd330c1219b250da26ef","datavalue":{"value":"complexity measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$CFA2825B-0248-471B-A4FB-A8AF5737020E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce30576a1b29363978101d1cef3931ab8b02c92c","datavalue":{"value":"computations on discrete","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$DB81AF0A-3D4A-45C2-926F-921CA7E7EF22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6152e434a72882b8eef2cae2c1c4925f13f3144","datavalue":{"value":"structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$8E2270EB-9F53-4548-97FE-09B5CBF6B8E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0b9e816c430cd3e88ed419c55803a9d678ae625","datavalue":{"value":"trade-offs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$264ED2AF-3ABB-4FA1-BB73-FB1C0347006B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"798b443c473ce38e484a6b05e1b770274340eabb","datavalue":{"value":"combinatorial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$8C24EA52-8C90-45D4-804B-B2D85E9DB810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa64eae916ac50f9d0bdde79696d641a11ea4cba","datavalue":{"value":"counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$4B3595AB-1B77-4301-AA39-167F48C78836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4ef5a98087326b7b6ae23e1778e62561b3757de","datavalue":{"value":"problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$AB3976B5-3161-44C7-8008-CEB0A4AE1DD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$6C4F9A24-A591-4C5C-B0F7-71BBEED26893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$B48D7B1D-DC58-4D03-B820-046F45918FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$34C8A221-A143-4ECA-823A-629079BB0CBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477959$4F417953-94F4-4AEA-8181-84C029157360","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":"Q3477959$ECF5B50B-E09D-46CA-9177-FEAFEA43BA71","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b4cb6e9a108aad24c27e6ff56e57a5681445be54","datavalue":{"value":"https://doi.org/10.1145/79147.214070","type":"string"},"datatype":"url"},"type":"statement","id":"Q3477959$E19645B9-C94A-4A0E-A0EE-A9E8ADDEA687","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"05c2ac2e6e377245700f8ea9a84ff17bd73e4661","datavalue":{"value":"W2015314424","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477959$A47DED1A-3A2A-4AC7-A881-10A3098743D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82b86d9964b01e2a3a2ac0b2bde680fe46b545be","datavalue":{"value":{"entity-type":"item","numeric-id":4259986,"id":"Q4259986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e049025d1fda8c38fcc7e2946144e9b46291ba5","datavalue":{"value":{"amount":"+0.7895217537879944","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":"Q3477959$9D9CF6B2-50B0-42F0-8EFA-A2B94E64CD3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1620c871e292c3eae4e2aaa77463077be9149e03","datavalue":{"value":{"entity-type":"item","numeric-id":3455557,"id":"Q3455557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d68d57ca0084e6b91854387c4895eaaca5909dd","datavalue":{"value":{"amount":"+0.752258837223053","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":"Q3477959$45B90929-DD52-4753-8264-19EBB0DC3E41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7654215844f920cb0227722202d2dcc4aabc8329","datavalue":{"value":{"entity-type":"item","numeric-id":4608568,"id":"Q4608568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"759797af9b73c101ae41140bc253490fa59c3919","datavalue":{"value":{"amount":"+0.7515856027603149","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":"Q3477959$F5BC6127-6A34-46D6-A444-F194DEB0BF3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78220a8d1c4a2e714efc401332d6635ab94fabf3","datavalue":{"value":{"entity-type":"item","numeric-id":4302285,"id":"Q4302285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f82a0e2c60a4e8517c4b4df968b51ae8eec3455","datavalue":{"value":{"amount":"+0.7445075511932373","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":"Q3477959$8193FDDC-9004-4ED3-A8ED-6C66A2E29FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9a8b60570582b369c57eabe9fa68e8d7761de34","datavalue":{"value":{"entity-type":"item","numeric-id":4283241,"id":"Q4283241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b350f8896b78cc809ef6d547c554e68f560fb34b","datavalue":{"value":{"amount":"+0.7443056106567383","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":"Q3477959$163B1B05-CBE2-4E7A-A904-F20D57EB19C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3477959","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3477959"}}}}}