{"entities":{"Q1978500":{"pageid":1989242,"ns":120,"title":"Item:Q1978500","lastrevid":43460111,"modified":"2025-07-26T01:46:44Z","type":"item","id":"Q1978500","labels":{"en":{"language":"en","value":"Topology of strings: median string is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1454280"}},"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":"Q1978500$45A4FE0A-AF16-4BE0-BB8F-529771435562","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bdabb95a4b53fa35ebec4a1354daff4f8647f87a","datavalue":{"value":{"text":"Topology of strings: median string is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1978500$0B097071-6524-46AC-9399-EF3201918FF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cf755188f3aab58118c5f70c38b6877c1c0b80a3","datavalue":{"value":"0940.68116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978500$9E49878B-B0F1-40A2-8108-4780710BDC21","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"007009e67ad15c4a05ce8dd544b2e8ab6fcdf546","datavalue":{"value":"10.1016/S0304-3975(97)00240-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978500$EB9FDD05-D628-4BB9-B86D-AC584296A48C","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":"Q1978500$BE352D44-7639-4D82-95A7-44AFD0DA1567","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cea4e04940bd3504f3c0f2b605e025bc106fb722","datavalue":{"value":{"time":"+2000-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1978500$4C5EAB6E-AC24-4A80-89EC-DAD67B2F2637","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"13cead95486be28d57d268e35db17f4e8c1eecb5","datavalue":{"value":"Given a set of strings, the problem of finding a string that minimises its distance to the set is directly related with problems frequently encountered in areas involving pattern recognition or computational biology. Based on the Levenshtein (or edit) distance, different definitions of distances between a string and a set of strings can be adopted. In particular, if this definition is the sum of the distances to each string of the set, the string that minimises this distance is the (generalised) median string. Finding this string corresponds in speech recognition to giving a model for a set of acoustic sequences, and in computational biology to constructing an optimal evolutionary tree when the given phylogeny is a star. Only efficient algorithms are known for finding approximate solutions. The results in this paper are combinatorial and negative. We prove that computing the median string corresponds to a NP-complete decision problems, thus proving that this problem is NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978500$F8DF69B8-2D59-4AE7-AC26-CAC521A7A2E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a784276b4e09d379c8147965411b455c3d79751","datavalue":{"value":"68T10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978500$132D5E35-0DC8-4B02-B6ED-1FC8BE32B908","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d994e47d5f8418b19faffb130466dde56de480ed","datavalue":{"value":"1454280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978500$D4FC11B4-67D6-4696-819B-29AFEA199EC8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978500$249BE745-2BCB-4CD5-ACE3-2ADFA0438D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bde557def9d4616f22a1529222314886ba2bd870","datavalue":{"value":"string-to-string correction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978500$6017E1D4-6666-449E-AE80-3A1FA1E4B5AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dbcc40adfff09d8abb1ed419690f997e3c652e4","datavalue":{"value":"Levenshtein distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978500$AB64E2EC-3758-4437-A658-CB7ED359A01A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80d93058835fb8528e41ad0bb9bd341b964abd06","datavalue":{"value":"generalised median","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978500$B374F092-82E3-45EA-A3C5-1FAA4E46CBEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e904b6a2b63343426458be16881487ba173b5576","datavalue":{"value":"multiple sequence alignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978500$FB80F60E-F2DF-4529-A35A-EC9181DA2B96","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b1ac159602d2ba36859d766a12e5c8220e72725","datavalue":{"value":{"entity-type":"item","numeric-id":391202,"id":"Q391202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$F90FD24F-5FA0-4B4A-A52D-3A48BB9868DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3cf7cffa8950aa7ac7e529c3ee8bf19d8d7aa20","datavalue":{"value":{"entity-type":"item","numeric-id":207949,"id":"Q207949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$A96E743D-554D-40D0-8F56-E26D6DCEE284","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":"Q1978500$A5068831-BB9F-4486-9A07-C051F108E0D3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0cac6dbfc86183a366c75151800e8612af5d043","datavalue":{"value":{"entity-type":"item","numeric-id":1191624,"id":"Q1191624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$5EDEB48D-4D94-4D73-9493-47CC5AFA44B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c48056905641e6fd74ba309322613a7199dc7f2","datavalue":{"value":{"entity-type":"item","numeric-id":3670607,"id":"Q3670607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$B99457C1-7CFA-419C-A1B1-987BD053BBF7","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":"Q1978500$ECA67D20-C38B-43AB-880C-A105ADAECFD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9faa8a234ab5a7b213a023fd44fcc066cb7be2bb","datavalue":{"value":{"entity-type":"item","numeric-id":3971961,"id":"Q3971961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$5917A4FF-A425-461D-B83F-7AB52BB9E4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab9691a696d1db2e74c8d320b8ceea30e9281fd6","datavalue":{"value":{"entity-type":"item","numeric-id":1390863,"id":"Q1390863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$3324DEBC-2F24-4C63-AAD6-18905C3B3194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e6ba0e02850b1781a5067268c95eeb155a7e9c5","datavalue":{"value":{"entity-type":"item","numeric-id":4859180,"id":"Q4859180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$3CC31FE7-D046-44B0-850F-0F1ED238076A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"016534c5051497ac9d921dc440506ff67c153fe8","datavalue":{"value":{"entity-type":"item","numeric-id":3681960,"id":"Q3681960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$B50B625A-789C-4C5D-BBB1-4120A3CBB70A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6f12679e730f186e807cbb39398fa0f8075753","datavalue":{"value":{"entity-type":"item","numeric-id":4404425,"id":"Q4404425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$15CE4D1F-B390-4B08-BDCE-13DD15C69C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52167224d36a5d07a0811c1028a343afd1d168e3","datavalue":{"value":{"entity-type":"item","numeric-id":1924406,"id":"Q1924406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978500$81E29A39-4F24-41C5-95BA-74C3B1DFD1B8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92b5ab42eb1b1a2ee6adcb70b8c069d2732d077c","datavalue":{"value":{"entity-type":"item","numeric-id":3550844,"id":"Q3550844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1b0f079f084ba2472a27d346196119ba710cb4d","datavalue":{"value":{"amount":"+0.85023147","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$9254C0FD-1C7A-44A5-94AB-3C5BC2226BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dad98650dd151bbfed75dc43b29f123339bc576a","datavalue":{"value":{"entity-type":"item","numeric-id":5874533,"id":"Q5874533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26d555044894ec9543b4e1fcbd980a91b6adc086","datavalue":{"value":{"amount":"+0.8209348","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$389BB632-17A4-4104-AD60-3663F4F0BF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22d9f399ae292852db0c9f17eefc09edbc25235e","datavalue":{"value":{"entity-type":"item","numeric-id":5917583,"id":"Q5917583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bce9fb3e9d2f98182b93a453f1b0f93b4cca4173","datavalue":{"value":{"amount":"+0.8076331","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$E90F6CB1-09E8-413C-BCAA-8A8CBDB230BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ff207c341c51ccc8796b32508d391ff8bd6ebd3","datavalue":{"value":{"entity-type":"item","numeric-id":876700,"id":"Q876700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c35c2e7f6ce84916dfa9961d18bcf99bbfacd20","datavalue":{"value":{"amount":"+0.80695057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$9692C0FF-864D-4AEA-A60B-703AB6FBC22B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25b89f3bc36fc24e1c0b0369e29095e0b161a951","datavalue":{"value":{"entity-type":"item","numeric-id":6089314,"id":"Q6089314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f860403e85e4ac54e46b2b507fee09c74b83032","datavalue":{"value":{"amount":"+0.80482966","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$CAB5446F-9591-45FF-8790-E829E8A5660A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6780a473f2531033ed9ff794b00f2c819392e060","datavalue":{"value":{"entity-type":"item","numeric-id":4258669,"id":"Q4258669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"077d9684841dd58ff4a1f79f1e91cd0a5f8d5c2b","datavalue":{"value":{"amount":"+0.8035176","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$21E0DF5E-F91E-48E8-9143-BC86DC0B3257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"babde557e5cdbec10149a2d9acaaa7b4467a3789","datavalue":{"value":{"entity-type":"item","numeric-id":1112845,"id":"Q1112845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cd7bc5f10ab2895be622e65e997412bef2df977","datavalue":{"value":{"amount":"+0.8027258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$60688F37-62D4-43EC-9D50-1F2CB14C6709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1769f4d92c056bb50f053c2d6c288a200ff6af4","datavalue":{"value":{"entity-type":"item","numeric-id":631772,"id":"Q631772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"682c621bad29b0da0148b7d53bd2356420465c44","datavalue":{"value":{"amount":"+0.79878247","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1978500$90BCF4A5-2621-40EE-AAA9-576481C618B5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1978500","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1978500"}}}}}