{"entities":{"Q761246":{"pageid":763095,"ns":120,"title":"Item:Q761246","lastrevid":42680767,"modified":"2025-07-08T10:30:15Z","type":"item","id":"Q761246","labels":{"en":{"language":"en","value":"NP-completeness of the Hamming salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3887437"}},"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":"Q761246$E7D42F33-9C6D-4F04-85DD-337B412D6DC2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b41cc3494d1ddf6080725f58416b303c55bc923a","datavalue":{"value":{"text":"NP-completeness of the Hamming salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q761246$197E289A-34C7-4ADB-839C-5A4AFDB31E7C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cda356e7e48ecce5c5c5198bf845be9253120748","datavalue":{"value":"0556.90059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761246$EC182203-9681-4B64-A999-75C90DB7BE45","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d5b49fc4c99b25496c4a8cf4be5a2576333feaac","datavalue":{"value":"10.1007/BF01935007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761246$0D7096DA-7635-4014-8040-C724A06C3D00","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2462bfa2e7b21647971f5ceba0db4df7e82b9c7c","datavalue":{"value":{"entity-type":"item","numeric-id":761245,"id":"Q761245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$D8FABF5C-22DC-4A6D-A0EA-FC991A96507D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2fe70195d1e0d46d568646f1bb894a0f78708017","datavalue":{"value":{"entity-type":"item","numeric-id":396691,"id":"Q396691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$1A14FC4C-A8DF-42AA-9911-A4A669179E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b9d41db9542b9e299bc59f6b5e045205852e8537","datavalue":{"value":{"entity-type":"item","numeric-id":666177,"id":"Q666177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$FF400456-2355-4615-97EB-03F16902AFA8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$95845999-616E-4B23-B9F7-660CD210E8CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q761246$E22A5DBF-C354-4C2C-9E8C-DE43ABA9A664","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa9a92ad1fbfe4dc5c14568b238602bd3fe1b648","datavalue":{"value":"It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q761246$381683DF-27D4-4911-9FEF-2DC254F01E51","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761246$B46E7208-FE15-4611-BEEC-1E360BDC8CC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761246$DACB9ED9-CFC5-4778-9921-25FBE3136239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761246$EFD5A8F8-4F4C-4180-B8A7-4BD1B3407636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761246$3EB90CCD-2890-4939-BCCB-468978066169","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"048860820dd033c936fa5d60166cca94c644c25b","datavalue":{"value":"3887437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761246$A33E3E2B-69C9-45D5-BB95-3625FF6F4120","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d5b12d0177e268df375aad2ad619a8f45edc384","datavalue":{"value":"Hamming salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q761246$7FA81109-838C-44E9-93C1-1C75BCA5DBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q761246$B60AC783-AEA0-45BD-9963-E44D3CDEE924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99de46d71759c0d7b682d826cd549f3d1ed09133","datavalue":{"value":"data compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q761246$9DD77BA8-7C88-40EF-A3BB-C13C83AA8323","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q761246$87F34DE8-28E1-47C4-93FF-5605D689DB7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41d705fce159038d4e9fa6f75b93491a0ae80440","datavalue":{"value":"bit strings with Hamming distances","type":"string"},"datatype":"string"},"type":"statement","id":"Q761246$659F33F9-ED8C-4496-A9B6-A592CEC40892","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":"Q761246$13B186AC-DB1B-45E0-A79C-6FE364F56402","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b0f1936becf1a709a2aae7f54a275ca7b4b13de","datavalue":{"value":{"entity-type":"item","numeric-id":3339301,"id":"Q3339301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$D84BF49A-137D-408B-8E3B-DE4C979ED32A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7f026c0302f30c0354ff4c709bf1b9860da93c","datavalue":{"value":{"entity-type":"item","numeric-id":3851615,"id":"Q3851615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$6691FA25-BDCF-45D9-9B80-D1EF5779E13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7431b8bc1af7a6351e7c2d86660f496894ee616d","datavalue":{"value":{"entity-type":"item","numeric-id":4155835,"id":"Q4155835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$4CA63029-CE3E-41FF-8A1C-C98B7F95F790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8b5333eb1b8ed8e5a5b9dc077a98e596db9c9cc","datavalue":{"value":{"entity-type":"item","numeric-id":1250163,"id":"Q1250163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761246$3FA362DE-A46A-4115-848E-07032772EF42","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2ba5d04def5423a8349f4ef7c6e442b27423818","datavalue":{"value":{"entity-type":"item","numeric-id":4885735,"id":"Q4885735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dc3096cc7e8b7193b5508701600cfdc6ae09d37","datavalue":{"value":{"amount":"+0.8642417","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":"Q761246$C49C54F7-555B-480C-9CC6-2401522835BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50abd82f7e41a81e3456e7bb3710326b6c46aa31","datavalue":{"value":{"entity-type":"item","numeric-id":293205,"id":"Q293205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0030f413c411617fe55b8a943eeaf9ddfc63686c","datavalue":{"value":{"amount":"+0.8627821","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":"Q761246$BBF90959-A4BE-4085-924A-A62075A2FCFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4798a608c6785aed8b6aab66fb543734ca522fa","datavalue":{"value":{"entity-type":"item","numeric-id":1903594,"id":"Q1903594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcdb85fc69864ad13eb9505eed996dbb99aab51f","datavalue":{"value":{"amount":"+0.8619164","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":"Q761246$32163B34-A0F7-4ED9-BC3D-3931C113EB8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"379f0719730f316d71685ac33928eb7ef6a7eff2","datavalue":{"value":{"entity-type":"item","numeric-id":629366,"id":"Q629366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba2b479f7a6d8ebdc8164c6623c075f55c3be3e9","datavalue":{"value":{"amount":"+0.84914804","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":"Q761246$55E70674-BF5E-4EA5-A7A3-E71A8D982559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fe6b26c3f1e971e19dd31c9a65e729c24a363f5","datavalue":{"value":{"entity-type":"item","numeric-id":5897915,"id":"Q5897915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a4ba945fdf90bf9b52de506f0ea5f757ced47c7","datavalue":{"value":{"amount":"+0.8450899","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":"Q761246$742497FE-3E7E-4389-ADBB-6B5E2F116791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b6cac11bde44270e4e1e3fa2eee2c3b5625fa3c","datavalue":{"value":{"entity-type":"item","numeric-id":3191592,"id":"Q3191592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d09dc30ab7d2917b7e80003043993d7083776f3","datavalue":{"value":{"amount":"+0.8439287","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":"Q761246$1E78A10F-7412-442D-8F15-040C5A1149DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"908fad04dfc551c68dd9440837b8ffe2c376d7d2","datavalue":{"value":{"entity-type":"item","numeric-id":4542552,"id":"Q4542552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93dec95e3f1d30d681c70b085b0a2e920e1ee998","datavalue":{"value":{"amount":"+0.84313285","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":"Q761246$D8E520B7-388C-4C36-8D69-CBBBBFB9100C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"802ec88cfcf2fa422e9be90200123ec7ef418236","datavalue":{"value":{"entity-type":"item","numeric-id":1201257,"id":"Q1201257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f13887ace57c0efbabbf08fee93aebbe47c40af","datavalue":{"value":{"amount":"+0.83475006","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":"Q761246$F24C9E1B-398B-44A0-BC41-0056DC45CB8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee3c49add65936359282bedbce48434af69813e7","datavalue":{"value":{"entity-type":"item","numeric-id":2686649,"id":"Q2686649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6f7a54fbddb47e762109b13ee2f76ff719aeaa5","datavalue":{"value":{"amount":"+0.8346108","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":"Q761246$6F4370F7-8830-4EA6-B5DD-88071E724D62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f17e23f676f606adbaf63688d7fe6b8ac1c54f7c","datavalue":{"value":{"entity-type":"item","numeric-id":1095806,"id":"Q1095806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8aabca423a99aa2b3f70eb8b8d2795a3410e38a3","datavalue":{"value":{"amount":"+0.83377856","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":"Q761246$6F37702B-0C84-4B25-B0C1-EF1D5353AEA8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:761246","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:761246"}}}}}