やったこと

Marktoberdorf

引き続きSAT関連の話が多い。
ただ、より詳細に踏み込んできたので面白くなってきた気がする。
とくに、グラフっぽい問題をSATにエンコードして解決する話は興味深かった。
点が何個あれば凸n角形 ($n$-gon) が作れるかという問題や、逆に何点あっても凸n角形で中に余計な点を含まないもの ($n$-hole) が作れるかという問題 ($n\ge7$ だとそもそも無理らしい) をSATで解決していた。
ソートした3点の配置の関係でエンコードするらしい。

研究

arXiv版が公開されていた。
よろしくお願いします。

https://arxiv.org/abs/2508.04458