きくちさんの blog on SuperCon http://www.cp.cmc.osaka-u.ac.jp/~kikuchi/weblog/index.php?UID=1154518741
予選問題を見ると (これ)巡回セールスマン問題っぽい。Simulated Annealing とか Genetic Algorithm とかで解くという感じでしょうね。本選問題はたんぱく質のフォールディングとかかな？予選問題も複数のピン止めサイトがある Self Avoiding Loop の基底状態探索、という解釈が可能。
追記：きくちさんのライバルだったという人はこの方と見た http://mono.kmc.gr.jp/~oxy/d/?date=20060803
やはり多項式時間では無理っぽいのか。しかし二次元±J Ising Model は基底状態を求める多項式時間アルゴリズムが存在するから、どうかな。
本戦問題の公表はまだかなあ http://www.gsic.titech.ac.jp/supercon/supercon2006/problem.pdf
