An Optical Solution For The Traveling Salesman Problem<\/a>
\nTobias Haist and Wolfgang Osten<\/p>\nAbstract: We introduce an optical method based on white light interferometry in order to solve the well-known NP\u2013complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non\u2013polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to NN<\/sup> for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal\u2013to\u2013noise ratio. The proposed method is meant purely as a gedankenexperiment.<\/p><\/blockquote>\nLook, this is really<\/em> not hard. You really<\/em> don’t need a world CompuCrackpotism expert to tell you what to think of this. If you read carefully, the authors were actually kind enough to explain themselves, right in the abstract, why their proposal doesn’t scale. (This, of course, is entirely to their credit, and puts them above ~98% of their colleagues in the burgeoning intersection of computer science, physics, and non-correctness.)<\/p>\nHint:<\/em> If the number of photons scales exponentially with N, and the photons have high enough energies that you can detect them, then the energy also scales exponentially with N. So by the Schwarzschild bound, the volume also scales exponentially with N; therefore, by locality, so does the time.<\/font><\/p>\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Several readers have now written to me independently, asking for my reaction to the following paper: An Optical Solution For The Traveling Salesman Problem Tobias Haist and Wolfgang Osten Abstract: We introduce an optical method based on white light interferometry in order to solve the well-known NP\u2013complete traveling salesman problem. To our knowledge it is […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,30,17],"tags":[],"class_list":["post-261","post","type-post","status-publish","format-standard","hentry","category-complexity","category-mirrored-on-csail-blog","category-speaking-truth-to-parallelism"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/261","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=261"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/261\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=261"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=261"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=261"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}