{"entities":{"Q2849941":{"pageid":2860661,"ns":120,"title":"Item:Q2849941","lastrevid":51828812,"modified":"2026-01-20T06:11:44Z","type":"item","id":"Q2849941","labels":{"en":{"language":"en","value":"Length-increasing reductions for PSPACE-completeness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6210000"}},"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":"Q2849941$797E9436-1EE9-40FE-BC91-5849AF874187","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"831f0497421e7a1468223bb6466238d8d4c05b0d","datavalue":{"value":{"text":"Length-Increasing Reductions for PSPACE-Completeness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2849941$7AB8EDCD-C56B-41DB-9097-C1685C233DAA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ed757500057c46c7537a28fe42339ff30fcbbd6","datavalue":{"value":"1398.68182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2849941$51E515E4-0C40-4BB4-82B0-AE7F1043F387","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"69c60a11f63ee6ec68ebd7a6b240a7c3566f0f81","datavalue":{"value":"10.1007/978-3-642-40313-2_48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2849941$675692FE-F03D-48EC-8103-13AE89CF6F16","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ee1f3cf09e866f3eab6561711e5db4300ad48b0","datavalue":{"value":{"entity-type":"item","numeric-id":596116,"id":"Q596116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2849941$C4ECD69E-4508-4B48-9E71-D6F739ADCCED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"717bd7e49187dccbd000704e69f42d17b3b2d5b2","datavalue":{"value":{"entity-type":"item","numeric-id":208054,"id":"Q208054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2849941$1E8864BC-4060-4AE8-BF15-9610C13DF1CC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8b0aacf98b336f97857e5af880885f827de491a1","datavalue":{"value":{"entity-type":"item","numeric-id":2849893,"id":"Q2849893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2849941$AB193799-01A6-4ECB-853A-5F35C04BBBC2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3dcb12e53a075f2a49b79b16a6317b340847e43","datavalue":{"value":{"time":"+2013-09-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2849941$4619F9F9-B151-4A23-96D7-EA79DFCDF627","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2849941$46C93905-85B1-48A9-A58A-1BC081BB4241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2849941$268B0467-4D48-40E8-9131-80C573AF1C9E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45487321c8cc51e21954d9fa8c7102390210dbc9","datavalue":{"value":"6210000","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2849941$0023EEA6-494B-4E96-8709-19DF56BA3790","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2849941$A3DEB761-14D6-4C18-89A1-8786672C0763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6816fdf79dd11ac09d9af4886c02baab03d2cf9","datavalue":{"value":"completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2849941$7FE41EB6-7E32-4E2D-BDFA-ED3FEA6AF288","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9a5c39c49495b493fde67f93bdb47081b7713e0","datavalue":{"value":"length-increasing reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2849941$6A6C1E53-772F-4DAC-8490-BA5A52728ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c107bb63de79565718d188b33fcc483957cfdd","datavalue":{"value":"PSPACE","type":"string"},"datatype":"string"},"type":"statement","id":"Q2849941$39F353ED-5D2C-4B76-AE14-377E8A183869","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":"Q2849941$FCFA0C22-CDE3-44C6-B6BF-ADDA116817E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b36bcf2855bcc817764efd83d120576e6521d10b","datavalue":{"value":"https://doi.org/10.1007/978-3-642-40313-2_48","type":"string"},"datatype":"url"},"type":"statement","id":"Q2849941$FE4BB34D-314D-4F38-9C1B-261A5DA21EC1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9b53459387470ad8422a99a2b6adfb528a323640","datavalue":{"value":"W176257112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2849941$B52166F0-95A2-450F-ABCE-68C7A76D190B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8273181031919cc5ee9ed42b01d671c50eac338","datavalue":{"value":{"entity-type":"item","numeric-id":1193869,"id":"Q1193869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"736722217dce2bdb588d7b62f9088dba88979e11","datavalue":{"value":{"amount":"+0.7862536311149597","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":"Q2849941$014A1E49-563B-44A2-B1E5-9809017DA188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73b19e37bf9cdb775f931feb20a2a2efac2d82a4","datavalue":{"value":{"entity-type":"item","numeric-id":4596607,"id":"Q4596607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e08dd70127a1c3d4904690e474498be7052f851","datavalue":{"value":{"amount":"+0.7802433371543884","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":"Q2849941$BF53DA06-5F24-4355-926F-732F755CE84A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a06a8960d554c08fc9d564eb0a373a0cd788708c","datavalue":{"value":{"entity-type":"item","numeric-id":1107310,"id":"Q1107310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d4d50c4726afd833210eb480337b758452e4bb1","datavalue":{"value":{"amount":"+0.7762965559959412","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":"Q2849941$35B26506-B607-4E3B-970C-FACF9A3171B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"762f764aba4e743b1e95274db89089b2e0502b4f","datavalue":{"value":{"entity-type":"item","numeric-id":5492867,"id":"Q5492867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7079e63764dbd0bf39ac86569b61b5ef2d490714","datavalue":{"value":{"amount":"+0.7762117385864258","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":"Q2849941$940558AF-F345-41B8-A3F6-3006ECE9E8FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df312a1d0f915a1d483f5a73dc70c4fcc38a622e","datavalue":{"value":{"entity-type":"item","numeric-id":3747726,"id":"Q3747726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad643302fed341d814322abdb0754b0e9d6c9298","datavalue":{"value":{"amount":"+0.7761314511299133","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":"Q2849941$B8B8C74B-5916-4F18-8524-94D7486A1998","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2849941","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2849941"}}}}}