Conversation

https://qiita.com/iKodack/items/d606a09f0a40b95bf2b6
ウィンタースクール始まって朝の余裕ができたのでちょっとこれ真面目に考えてみたんだけど、やっぱりここで言ってるTSPはわたしの知ってる(Wikipediaみても一般的だと思う)「最短経路を求める」ではなくて「あるKに対してK以下になる経路がるかどうか判定する」となっていて、後者から前者はKを下げる手順を繰り返すことで求められるけど、宇宙破壊コンピュータでは「K以下になる経路がない」場合には全宇宙が破壊されるため、これは計算が終わらないのと同等なのではないかという気がする。と、思ったのだがコメントでそのへんの詳しい解説があった。やっぱりこの本文では不完全なんだな。