{"entities":{"Q685391":{"pageid":687240,"ns":120,"title":"Item:Q685391","lastrevid":63459789,"modified":"2026-04-11T13:18:20Z","type":"item","id":"Q685391","labels":{"en":{"language":"en","value":"Methods for proving completeness via logical reductions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417337"}},"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":"Q685391$1F8D6F63-D650-4F79-8592-B0D3959ED644","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"710e91b699980e8187918f33e20c8d99b8f97094","datavalue":{"value":{"text":"Methods for proving completeness via logical reductions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685391$2DE82156-C914-4528-A60F-80C19DFEC95A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a10823436e88427a86723faec141f61bd5da6552","datavalue":{"value":"0777.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685391$82AC6CD4-E880-4063-BA92-CB76F31236B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"18c6af1e50e9ddc40ce073235037404f2f61b819","datavalue":{"value":"10.1016/0304-3975(93)90109-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685391$4FBEC641-869E-49A2-8476-790C84EEB1B7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f466736e4a4b4501d0136ec6feb8a629013f44a0","datavalue":{"value":{"entity-type":"item","numeric-id":265086,"id":"Q265086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$BABBA3F2-7465-41EE-8AC9-E5D2093206EF","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":"Q685391$05C8CB27-3B54-4389-9D9C-9347BBD78FFA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"92112234a474f78049341bfb55637019f67e54ac","datavalue":{"value":{"time":"+1993-12-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":"Q685391$4E7694FB-C35E-4054-BD02-D5E6A474CB8D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bda0b7faf227c59c1728b1898decf7ce878b9c65","datavalue":{"value":"We illustrate five different techniques for showing that problems are complete for some complexity class via projection translations (these are extremely weak logical reductions). These techniques would not be available to us if we were to take the traditional view of complexity theory where devison problems are equated with sets of strings instead of sets of finite structures.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685391$0B9241AC-40C1-405D-A128-AB9E1169BFD5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685391$6D6BE05F-E4CE-4507-96CE-C654133A3CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685391$66BEEE24-7ECA-451F-ACF0-4DA86FD9CBAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685391$08CFFE44-2E2E-443D-9946-38C3BEF0F2F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"991528d43c76797ced1d89b4e98af8684bd0fcbe","datavalue":{"value":"417337","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685391$F92C2910-5E0F-4B98-AB23-51A80EE21730","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"158dda8c4a746799a6a46ef33bd6a1c279ad7e69","datavalue":{"value":"complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q685391$FE0143F2-E270-49E8-A31F-C07346E86711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69e4ea30093d8fa32dfa08d62053fb8ff3268739","datavalue":{"value":"descriptive complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q685391$91C84E4C-59DA-429F-9938-0BA47D6C3A14","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":"Q685391$2BE58E7A-507D-4A17-A022-BD258061A4DA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e0c57c83ccec3708beb11432675d0124295fe770","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90109-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q685391$DDF4AA0D-EE97-4F28-9C5B-216B952DD6A4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eec5c5228638dd5f9e401fdc69023cf61b638989","datavalue":{"value":"W1976534954","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685391$038E4FB9-241A-4B43-9A3B-8C238271C804","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5592afdbc278531a8faff3dfe5516c2b3be670a","datavalue":{"value":{"entity-type":"item","numeric-id":2640342,"id":"Q2640342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$75CE5949-3E1A-432D-9C64-03BF07D43C54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$8E13984E-BB8C-41F5-926E-018FA6564725","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":"Q685391$BB993B3D-EBA3-425E-A318-84339D6E7828","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33af22eaf65f5b4ee08bb626826ae3899aae9757","datavalue":{"value":{"entity-type":"item","numeric-id":3221973,"id":"Q3221973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$4108E592-7374-4481-9CE4-33781CD0D275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$502B7A11-04DD-4EEB-B252-3D5E7B9775CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$E3EA90E1-C3A1-4D85-A60A-D322B1ACC1F7","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":"Q685391$8AAA2951-DB40-4631-BA3D-439AD3165443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b86a7428d25186a655d06d9001814911af977b6","datavalue":{"value":{"entity-type":"item","numeric-id":3830533,"id":"Q3830533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$D8047C65-DE75-475A-BBC2-EDF89470C486","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":"Q685391$1EBD0742-A5D2-4466-871E-CE11C5AA9036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7bcf3ca57d05b5f25a83ca2306762ebecb2e712","datavalue":{"value":{"entity-type":"item","numeric-id":5402539,"id":"Q5402539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$650C2AA8-89B7-4B56-AB4B-A50C8A9D910C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1543a6d9030474a2d21021a96f6fd782e1dd1a4e","datavalue":{"value":{"entity-type":"item","numeric-id":1167537,"id":"Q1167537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$630C1FB4-A593-4DC1-9D78-C81044CC27E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"938de9f1befc541f724f21f144961dfe3d7dd15d","datavalue":{"value":{"entity-type":"item","numeric-id":4182723,"id":"Q4182723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$E33152B3-EAE4-455F-9F48-1F43B8081CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a53a620792c1d6ed972f10c353c8182901d68fe","datavalue":{"value":{"entity-type":"item","numeric-id":918199,"id":"Q918199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$A9B0A19F-B3EC-4ECD-A4B2-CF370CE4DFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc6b6537a8c32e823da2d8eed00d4eb81ae5d6c1","datavalue":{"value":{"entity-type":"item","numeric-id":2264758,"id":"Q2264758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$7EC38321-109B-48DA-AEC9-CE15B2B01EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e73c4b1eb952ce21189627f2e0b84dd36494db","datavalue":{"value":{"entity-type":"item","numeric-id":3771612,"id":"Q3771612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$739CA4AC-4573-4968-B78B-1D2C3D95E3B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9986daf6052d9f01de563c5f1fdddec8de4a193c","datavalue":{"value":{"entity-type":"item","numeric-id":4016524,"id":"Q4016524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$A3FEC9AF-4656-4833-AF05-0B640DE85E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45e2c98fb0d6ccbfde016372e777f83b35c84af6","datavalue":{"value":{"entity-type":"item","numeric-id":1183484,"id":"Q1183484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$423BD3E2-FA8C-4ED2-8D06-B63D844B7B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a41df49f51cef3a910ecbc6a3cd38f47613084b","datavalue":{"value":{"entity-type":"item","numeric-id":3358723,"id":"Q3358723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$8F09E8D8-992A-4BF6-9644-FC82F00B4E5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27bbe3725bc74a972465b306588af0ea363d11cb","datavalue":{"value":{"entity-type":"item","numeric-id":4694732,"id":"Q4694732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$909A5607-2257-4227-95D8-2074F2C8A677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ec8eedbc1eea9bb665df31ece605b933e9684fb","datavalue":{"value":{"entity-type":"item","numeric-id":3988061,"id":"Q3988061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$CE861D53-61DD-4810-964F-A65F90E64E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e51b937e5ed6ffa343614ecfb6b0c125b538a5f","datavalue":{"value":{"entity-type":"item","numeric-id":4202957,"id":"Q4202957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$AC3B155F-78F6-4F23-8DBF-227349CFC4CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8148e1b5712da3182330083c0fc5cb5947d9af1d","datavalue":{"value":{"entity-type":"item","numeric-id":4711256,"id":"Q4711256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$F9E6BFFD-5D50-4029-9BE9-FFD6467CEA9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c35e4878a6fb7c4051976b67502cc1edb798561c","datavalue":{"value":{"entity-type":"item","numeric-id":2757847,"id":"Q2757847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$15214D1D-8EC1-40B8-94B9-B75E7BDEA01C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$6CD75131-E8DF-4283-A30E-89A2F918BEC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d1f5d749e4775b9ff8ad70d19f88e3741e680ea","datavalue":{"value":{"entity-type":"item","numeric-id":3495646,"id":"Q3495646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685391$F5B63F32-D674-412B-8BB6-1DF36228BAEF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"244c36a3220c2ca9c6f57c3cd47678b7b99ede4c","datavalue":{"value":{"entity-type":"item","numeric-id":4285624,"id":"Q4285624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71164670dad8f1b2ebd61b3ad31c5743d7a00372","datavalue":{"value":{"amount":"+0.8102332949638367","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":"Q685391$82F1B24F-F0F0-4D49-9E28-971A164A33B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcfbacf54ce5a47ba0fef293f5ef95011089b00f","datavalue":{"value":{"entity-type":"item","numeric-id":1271623,"id":"Q1271623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0024c6542fe4b26a50f67e7a66f274f20f363e12","datavalue":{"value":{"amount":"+0.8094484806060791","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":"Q685391$08DD442E-8497-4F8D-B080-44E3D88A4DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3fcc3fa8d96e84b3c9cf16374ba1f550f6527db","datavalue":{"value":{"entity-type":"item","numeric-id":4202957,"id":"Q4202957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b66ea9c653f00215ad70499b59e5c03b6eaad723","datavalue":{"value":{"amount":"+0.8027808666229248","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":"Q685391$B4571F52-4859-4B05-B26E-6FD8399C7A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a65dba3d324fd296089ad0561845cdead9cafce","datavalue":{"value":{"entity-type":"item","numeric-id":1709685,"id":"Q1709685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fa5394709234b1deafce1da313aff33dd00cfc8","datavalue":{"value":{"amount":"+0.8012567758560181","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":"Q685391$EFCE26CE-AE39-4EA0-ADBF-5A941361AAF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c370c38dc3cc02d897b1ba8a0dc6bc5072f0dbd","datavalue":{"value":{"entity-type":"item","numeric-id":4644504,"id":"Q4644504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea0bcd90967f5db61bfb8363d7c687ba8d2eadd8","datavalue":{"value":{"amount":"+0.7894110679626465","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":"Q685391$80610D57-F351-4887-8434-81018C82A29F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Methods for proving completeness via logical reductions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Methods_for_proving_completeness_via_logical_reductions"}}}}}