自明なプログラム

簡単なプログラム、あるいはもっと強く、自明なプログラムと、最適化されたプログラムとを比較して最適化されたプログラムの正しさを検証しようという話が時々ある。それはもっともなことだと思う。

が、よく考えると自明なプログラムって何だよ?という話になる。例として、DP で適当に書くと O(n2) で、頑張ると O(n) になる、組み合わせ最適化問題を考える。あまり考えていないと O(n2) が自明ということになるかもしれない。しかし、DP を使っている時点で本当に自明なのだろうか。組み合わせを列挙する指数時間アルゴリズムから始めるべきではないのだろうか。実のところ、それは微妙で、確かにアルゴリズムとしては自明かもしれないが、プログラムになると組み合わせ列挙はそこまで簡単に書けず、面倒な言語が多い。むしろ DP の方が素直にプログラムに書けたりすることの方が多く、作ってもなんか無理やりな感じになる。

結局のところ、自明なプログラムというのは恣意性が非常に高くて、工学という面ではヤラセ感が拭い切れないので、そこをどう折り合いを付けるかが大事だと思うけれど、昔いた研究室はその辺放置していた気がするなあ。。自明性の客観評価とかあってもいいかも。