{"entities":{"Q1108263":{"pageid":1119012,"ns":120,"title":"Item:Q1108263","lastrevid":66146676,"modified":"2026-04-12T07:51:35Z","type":"item","id":"Q1108263","labels":{"en":{"language":"en","value":"Decompositions of nondeterministic reductions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066858"}},"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":"Q1108263$EA0C1538-587F-443A-B5D5-7F7E0E7ACE90","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"003050308811fe30524996f8517c10e690f4f99c","datavalue":{"value":{"text":"Decompositions of nondeterministic reductions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108263$52219AC5-6829-4048-BC97-8ACAEEAF67F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fa070d771053d3a8c07f20df07ee0b1516f730ea","datavalue":{"value":"0654.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108263$C82E81F6-00B6-4EB9-8FDA-22A8B65B092A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"734335886a576a7736d0b78d29ff1bc45d6b2619","datavalue":{"value":"10.1016/0304-3975(88)90025-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108263$68E7AFF8-7BDB-420C-B9C2-DB86C161BA26","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":"Q1108263$C6201FF6-9C32-4BC4-B1A5-4395E2EB2D27","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":"Q1108263$19C03EAF-32B1-46FB-A022-17411A311669","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"26d92518b90b6aa248511f05155793cb1938cd7a","datavalue":{"value":"Turing reducibility, conjunctive Turing reducibility, and many-one reducibility are related and compared with respect to determinism vs. nondeterminism and polynomial time vs. logarithmic space. By relativizing some equations relating polynomial time and logarithmic space classes via formal language operations the author obtains a characterization of the nondeterministic reductions with a polynomial time or logarithmic space bound in terms of nonerasing homomorphism and Kleene's star.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$EB80920A-2AEC-4EFD-B6E3-A618F23E8DF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108263$9ECFFD05-A473-4206-AF3A-A9AF4DD693A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3fca415580115e1e0a74c69afb3a7d85b0c01d8d","datavalue":{"value":"03D55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108263$DC089A8F-DE70-486E-94A3-5B01718B8B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108263$89DC8BFD-14F0-4D6E-A05B-254D38525FE4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2450bf0c839d41811717126d31e91350f6cb0f5e","datavalue":{"value":"4066858","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108263$A8725289-68FC-4E3C-8131-A7DAA94DCC90","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a4571ef153b923cfe613550c3ec4d2c1e665f8c","datavalue":{"value":"relativizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$05FB628B-F2F0-499C-9011-7AE11D8F5024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca8747e792c9ec070a2b651f7745015b1625753b","datavalue":{"value":"Turing reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$3212E2DC-A031-4A66-BEF3-2FDF29DEDB8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"214cfd74473bc6d0eae3b8ca28189646d43fd7f1","datavalue":{"value":"many-one reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$25B481C6-06C6-4B32-BDA2-A23B3D4A45A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52ba6d968a7617d9b56b80603a9b30974da2b918","datavalue":{"value":"determinism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$9AD558B8-8D28-40B6-8747-60554B81F5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$BBE3F483-BCBE-41D3-8797-33104C8424E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$7A9242FC-AF75-4357-A1CF-E2BFF416B0C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f18bc21d823222e01f5a88a6fb3d1663d7daa25","datavalue":{"value":"logarithmic space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108263$B469BBBA-BD6C-4C68-B6DE-144C804AB480","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"506f0ce7bc6c0b7f9b3af2721fc1bde2eff5db2d","datavalue":{"value":{"entity-type":"item","numeric-id":1163379,"id":"Q1163379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$8FA1C24D-838E-41D6-AD27-B3E777C87F6C","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":"Q1108263$21007EEC-EF0B-480A-963F-43C23BB69481","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1ecee5f64a58d36247d9753b01d2f3839164bf59","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90025-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108263$07C8DB72-EA23-4257-9FA8-563DE1D74770","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7ba281cbca86c984e118312ee2911a5aba878adc","datavalue":{"value":"W2062265191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108263$5EE1BF67-0CA9-4CA1-B2AA-FAAB3B2977E4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$5557B441-D6BF-48DF-800F-5678492480DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$6712F8A0-21FE-4B93-BB4C-AC66D36DAC7B","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":"Q1108263$C2754856-00E6-4A1D-BC29-8B35608B9B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$2A8B9E03-F14A-46C3-B197-DDFFF79399FE","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":"Q1108263$C0AC1A98-19F2-43B4-8B89-D1E7C3818E51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$7778DE83-9954-4E76-9FCB-F9A36A8FB005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a181dd30afaafedddc5b141ee9b82f81ccc5fe9","datavalue":{"value":{"entity-type":"item","numeric-id":4185825,"id":"Q4185825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$3900A204-2509-4F93-A14E-F1CE3D41DF19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800321fe9f6efe205a2eb283e0da5841a2b5eaad","datavalue":{"value":{"entity-type":"item","numeric-id":1061485,"id":"Q1061485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$E19AD772-80D4-44AE-9963-425996452504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$F5CA0A63-429A-4F60-A6D1-6F93AC220803","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":"Q1108263$E874FADA-10DA-41FE-9C47-971BC2898309","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":"Q1108263$E381F1BE-0F91-4475-A46E-FD63EE30DFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fe382d78f0b00c10085a8c1b7559bfa56c77c82","datavalue":{"value":{"entity-type":"item","numeric-id":3036705,"id":"Q3036705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$6224A477-209B-4276-B01A-424DB02F5BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$2F2D31C8-BA0D-4864-A389-BE66C10A18DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$1D42BE6C-7996-44AD-9CF8-7A8D0CAEE128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10e0ec2d25eff3ed5afdd13928195836b0b8d94","datavalue":{"value":{"entity-type":"item","numeric-id":1094139,"id":"Q1094139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108263$6B37EE1A-5F76-45FD-93F3-4F6799997144","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0796d2b8179f01de4fec5ad84e2e46d0f1ca6acb","datavalue":{"value":{"entity-type":"item","numeric-id":3730019,"id":"Q3730019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4cf31b35dd02a3e033380205d0d88bbaa9b92e9","datavalue":{"value":{"amount":"+0.8967773914337158","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":"Q1108263$4E3191D4-0011-4789-A614-A550D0734B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4671e20e55fd66149796a8476cb163b99fb1f344","datavalue":{"value":{"entity-type":"item","numeric-id":3682474,"id":"Q3682474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5872b3c48c2a79e97e84a4462857c625de6cc000","datavalue":{"value":{"amount":"+0.8721204996109009","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":"Q1108263$650D9A80-3805-402E-BF5E-B29BBAF20BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07a9d4ad7ae22f524bdc74d68af21286c7e889ee","datavalue":{"value":{"entity-type":"item","numeric-id":3763590,"id":"Q3763590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfe356d03e4d2179dff7b0cbd4ec589236028e1d","datavalue":{"value":{"amount":"+0.8369327187538147","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":"Q1108263$5CB0E61F-EB70-48EF-913B-AE7294B63392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f771479938cc1c59d36669e47d77573bf3afa84","datavalue":{"value":{"entity-type":"item","numeric-id":1312179,"id":"Q1312179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7037efa5b6bf380f27ece2bdbff7cae14d00a877","datavalue":{"value":{"amount":"+0.7766888737678528","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":"Q1108263$FB22292F-C1A3-4071-9E26-76DA260AE042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45302ee3e76657c4343961037e9229a737aad4f5","datavalue":{"value":{"entity-type":"item","numeric-id":4351919,"id":"Q4351919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8941eea61c109635913e0a1dc44ef4b0c50cbabe","datavalue":{"value":{"amount":"+0.7722665071487427","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":"Q1108263$01309EF7-5DE0-4D41-9E6A-EF95A0CAD974","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Decompositions of nondeterministic reductions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Decompositions_of_nondeterministic_reductions"}}}}}