{"entities":{"Q1107320":{"pageid":1118069,"ns":120,"title":"Item:Q1107320","lastrevid":69835761,"modified":"2026-04-13T10:40:23Z","type":"item","id":"Q1107320","labels":{"en":{"language":"en","value":"On characterizations of the class PSPACE/poly"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064491"}},"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":"Q1107320$2E9AD545-B2B6-4BFF-BA02-FF48F7576D61","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efba7f54fb15195f3cc99836328392c517b1cef2","datavalue":{"value":{"text":"On characterizations of the class PSPACE/poly","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107320$5617B07F-77CE-4829-8419-FE2D676C8FFE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fb0a2fc39b8892caaf18311a364e230dcc931846","datavalue":{"value":"0652.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107320$43A2EAD3-D50F-4912-AAF9-18795B230A2B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6a4aaba6abe20e8d9d9bc7ec53587ca577e54ba","datavalue":{"value":"10.1016/0304-3975(87)90111-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107320$582C6EBD-4C57-4C5F-A7E4-E4A2E26A42FF","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":"Q1107320$60DD351C-5DA4-4E62-9E97-79B4EA7EBA8A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1107320$AF64CEC3-AFB5-4E3B-8A05-41B85B0FB948","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"64ad4d076ed74d4fa21c35dc8e61ea954119f62e","datavalue":{"value":"The class PSPACE/poly is defined as the class of sets recognizable by a deterministic Turing machine in polynomial space with the help of an advice of polynomial length. The additional information given by an advice is the same for all input words of equal length.    The authors present several characterizations of the class PSPACE/poly. For instance:    - as the class of languages with polynomial size quantified Boolean formulas,    - the smallest class of languages containing regular languages, sparse languages, and closed under concatenation, intersection, polynomial- erasing homomorphic replication, and transitive closure of length- preserving relations,    - the class of languages recognizable by polynomial size vectorial programs,    - in terms of space-bounded Kolmogorov complexity sets.    For vectorial straight-line programs a characterization of problems with an exponential lower bound on their nonuniform complexity is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107320$AC94B4DE-E5DE-410B-8A69-5F9FDF2123C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107320$F7E15903-323F-482C-B262-C6380CD59D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107320$113ED8EB-2BA5-426B-8DDD-90F239AB544B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"25d23bce0fa5891c0be259761326ac64ed805424","datavalue":{"value":"4064491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107320$1DC9B191-5657-423F-AD61-20F9CE7C358F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b9523b81abac7dcf2946305ecf06ced9bb8e7c3","datavalue":{"value":"structural complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107320$9CC02629-A4DB-4060-8226-394B9E0CBBC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9a7b03c1290f4420f511d8fcb71a4d38b5c445b","datavalue":{"value":"closure properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107320$58413F4F-7656-478E-B344-26555D21458B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08c32420b55550422a342b5bcbce3f4569e98de5","datavalue":{"value":"parallel computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107320$65D3922D-F53E-43CE-B7D1-4CBA449FDEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d418edb5228027fbfce9f0201bc21ddd0c87513","datavalue":{"value":"PSPACE/poly","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107320$992FA835-4D1C-4326-977C-437156757C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107320$02D0D12F-FF0B-429D-B140-0D60BD38D490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7addf554547f5b8ac51affbbb26514d03f507bb9","datavalue":{"value":"vectorial straight-line programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107320$7A8554BB-F693-4F08-B217-87A4C2D525B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"387251027f7a6e047be71bdb6ddf8e33740cddeb","datavalue":{"value":{"entity-type":"item","numeric-id":415620,"id":"Q415620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$ED98C1B4-7D24-44DD-B190-2CB08DC1CE1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2dca00cf5e3506d17c2986004891f80ecd82aa0","datavalue":{"value":{"entity-type":"item","numeric-id":314817,"id":"Q314817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$2A6633E5-DA03-4FAE-ABA1-83E8D0EAEFD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb01c5911b75cf8a04ac445d3e91b5ce7cb29956","datavalue":{"value":{"entity-type":"item","numeric-id":293413,"id":"Q293413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$88120C45-DEB3-4906-9E73-1BC9D5B4BE1D","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":"Q1107320$04E30DA3-4331-491F-B40A-A92779E35684","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3c0844c5220d12b13992de8d21371b3338fe8d28","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90111-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107320$809931D6-5BFC-4878-8195-76BD86F67032","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"df029b543f69c0c1fc331d0a9a2d5f5bef73180d","datavalue":{"value":"W1966101287","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107320$B73B7A93-7B26-46EA-A5D7-6ACB6DAC13F6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6fb41bd0ccb37924a4c937a2bb8019232379890","datavalue":{"value":{"entity-type":"item","numeric-id":4430281,"id":"Q4430281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$EE170575-F08C-4469-B16D-F985543D513B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458c0889fc8c6fce9f88bcfe1e3a7f838d82b19b","datavalue":{"value":{"entity-type":"item","numeric-id":4139701,"id":"Q4139701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$D34D7591-443B-4F93-974B-DA29A97FAE67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc9ae9d5fff6aa6e473c37bd6f69c5fc14bec7fc","datavalue":{"value":{"entity-type":"item","numeric-id":3856099,"id":"Q3856099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$392037A5-9DB8-485D-9C34-74E48DD78F18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebc88252a3381864b1dcabc8cfbc007d9bc85ea5","datavalue":{"value":{"entity-type":"item","numeric-id":1251069,"id":"Q1251069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$0A35A37B-9043-4850-8A6C-E2F1BB941A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07adfa7411d8716c42e7a81a35a8dc21f533009d","datavalue":{"value":{"entity-type":"item","numeric-id":3951543,"id":"Q3951543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$508254B7-F2E6-47D8-A8B3-211F4596C803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bc3040b7348184db3eacf7d8b95da966aad979d","datavalue":{"value":{"entity-type":"item","numeric-id":4197339,"id":"Q4197339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$2A96D011-DB9F-4196-BFF5-83FBD62010E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"701aa2250533d80f4380055710c24c90ee1cec71","datavalue":{"value":{"entity-type":"item","numeric-id":3718157,"id":"Q3718157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$D66C89B1-C47D-4325-84A8-2D3A563B9F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d700f265cf737d8de6345cc5812fbb3555684ba","datavalue":{"value":{"entity-type":"item","numeric-id":3674026,"id":"Q3674026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$7DC36E6A-FCA2-447F-9BCC-94BB103DE817","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":"Q1107320$4612C06F-9BCA-46E7-8163-9B897B7E22AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6841b9962aaa0960cd814a5370c9e0eeb2fc6839","datavalue":{"value":{"entity-type":"item","numeric-id":1091817,"id":"Q1091817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$3F39741F-7AC6-4ADB-9D29-3B96C0483B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ee215ab31826542ee08b5f2836a7e16b51d11a2","datavalue":{"value":{"entity-type":"item","numeric-id":3668855,"id":"Q3668855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$C16D8FBC-948B-4129-869E-E57D4594EF6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0670b22f2552f07ca7245832dc7b60b11a95ad28","datavalue":{"value":{"entity-type":"item","numeric-id":1232182,"id":"Q1232182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$4A0D184D-7241-4A3A-B9B5-E2D47112FD88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4ab13142076117cc14856c9cfe9c081eaaa2f9d","datavalue":{"value":{"entity-type":"item","numeric-id":4172915,"id":"Q4172915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$0819B4C2-2B7E-426A-8718-760C2BF8C01A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63543c709dbc0dad9af888025f0c28158a4c2594","datavalue":{"value":{"entity-type":"item","numeric-id":802309,"id":"Q802309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$AC9B5AB8-A43D-4634-8948-C9F42CFA07B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ff2c269b97a88de0fe652e2add75347876b7e3","datavalue":{"value":{"entity-type":"item","numeric-id":1361890,"id":"Q1361890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107320$96DA7161-8D5F-49F5-8038-E4E18FB39E2A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1e93a51d666326998dff447d7379e77ed608b366","datavalue":{"value":"Q126472584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107320$8E6E4237-FD4E-4712-BB58-472CA2313BCB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c1a67c0e1809aed0f6153506a73a5ddd2089698","datavalue":{"value":{"entity-type":"item","numeric-id":3753480,"id":"Q3753480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"523592681d7f6568358e381b138bd7b374d770fe","datavalue":{"value":{"amount":"+0.8986606597900391","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":"Q1107320$EC06D81B-03FB-44BE-974B-5D80B7DDBAED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75bdb882f4750a686aa82cfd918ceb59e50b5856","datavalue":{"value":{"entity-type":"item","numeric-id":4301636,"id":"Q4301636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c00aa91026f47b54b5c311081d161fe0a94250c1","datavalue":{"value":{"amount":"+0.7452505230903625","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":"Q1107320$58676E49-4D42-49F2-9DE5-F7291A255AD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4354a20f0e3a1c1bebc8a9b4f2c93f432a5ff244","datavalue":{"value":{"entity-type":"item","numeric-id":4436033,"id":"Q4436033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c00aa91026f47b54b5c311081d161fe0a94250c1","datavalue":{"value":{"amount":"+0.7452505230903625","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":"Q1107320$BFD2C1F5-B9F3-4E50-AB17-9FEF1FC9D5CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c98b7889617822a5d36b305c752a3b15eb7d4ec","datavalue":{"value":{"entity-type":"item","numeric-id":5192980,"id":"Q5192980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"292224670a2df915d091ff8540ec9545df6c5471","datavalue":{"value":{"amount":"+0.7382365465164185","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":"Q1107320$6936A13F-7193-444D-8A1C-81B706F38EE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1c60c2c59bd153eb7cff323c3427866bd6c13ab","datavalue":{"value":{"entity-type":"item","numeric-id":3506329,"id":"Q3506329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a16079341ca3d8312261b302f780bab9605492cb","datavalue":{"value":{"amount":"+0.7376615405082703","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":"Q1107320$97BEFFBC-9712-410B-9C77-B3185979DC67","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On characterizations of the class PSPACE/poly","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_characterizations_of_the_class_PSPACE/poly"}}}}}