{"entities":{"Q1183604":{"pageid":1194353,"ns":120,"title":"Item:Q1183604","lastrevid":47057707,"modified":"2025-12-31T13:13:33Z","type":"item","id":"Q1183604","labels":{"en":{"language":"en","value":"Oracle branching programs and Logspace versus \\(P^*\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33434"}},"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":"Q1183604$4867BA69-A5BD-4E3E-83D8-EC867D914246","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9664e4bb48e59965baa1b70331dacb85760d7e51","datavalue":{"value":{"text":"Oracle branching programs and Logspace versus \\(P^*\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183604$63212338-3451-4671-92EA-F43100C24638","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ff9223de4fe2b3bfb906c47a6bf6bc1f04bf0818","datavalue":{"value":"0744.68107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183604$42C53D71-2B44-4707-B044-A3D05FCC1176","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"33e54f4d4a73c718d0623fa086dc7e09012072dc","datavalue":{"value":"10.1016/0890-5401(91)90017-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183604$C558D028-C0D6-45FF-8B81-04E810DC58EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"795e5af62cffee265773a4ab5f77af480f86d75e","datavalue":{"value":{"entity-type":"item","numeric-id":386052,"id":"Q386052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$ABF2122D-F3A9-4798-8BB2-322D73A4DC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4068ada97919eaff29760aff5ebf2f7939a1ba7a","datavalue":{"value":{"entity-type":"item","numeric-id":208763,"id":"Q208763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$0B2AA47C-0763-444B-B644-4A8C8246B6F2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$DBE47F18-42BD-4702-A0D7-8F8990F65EE3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183604$B47E7028-3AA1-4C60-AB54-77DA74562CFA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"363a7f8a089b24db3bc0786435d4105430f05f76","datavalue":{"value":"The authors investigate the space complexity of the \\(P\\)- complete \\(GEN\\) problem by means of so-called oracle branching programs. \\(GEN\\) consists of determining membership in a subalgebra of a general (not necessarily associative) binary algebra (input as a multiplication table). natural subclasses of \\(P\\) can be expressed as natural subproblems for \\(GEN\\). Finally, the authors prove optimal lower bounds on the size of oracle branching programs for \\(GEN\\) with certain natural oracles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183604$1EF1C18A-E6B9-4AC5-864F-E41F4435E07D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183604$C0417BBF-8FEA-40BE-8806-33A779E36C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183604$45DF62C4-76A7-4DDE-8C40-83EB981E1FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183604$6612781C-69A3-4B17-BE6B-99A5632BA2E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee890c6c6897d7427c8ae909a2069f6e75c4ea5e","datavalue":{"value":"33434","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183604$72514EB6-B704-4E13-918B-305862549761","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88bef4b4e25191a906198683a98c2dcbe39300c4","datavalue":{"value":"\\(P\\)-complete \\(GEN\\) problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183604$2CB8AC25-8FE7-4B6E-A838-5DE9824E4610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183604$86C800BD-8FA0-4BEE-9844-CAADCEA87A25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c912dd45456959aa9594fa8a89e3f787ad398ae","datavalue":{"value":"oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183604$AC6B03D8-F52C-4651-A796-FE1BA0120751","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":"Q1183604$7BB149E0-C130-401C-81BB-92C7322BB11D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85332f45c574807884e55f6488cd3b450f276a8f","datavalue":{"value":{"entity-type":"item","numeric-id":1117696,"id":"Q1117696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$77F67BA2-3492-4467-92F3-EE6BA426B925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a500206698011a9fd73535b39e18690c6e06e392","datavalue":{"value":{"entity-type":"item","numeric-id":3820014,"id":"Q3820014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$F58077E2-1A9D-4375-B129-DA9A6B970F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e86a79bfcfca810fb7601492bd0551fae9de8408","datavalue":{"value":{"entity-type":"item","numeric-id":4142697,"id":"Q4142697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$C229CC1C-0A4D-4B5D-BAD5-36019205CAA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfda1aaef4d74a55b724a4e4b97259bc5a577f06","datavalue":{"value":{"entity-type":"item","numeric-id":3936210,"id":"Q3936210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$B3C6DE48-5FF1-4D77-9BB5-427A43923277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0445ca81f1046c8b5bea1a2062f174b139078383","datavalue":{"value":{"entity-type":"item","numeric-id":1217591,"id":"Q1217591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$E5E4BC49-A8D0-4E42-95A6-DD11D0628E46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a006907d50546bdc051c28c96b89ad928a5269a5","datavalue":{"value":{"entity-type":"item","numeric-id":1158753,"id":"Q1158753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$F53DB30A-D476-4E7C-A6D2-20C96574EE8A","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":"Q1183604$3D3B3F05-5352-4AAB-9C0A-FB705D4D9BE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b23a99da8df474d603cdef7b4c76229f6a312c3","datavalue":{"value":{"entity-type":"item","numeric-id":3787477,"id":"Q3787477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$57A37D39-5A00-41A4-B34F-849BCA94985C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd898582b3042cd9f98f55a99a55f26af0712fb","datavalue":{"value":{"entity-type":"item","numeric-id":4128417,"id":"Q4128417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$9B52E5AF-A739-4651-B9AA-ABF60F80B423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$E2BE0AFC-5F5F-4EED-917A-9B352AF9882F","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":"Q1183604$2BF7372F-1F2A-463F-88F1-CDCB0BE2388D","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":"Q1183604$88FC8114-E497-4295-A1FB-24FE13637114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"373c65ef4069b52a23fe230e08a271e32f56a00a","datavalue":{"value":{"entity-type":"item","numeric-id":1235982,"id":"Q1235982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$A0F38776-5D7B-4286-9C7A-E041A5726831","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":"Q1183604$58400B7A-8084-4CC6-B23B-B269AB4CC07A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e8f4a97c15151b7298e02d2e43c13b4217479da","datavalue":{"value":{"entity-type":"item","numeric-id":1106664,"id":"Q1106664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$A6B88FE7-8CFE-4558-AE22-E34B60CDEE42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66c847f293733ed20ca36508bc48a02f1d51906c","datavalue":{"value":{"entity-type":"item","numeric-id":4732127,"id":"Q4732127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$770C94C1-90A6-4CF4-A7B5-180293F0EA70","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":"Q1183604$11419B53-9F4B-4473-A432-9A516757394F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67ed33de7061de4d7d8391bea59c71fda756b59c","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183604$DB1260C6-9AB4-4F3F-8AB6-4ACAC469886C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f98d2f53a0439cb3286b4114a0f88aa925154c12","datavalue":{"value":{"entity-type":"item","numeric-id":3975161,"id":"Q3975161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d795801106bf8a49d7f5430b9e701200ac68e55","datavalue":{"value":{"amount":"+0.9490790963172911","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":"Q1183604$16050EC6-3FB6-4E39-8AF8-D2378016B58E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"541a178111f993a235d5703f41bb424e48ce3ec8","datavalue":{"value":{"entity-type":"item","numeric-id":3974873,"id":"Q3974873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d795801106bf8a49d7f5430b9e701200ac68e55","datavalue":{"value":{"amount":"+0.9490790963172911","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":"Q1183604$C8CB0E54-F84B-4F86-93E3-3D90878257E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dce546b9b5a7338926d39a7f160efa85dfee29ec","datavalue":{"value":{"entity-type":"item","numeric-id":918199,"id":"Q918199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96e4dee237c51c19a13494b0d2335b23d28c0dc0","datavalue":{"value":{"amount":"+0.7596017122268677","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":"Q1183604$1C273899-199B-454C-9D34-498B398BF227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5ea381846430470ab6059997a9dcdacbd56f4e5","datavalue":{"value":{"entity-type":"item","numeric-id":929291,"id":"Q929291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53ad89a8fdfa79e68afac24c3b87d3cb867eaca4","datavalue":{"value":{"amount":"+0.7511574029922485","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":"Q1183604$1894B7D4-CF56-457D-A96A-AC9353B29659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f460ed5be1d82cef3bdbaef78e81691ac4e7bc68","datavalue":{"value":{"entity-type":"item","numeric-id":3787493,"id":"Q3787493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1900d1136e763c3ee1de2a887fa7451708c2cb","datavalue":{"value":{"amount":"+0.742822527885437","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":"Q1183604$AC787659-6315-421B-B5BA-583ACA2CABE8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1183604","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1183604"}}}}}