{"entities":{"Q631772":{"pageid":633620,"ns":120,"title":"Item:Q631772","lastrevid":63112110,"modified":"2026-04-11T10:40:06Z","type":"item","id":"Q631772","labels":{"en":{"language":"en","value":"The transposition median problem is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5865594"}},"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":"Q631772$F093F392-6111-411B-B3C7-4A8225AAAF95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c54c4661102f2ab95a915d3e631635085d2355b8","datavalue":{"value":{"text":"The transposition median problem is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q631772$2AE00D2A-9990-4713-9F4C-2A51F5020A1C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b43871c14e7aa369b1b64625c5680ba70d2b7429","datavalue":{"value":"1207.68155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631772$0546D1C7-0A6E-4175-8702-F6C9EDFB7562","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d67d906459308ff6d46d607c3d28eab180d0b395","datavalue":{"value":{"entity-type":"item","numeric-id":631771,"id":"Q631771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$5C8568B8-149A-4D29-90F4-1E0704DBB7B3","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":"Q631772$35C91884-C8C2-416E-AFDA-85B8B11A0363","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4f05c15c599566c03aa1303bff626bf49bc05676","datavalue":{"value":{"time":"+2011-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q631772$EB34233F-291C-495C-B0B7-59B56703B8FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631772$C451998B-F76A-4144-BB30-0292D70194D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631772$67D43B23-EE39-4924-95F8-E6083B042E4F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"99ff7a754ebe5b3598eea41e989eca886ad51431","datavalue":{"value":"5865594","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631772$74E225A9-CB9C-4FAA-89BB-4E5AAADDD2DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b7e4790f966cbd4dc64c66bc171d552cd7af6ca","datavalue":{"value":"transposition median problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q631772$116F9BBF-6318-461D-B955-42AA41F4F123","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q631772$A6A4E791-9873-41F4-B65F-07A9348C3777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e958ad869053060c15accd06c291b22b21f46de","datavalue":{"value":"phylogenetic reconstruction algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q631772$F671B6BE-FEF5-45BB-BBE4-8B97EA5E57A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e10792f2d5189c9c9b856105b6a9fdabfade126b","datavalue":{"value":"reversal median problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q631772$4ECF424F-8A17-4E73-B50B-278CC145A023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d76cdd4b1ebc5ec206f469e727c0d7a7fd4337e3","datavalue":{"value":"transposition distance problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q631772$F5C42FC0-0FCA-4159-A8A4-9D7610B42AF2","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":"Q631772$834C0F1D-CF91-4140-A98F-FA38CC715554","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1681239be5b2228f8175dad4a035c55025f43398","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2010.12.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q631772$4688579F-C396-421C-8D6D-BEAF5A11D5AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ebc5abb2e28e5e18fefb0dbed2bf089003373365","datavalue":{"value":"W2012090438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631772$308405FF-8E9E-4D14-A021-950954A86B13","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c21084dc8e80215f9fa0f0c8b51f2fd1e2c5c88","datavalue":{"value":{"entity-type":"item","numeric-id":4410169,"id":"Q4410169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$D0AFDBBE-F751-409B-AD06-13050DB290A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3ec8c3d9a5965ddb21e87cd3e0556de8a68dcd9","datavalue":{"value":{"entity-type":"item","numeric-id":2884551,"id":"Q2884551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$F3A96A13-04AA-467D-BC5C-99B427B19AD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22212ef2cd5eca400a52668c90cdd00e27c4560e","datavalue":{"value":{"entity-type":"item","numeric-id":4801153,"id":"Q4801153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$BE09B86E-3B65-4122-B6D3-E0FF7C940223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c408d98e9c3e1333746b8d16b11c5d7096a91f7","datavalue":{"value":{"entity-type":"item","numeric-id":2490115,"id":"Q2490115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$21060088-3317-4183-AF9A-7C8ABB376FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29ce20185623f8c28bebb00ad0d073799967be02","datavalue":{"value":{"entity-type":"item","numeric-id":1853543,"id":"Q1853543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$698360EA-3721-46C5-BAF4-399499CAE2A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5e201c2b579b8c70d76c6408c175e8ca744357","datavalue":{"value":{"entity-type":"item","numeric-id":3922182,"id":"Q3922182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$5DF3A33C-4C84-49D6-BDF4-8129FFAAF10B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea741b440cf384527b78a1da2273aaa863fe8038","datavalue":{"value":{"entity-type":"item","numeric-id":4255810,"id":"Q4255810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$915A57D8-8FAD-4F66-A979-48FE34DF32F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd386990ad28d7631b1993101e8123a7da1e3fe9","datavalue":{"value":{"entity-type":"item","numeric-id":4877518,"id":"Q4877518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$E58F5974-6F3F-4768-9F60-5144A0334406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"000cd166dda4aa770c70b63e00261c6853dfc028","datavalue":{"value":{"entity-type":"item","numeric-id":4388990,"id":"Q4388990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$3EDC6358-0957-4D71-A1EA-6CF3F1DC404E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81e8c47b53d219690ccca6f2ddf47fa915a07c06","datavalue":{"value":{"entity-type":"item","numeric-id":5901157,"id":"Q5901157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$0DF9E248-AEE5-4B29-96A4-9AF85E26B0F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ca6bf99a9d443a7446549c9fea6945659a7963","datavalue":{"value":{"entity-type":"item","numeric-id":5539432,"id":"Q5539432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$E6A4B6AB-B198-49B6-99DD-1AD8FE48C0D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa2a1ac4e864d41c30b8a828a68a91d18d8ecae","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$92AEDA00-8724-4B9C-A704-35720FBD4010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e917d43e8b25008fefbc321152cc22fb4c2ba954","datavalue":{"value":{"entity-type":"item","numeric-id":3596365,"id":"Q3596365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$E45D0A7F-6194-4412-AA74-8124866D277E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d6105cba249d613ed52b5bf40f233f82d706bf8","datavalue":{"value":{"entity-type":"item","numeric-id":1022594,"id":"Q1022594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$D937B788-7AFA-4B1E-B409-4991EBAB32BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0a3aa0d959be786f82bc234e7cff91ad4e4a4f","datavalue":{"value":{"entity-type":"item","numeric-id":3176582,"id":"Q3176582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631772$21043010-5550-484E-BDBF-AA91B2220625","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a2e1c3e05009f8e0a2e29134939ef824b6c69be3","datavalue":{"value":"10.1016/J.TCS.2010.12.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631772$C1BAD9CC-1EAE-4669-B8F8-70AAA0BDF266","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"913e242c0e3a0fadbf2406be264352b554072a36","datavalue":{"value":{"entity-type":"item","numeric-id":1022594,"id":"Q1022594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca126910a4d6c9528e0385067e402e0f807fc9ca","datavalue":{"value":{"amount":"+0.8058801889419556","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":"Q631772$ECDD4656-59AD-494E-959C-7F5D57D4E474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"719cb09ea62b84fe5b508a2b052b9f44febf3e99","datavalue":{"value":{"entity-type":"item","numeric-id":5713534,"id":"Q5713534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12f3188ac8935ee6a93f8c692dc491bf89df1063","datavalue":{"value":{"amount":"+0.8045620322227478","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":"Q631772$F679FB62-B20E-45A0-968F-21E060A3523B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"732851b03df1e338a3a828259f7629b7df230760","datavalue":{"value":{"entity-type":"item","numeric-id":818147,"id":"Q818147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2c94a1baec3453917090f43ed4ed1b4549370d4","datavalue":{"value":{"amount":"+0.8028897047042847","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":"Q631772$C2457983-005A-400A-BE10-459904349061","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The transposition median problem is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_transposition_median_problem_is_NP-complete"}}}}}