{"entities":{"Q1077168":{"pageid":1087920,"ns":120,"title":"Item:Q1077168","lastrevid":70062291,"modified":"2026-04-13T12:10:45Z","type":"item","id":"Q1077168","labels":{"en":{"language":"en","value":"Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3956456"}},"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":"Q1077168$9E31F14C-2F3D-427C-BBAF-9B77A07535FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb9e38d40941ff67820af986ee2269632cc7b9ce","datavalue":{"value":{"text":"Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1077168$5E6CCBEE-2DA9-4365-9547-19B572B0AFB9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"66796f94ddf28635ed7b0a48d0f697d7d383ff7d","datavalue":{"value":"0594.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077168$32997F30-EC55-442C-BCAE-A505F89B66F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"acae7e82c2d3ef46398d19f3366628216b4d343f","datavalue":{"value":"10.1007/BF01896811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077168$70E8CAE2-CBA0-4ECF-8019-65B0BE5E160D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f599934ad10d19e2cb67f86f48d0ea65a928295","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077168$689405F6-B4AC-4571-B0FE-C5FEE8786B04","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2febee684711f4cb1a453192904f1a5144211493","datavalue":{"value":{"entity-type":"item","numeric-id":65457,"id":"Q65457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077168$13CD0B4F-3AFB-483A-BEB8-B8A2433968CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1077168$9906E46B-249F-49FC-8CE0-4CFBFD538E58","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f5ed28f420a4434059a135bfa6ef950a01de97ce","datavalue":{"value":"The paper deals with the NP-completeness of computing the nearest neighbor interchange metric in the space of all unlabeled binary trees. The polynomial transformation starts with some variant of the problem PARTITION which is unfortunately not strongly NP-complete. However, the author has the analogous transformation from the 3-PARTITION problem (which is known to be NP-complete in the strong sense) and thus the announced result is correct.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077168$F6F0DC5D-8F40-4703-9E51-37CA0ABBBF4F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077168$6463C57E-70E4-41C6-9DEF-4B06FCBC9A4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"48a59f52dcfcc38cd6697e0ef07319031311895b","datavalue":{"value":"62H30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077168$CC0555EA-DB57-49D3-9D66-DFB8F27D8722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b821ebafb3baf72aa941fa76ac449b531a981f1e","datavalue":{"value":"92F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077168$E6A9FE23-CBEC-4824-BEAF-4647B3BF6F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077168$80FD9906-25C4-4F94-BCC8-5655E53FD959","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"515b4559f54722dd2780051b0c28866283e4a5b8","datavalue":{"value":"3956456","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077168$0D1CF924-7969-4804-BC62-5363F12EB922","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5dc3d1fe025b4d4b1c20b96ea859e2ed97cf2a2","datavalue":{"value":"dendograms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077168$F62E13C0-CD95-42CF-9809-A9942ED76229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077168$7AD50EB8-71C5-46CD-A800-521D66CEAAC5","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":"Q1077168$0AF4CE68-D095-4AF6-B44B-7853E96BA18A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d6ced5345cd68953fa80157358a19516bd3b5c3","datavalue":{"value":{"entity-type":"item","numeric-id":1057598,"id":"Q1057598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077168$18F51A2C-D563-490E-BBB3-3F214BE1520A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b875fe67b4d8496bd5d08cd6af0fefb1515124a","datavalue":{"value":{"entity-type":"item","numeric-id":1166933,"id":"Q1166933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077168$D75B5CE4-503A-437C-BC48-D38AFF1595E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26e5b6ecff16f443f95123d12d4a05d82778e189","datavalue":{"value":{"entity-type":"item","numeric-id":1057599,"id":"Q1057599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077168$9D17087B-8542-4E49-A81E-66CEFE0D18AE","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":"Q1077168$B7CC7AD8-CBCF-43CB-85C7-B8C55BB0A9E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4cc4a7ecc6049fce452aec78e65ad081d5e7ec","datavalue":{"value":{"entity-type":"item","numeric-id":4148000,"id":"Q4148000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077168$568E3408-2D3C-4550-8E53-593DCDC361EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e475a1333ff30fdd8204a93cef9e98ad42b35b8b","datavalue":{"value":{"entity-type":"item","numeric-id":1057598,"id":"Q1057598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb67294e98b6d22a9ee2f0b5ee15bd6903043560","datavalue":{"value":{"amount":"+0.865986","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":"Q1077168$27B9DB6B-BB35-4521-B88D-195435249381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ee7eb039438f9e6451f5c3d8c79f93d28de6bba","datavalue":{"value":{"entity-type":"item","numeric-id":3521928,"id":"Q3521928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39167dbeab53990b1ed18aee89e5ee3300ca2e90","datavalue":{"value":{"amount":"+0.8512788","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":"Q1077168$650E9BFF-7177-4E52-BC59-D27095CF1A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce83535899958c00668601f8ffc97aa596440b7","datavalue":{"value":{"entity-type":"item","numeric-id":5901089,"id":"Q5901089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb5158286405cbc49274e6b89beccc5fa7b69171","datavalue":{"value":{"amount":"+0.84561265","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":"Q1077168$B0436A23-65BE-4694-A6B1-880E18F05455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3eb2926e1ced4648218c65a66b2c2e815715444","datavalue":{"value":{"entity-type":"item","numeric-id":5917578,"id":"Q5917578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bef4398c15b580e22458746bbe1e05b22b1cc2a","datavalue":{"value":{"amount":"+0.8456126","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":"Q1077168$6E3E674A-1A8E-47CA-BC62-65DD54E7B54A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cce30be3f229e493cd93976525dc22327f9755a9","datavalue":{"value":{"entity-type":"item","numeric-id":96718,"id":"Q96718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a3905738b165eb75eb0fb53e7cd050f621c1614","datavalue":{"value":{"amount":"+0.84544706","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":"Q1077168$77E93A96-D5C4-44CB-AFF2-8C9B72114469","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcc9b3fdb3f8cd80fa81ad268a7e4b7a0166a797","datavalue":{"value":{"entity-type":"item","numeric-id":1708596,"id":"Q1708596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4eecbd88bb7d9117cf0a41d89f9acb9aab7e9133","datavalue":{"value":{"amount":"+0.84354997","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":"Q1077168$6A375F99-A1C7-44E4-B6F7-03D7AF85C727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76e69da6e76f15cbe385124b7c4959ca0fdfdd6c","datavalue":{"value":{"entity-type":"item","numeric-id":4542533,"id":"Q4542533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d61f0eed3e6ba9b32c7e5b333717c0979abc56e","datavalue":{"value":{"amount":"+0.8433136","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":"Q1077168$6205917F-A8CA-4D3E-96EB-8DE798ABD6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7c7064707a46c80a4530028bc08f2cfda4c2504","datavalue":{"value":{"entity-type":"item","numeric-id":410711,"id":"Q410711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67442dc65e23b58a0db77c900505172a513dfbee","datavalue":{"value":{"amount":"+0.84044385","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":"Q1077168$1F059873-672D-44AA-A3F8-33F4AD322EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca5a9f9e3d638f0f6220b7e29aa0dbb55f0c20f9","datavalue":{"value":{"entity-type":"item","numeric-id":2934633,"id":"Q2934633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c46ebe8c780fc272344fc6a5ad112ddb950c91d","datavalue":{"value":{"amount":"+0.8375953","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":"Q1077168$FB1D5A89-2481-44E5-94D2-99061C8030E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_the_nearest_neighbor_interchange_metric_for_unlabeled_binary_trees_is_NP-complete"}}}}}