{"entities":{"Q1208403":{"pageid":1219152,"ns":120,"title":"Item:Q1208403","lastrevid":67060095,"modified":"2026-04-12T14:41:47Z","type":"item","id":"Q1208403","labels":{"en":{"language":"en","value":"A very hard log-space counting class"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166418"}},"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":"Q1208403$64087080-6E0B-4190-8F20-FABEE4216D6C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"24f30c9e68b77401a9341c6ebfe203d166c1852a","datavalue":{"value":{"text":"A very hard log-space counting class","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208403$2D078DF2-E316-461F-8827-4A7F08000BA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2226e28cf7734314fb605470465d0fb886e23dd6","datavalue":{"value":"0813.68098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208403$F6370ADE-C7EA-4136-8396-4A2FAD5E748C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9edcec1788add2b7f792d17755827e15f34ad7d7","datavalue":{"value":"10.1016/0304-3975(93)90252-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208403$54F19538-DE38-4CB4-B207-102C1D4B2D4D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2ac9177c8ed8f1d0d6bfb2cfb40afb0f4276bba","datavalue":{"value":{"entity-type":"item","numeric-id":172543,"id":"Q172543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$1048BD83-0F73-47D3-9C2E-6D212135252C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a27874dd27bebc42c1492fa6e86ea62a823b910b","datavalue":{"value":{"entity-type":"item","numeric-id":672321,"id":"Q672321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$233A8E11-E5AC-48B3-AE01-B4D017777B9C","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":"Q1208403$3AAF3D1B-2A56-4C63-8B62-0F26494FEA51","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208403$F348E0E5-3989-4C10-9F88-F6435C208D57","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de2d2f1e683c6b1ca3e6346c35e53105e85d0a27","datavalue":{"value":"The authors define three logarithmic space analogs to previously investigated polynomial time function classes, namely \\(\\#L\\), opt-\\(L\\), and span-\\(L\\). They give various natural complete problems for all of these classes, thus showing that they should be considered to be natural function classes.   All of these classes are classified by upper and lower bounds: span-\\(L\\) is contained in \\(\\#P\\), and \\(P^{\\text{span}-L} = P^{\\#P}\\); \\(FL^{NL}\\) is contained in opt-\\(L\\) and opt-\\(L\\) is contained in \\(NC^ 2\\); \\(FL\\) is contained in \\(\\#L\\), and \\(\\#L\\) is contained is \\(NC^ 2\\).   Evidence is given that opt-\\(L\\) is not contained in \\(\\#L\\), because then nondeterministic logarithmic space computations could be made unambiguous, i.e. \\(NL = UL\\). Further, the authors give strong arguments to believe that neither \\(\\text{span-}L \\subseteq \\#L\\), nor \\(\\text{span-}L \\subseteq \\text{opt-}L\\).   This paper (which first appeared as a conference contribution on the 1990 IEEE Structure in Complexity Theory Conference) was a starting point for a lot of investigations concerning (functional) log-space counting classes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208403$E7734CB1-71B6-4A02-B86E-FEAB2F85D93D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b19fd7af7871663e4a0bc740ce9bce2772dc88a6","datavalue":{"value":{"entity-type":"item","numeric-id":263828,"id":"Q263828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$6AECD06A-4316-444D-BBA0-8C1D9E087A47","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208403$954D0562-379A-46E9-A46C-7FAEAC263A64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e393dcf5dc12a6fe4360550683682c1324f049ec","datavalue":{"value":"166418","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208403$DE1C0F58-907E-4B2A-A44C-8A9C6D944050","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f18bc21d823222e01f5a88a6fb3d1663d7daa25","datavalue":{"value":"logarithmic space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208403$A5B970CE-9CA4-4C71-8897-A98B71EDC229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f9db61c55229eb50958f0b0197189cfd3a0c8f7","datavalue":{"value":"log-space counting classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208403$243A836D-F44D-4B1E-B53F-A41EE370DFFA","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":"Q1208403$5016B3E2-5227-47EB-ABCD-1E102CA82721","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"62a7cf516855bec12a9c56ed37f9b0b18810e65d","datavalue":{"value":{"entity-type":"item","numeric-id":4035689,"id":"Q4035689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$3D1159F4-3150-4687-8BA7-02FD321A168D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20dbb88399b28648dc9d78bc8b7f00777d16b9fd","datavalue":{"value":{"entity-type":"item","numeric-id":3028343,"id":"Q3028343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$94739B0C-A849-4909-8707-5B0B779151A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffb3e46a0deb94f568837a5a711d518011b93539","datavalue":{"value":{"entity-type":"item","numeric-id":3773366,"id":"Q3773366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$82BEEB64-4F89-433C-A6E2-B4EAA720B79B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23708f3ee0b536410829c31900335701f20e86cc","datavalue":{"value":{"entity-type":"item","numeric-id":3835019,"id":"Q3835019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$4A2B9940-83F3-462C-9BED-06FEEA08EE68","rank":"normal"},{"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":"Q1208403$63CA3F18-98B1-4D8A-8CC2-906469677251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01be0fba01f41010482a9b92a86a128f4b1b9e6a","datavalue":{"value":{"entity-type":"item","numeric-id":4122837,"id":"Q4122837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$3CE4EBAA-B7A7-48F0-B3BA-ECC2213467EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"544f9d42a0a8acea09d2cbd1189f6a61d54cb466","datavalue":{"value":{"entity-type":"item","numeric-id":3926063,"id":"Q3926063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$0EF87BDD-29B2-4B87-B751-3B6646BFE4F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3098be175dfc83c9790b870357818695922f9220","datavalue":{"value":{"entity-type":"item","numeric-id":920620,"id":"Q920620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$E05916B3-155E-4B61-B952-6611B78E8B70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66856e28a8d065ae00cc1eb109ee4001e24e8421","datavalue":{"value":{"entity-type":"item","numeric-id":5582355,"id":"Q5582355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$EB4AA90C-1C15-402D-830F-E65C70BF7932","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":"Q1208403$64B2D139-90D5-48E5-9CA4-22A5CF561670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe0513ec18a30b3b0224651c837b2bc319ab97e","datavalue":{"value":{"entity-type":"item","numeric-id":3034844,"id":"Q3034844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$8450A042-5D84-4DA6-BC3C-CA08BE647AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$FD8A560B-DA7B-4F38-A1FC-D3B2883B5F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52f370a6908d3768b88496af00a743650f121e29","datavalue":{"value":{"entity-type":"item","numeric-id":3816981,"id":"Q3816981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$E076AD09-B054-4DE9-B7BE-B323A5F54930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$34BA4602-FB9F-4632-9266-D3BC5381ADA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d396cb7909eb8ef7cf9892a2d4d1be562fcbdc7","datavalue":{"value":{"entity-type":"item","numeric-id":4109298,"id":"Q4109298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$E2CD0879-A708-4312-AE98-0B1E6D27764D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9db059b0a8a64dc3d3cb765bd766be93207b0f3a","datavalue":{"value":{"entity-type":"item","numeric-id":1114675,"id":"Q1114675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$5A8EFA30-1F7E-4814-AA52-0CA9164E0B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30f6e432ce9e9ae75031144ac1199e0b83ca0d7","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$CE165D37-BDE8-4D52-98BC-BF369F0AD6AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"425d93bb2ee09fac5165159b9bd5cd489ffbdbf8","datavalue":{"value":{"entity-type":"item","numeric-id":3034822,"id":"Q3034822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$5697B47A-19D9-41D6-BB1E-E859721D62AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14259755a9136b7b26201f5111f10df5b52f768","datavalue":{"value":{"entity-type":"item","numeric-id":4109299,"id":"Q4109299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$5CF9CCD6-DB0C-4D1B-93A6-2A58088632A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f52d02c047e0712d8c12a407c602d331644480","datavalue":{"value":{"entity-type":"item","numeric-id":3682474,"id":"Q3682474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$AB1AFE8C-E9F1-457F-9613-DBF6E98F58A7","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":"Q1208403$4F91944B-3405-46AE-BECF-A44CE7462077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8194b210616a81519a29e9c197fab619e01f1c6","datavalue":{"value":{"entity-type":"item","numeric-id":1062759,"id":"Q1062759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$5008C090-2E10-4280-810B-1D80E780B2E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186efa9cbcaad91d0d4ad1f36de56ca7d39bfe2e","datavalue":{"value":{"entity-type":"item","numeric-id":1099620,"id":"Q1099620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$AD0626FF-9E7C-4B7D-AD31-D7EC37262CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$D57CE95D-507C-4103-8688-E17367F60214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70536879af054717c0f3d9d913a10e93c328980d","datavalue":{"value":{"entity-type":"item","numeric-id":3853129,"id":"Q3853129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208403$156C5B1E-9D40-4F6B-A47F-44EBA25F642A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6451fb0694527121d3b2aa24fd7c390561dbe11b","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90252-o","type":"string"},"datatype":"url"},"type":"statement","id":"Q1208403$D103AFD6-6AE8-4A6A-80BB-DA532F532DE1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"662d00dbac4412ebdd45d915df0dd1f0dc6e9c93","datavalue":{"value":"W1984509356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208403$0E7031D9-4F9F-490A-84EC-0CE74F5F9E99","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de43382d31a7cd3555e721774680154c6b2461ec","datavalue":{"value":{"entity-type":"item","numeric-id":3569006,"id":"Q3569006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0063cde20219e985779206d9012dfd726bb16469","datavalue":{"value":{"amount":"+0.8060402870178223","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":"Q1208403$F67AA9F6-D6F3-49DE-92A1-DE70F7AEA094","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6230f5d3b8ef0690701db2ec642de9af2200739d","datavalue":{"value":{"entity-type":"item","numeric-id":4035684,"id":"Q4035684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2578c682259cbf06127c1d20198a67a428d9d78","datavalue":{"value":{"amount":"+0.7971426844596863","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":"Q1208403$B0B7122A-5A62-45ED-9576-5731A16582C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a25bd6cad9fb2eac922649fbf9d3976dfee8ef69","datavalue":{"value":{"entity-type":"item","numeric-id":3800016,"id":"Q3800016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4028ee34faabcf98716edb558344d57baf35873","datavalue":{"value":{"amount":"+0.7967554926872253","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":"Q1208403$0A56DBEA-A7DC-4377-8153-4A7F9C134657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78ad04d5e9f660f66f8a162c4c21e58c134d4c28","datavalue":{"value":{"entity-type":"item","numeric-id":4009813,"id":"Q4009813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3db5f0529c23646765503d699d27194165e590c4","datavalue":{"value":{"amount":"+0.7922675609588623","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":"Q1208403$866C1500-0EE8-491B-BE05-B02FB8601A41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a5fe8d80c5088a6a9203082acd34c6ede886486","datavalue":{"value":{"entity-type":"item","numeric-id":1328756,"id":"Q1328756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68de63c5657e98f8859f1495171bf630dc47b32f","datavalue":{"value":{"amount":"+0.7886749505996704","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":"Q1208403$9E04D30C-9F3A-4C3D-A509-5D7002BEF41F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A very hard log-space counting class","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_very_hard_log-space_counting_class"}}}}}