{"entities":{"Q1406047":{"pageid":1416787,"ns":120,"title":"Item:Q1406047","lastrevid":68630649,"modified":"2026-04-13T01:03:14Z","type":"item","id":"Q1406047","labels":{"en":{"language":"en","value":"Upper bounds on ATSP neighborhood size."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1977917"}},"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":"Q1406047$611A060D-CF6E-47A5-8121-2EA62F7CD84C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d99ba76e13a027504a4584a1d52cb68e2de36d7","datavalue":{"value":{"text":"Upper bounds on ATSP neighborhood size.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1406047$12723E56-DA19-4E40-BB13-5AF94A16E7CB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ddce0637cdd3f14ad79cf405441e29b9b91ab07e","datavalue":{"value":"1126.90413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406047$C935BA6C-3671-4CBD-8A9D-0FA55F620D23","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"23cf28178ae3dedbae77625a98a31699c90eac30","datavalue":{"value":"10.1016/S0166-218X(03)00181-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406047$20B492F9-1895-4DB2-A4EF-D9E23473777D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$9DCFD59C-FBC8-4F0E-BC68-2BA8FD85A320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d62d1b98a8e47330bd8d09b4c364147d7b3d1f6","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$7404C158-A1CA-4882-9541-23309420DCEA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$35ABF606-C8A5-4DFA-A9C0-2152C90F3503","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5a3bd22b3255d28cafbe1a32be16f369f6f38fa5","datavalue":{"value":{"time":"+2003-09-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1406047$2A386813-891D-4C0C-97C5-0DA8A5ACA29D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c4500c7fb972d8319b71ef2ec341df911984f775","datavalue":{"value":"We consider the Asymmetric Traveling Salesman Problem (ATSP) and use the definition of neighborhood by \\textit{V. G. Deineko} and \\textit{G. J. Woeginger} [Math. Program. 87, No. 3 (A), 519--542 (2000; Zbl 1043.90075)]. Let \\(\\mu(n)\\) be the maximum cardinality of polynomial time searchable neighborhood for the ATSP on \\(n\\) vertices. Deineko and Woeginger conjectured that \\(\\mu(n)<\\beta(n-1)!\\) for any constant \\(\\beta>0\\) provided P\\(\\not=\\)NP. We prove that \\(\\mu(n)<\\beta(n-k)!\\) for any fixed integer \\(k\\geq 1\\) and constant \\(\\beta>0\\) provided NP is neither a subset of nor equal to P/poly, which (like P\\(\\not=\\)NP) is believed to be true. We also give upper bounds for the size of an ATSP neighborhood depending on its search time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406047$79039CE0-F71C-4E69-8499-471A735C9771","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406047$CE5A611F-5E1F-4D92-ADF6-DB7D1131E259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406047$6BFD24B7-CE66-4E9B-87C1-B24356A90962","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eeed6b56eb2d1620300151e86a289c3c3d79d7fa","datavalue":{"value":"1977917","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406047$626B5EFD-9680-4A50-8F8E-9911111B0B12","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97339565def2592a07038417be073b47fb6235f5","datavalue":{"value":"ATSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406047$79C96620-A544-4165-9067-6F120E9B0C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22dacbaef8a4f8d80a666aea3501722dc1ab720","datavalue":{"value":"TSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406047$94901E0E-AD7E-445A-935B-C502F847976E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df90664031335b301df87419552921d8159c86a0","datavalue":{"value":"Exponential neighborhoods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406047$D06B63B8-CBC3-4BCB-887A-63C9E06986F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aadfe02502da5af00e07656a1b8b4290e025112b","datavalue":{"value":"Upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406047$E73A7D75-FD5E-4E61-92EB-35DB8FFAAFEE","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":"Q1406047$F3635F3F-B68B-4C1D-85A4-5DAFF8BE5AE1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"77603a316f9fc5a4ef71b23813df472c259d2abf","datavalue":{"value":{"entity-type":"item","numeric-id":4208001,"id":"Q4208001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$AF182A39-7B28-4718-983C-16B44957A35C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2ca77c77da9ee11bcf24f059510cee8234cb30f","datavalue":{"value":{"entity-type":"item","numeric-id":2884495,"id":"Q2884495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$6405B22C-363F-4987-A852-30C18A99F91B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e0a936d29cdb004405e9ceab9ae0698c1fa987d","datavalue":{"value":{"entity-type":"item","numeric-id":4321931,"id":"Q4321931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$7DB3C9A2-10B1-46CB-95BD-ACBDB17A3289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f335709cafac8ad70fda23558eac5858cccfcd82","datavalue":{"value":{"entity-type":"item","numeric-id":2757553,"id":"Q2757553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$7CB3202A-83FF-4DC5-BD28-362DDCB42FA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666261474c9625949f651c962cde2d1f630ea4ba","datavalue":{"value":{"entity-type":"item","numeric-id":5202515,"id":"Q5202515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$6F8870AE-45D1-4DAD-9CF4-20705D4E599F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f02692ab5e02eeb4a93cdc93016786aca9db3e6","datavalue":{"value":{"entity-type":"item","numeric-id":4801179,"id":"Q4801179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$ACD76F09-C472-4EF5-9D7F-4C7C2F68BFC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5009df9c2650d54601861f947f8157b16561e492","datavalue":{"value":{"entity-type":"item","numeric-id":1575073,"id":"Q1575073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$1D5A9114-87F1-49B0-947A-DE9E3286C79F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"305990cab47347d26b508880daf4599932710fd4","datavalue":{"value":{"entity-type":"item","numeric-id":4347415,"id":"Q4347415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$89F586B7-0DCC-4DA0-A7ED-73EBB16DBA9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0603e209bc2c65199cd27ad284915c29390bd9","datavalue":{"value":{"entity-type":"item","numeric-id":1302597,"id":"Q1302597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$7C359C01-C34A-423A-91EB-45D2965EB9BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25d9f8f8116e4c4092d8523e564337cfe67f89ed","datavalue":{"value":{"entity-type":"item","numeric-id":1602705,"id":"Q1602705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$E70234A5-C50C-4ABE-878C-4814137A5BF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2b206654145bb614f823d931be67273ce8cde2","datavalue":{"value":{"entity-type":"item","numeric-id":5939600,"id":"Q5939600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$4A2F7359-51DA-40C1-9024-26FAC94E7E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07e0e210c2b538b89ee0cda8dffe01727da92864","datavalue":{"value":{"entity-type":"item","numeric-id":4461908,"id":"Q4461908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$AE541942-3402-4521-AB8C-3B7FC28C8ED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f32f78d6e8c3eba29ef098ef40d17751882b05b","datavalue":{"value":{"entity-type":"item","numeric-id":3915001,"id":"Q3915001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$235F8FDF-07E5-4740-97C0-6AE673FDD03A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dda67ffe55a20ae507a3599fd974da2bf2128dc","datavalue":{"value":{"entity-type":"item","numeric-id":2780838,"id":"Q2780838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$C63075F2-CC99-4ECC-9419-225BDB7A2411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"236471e7419367f6cbab7c264e3a1487e20722e5","datavalue":{"value":{"entity-type":"item","numeric-id":1602706,"id":"Q1602706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$810F9C90-34FA-4C26-AB0C-5C694EEB0180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"136de6ba8cbf4ce5721a71aadfedbbb485b25611","datavalue":{"value":{"entity-type":"item","numeric-id":4116281,"id":"Q4116281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406047$D3186032-5EB9-46B5-A2F9-6A1431ADEB4D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"616fff7985335753e233fb5dcd3ff371c01e0743","datavalue":{"value":{"entity-type":"item","numeric-id":1374382,"id":"Q1374382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"191094d16841965b84ba0c7005a810add4959fe7","datavalue":{"value":{"amount":"+0.7855377793312073","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":"Q1406047$53C1E15A-BFE4-4AA4-9CED-B0106F0C1B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62b392f7a2ae6e034a78f271578a10fd829774bd","datavalue":{"value":{"entity-type":"item","numeric-id":1302598,"id":"Q1302598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1617d111df09f702befebb9a79631172af1ed869","datavalue":{"value":{"amount":"+0.7674838900566101","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":"Q1406047$D4F76C53-36C7-434C-9B2F-BABE49EB632B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bb4e255666e6ea6efbe1bb0b381f192b731e269","datavalue":{"value":{"entity-type":"item","numeric-id":1575073,"id":"Q1575073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5780175f482bcdb6cbe10c640c2dec432ce56c8b","datavalue":{"value":{"amount":"+0.7674835324287415","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":"Q1406047$26DED9C7-7EB2-4714-A829-6C5555504330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62d9046129f415ea113da783658d064b65e395f3","datavalue":{"value":{"entity-type":"item","numeric-id":2491321,"id":"Q2491321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b54676fee32e94d4f1964ed37dc79831f70a7db","datavalue":{"value":{"amount":"+0.7668588161468506","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":"Q1406047$517CA3C2-82AA-4CC9-B458-9121DEA88753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2f040c82bd43e8859e6750909137eab07a53b4c","datavalue":{"value":{"entity-type":"item","numeric-id":5168426,"id":"Q5168426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b78e609002db95ec6b9d20adea1a62d322a4dd41","datavalue":{"value":{"amount":"+0.7636985182762146","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":"Q1406047$B885C63C-14CB-4F69-8A5D-799AF16A6BD7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Upper bounds on ATSP neighborhood size.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Upper_bounds_on_ATSP_neighborhood_size."}}}}}