arXiv cs.AI

アルゴリズム類似性の測定に向けて

Towards a Measure of Algorithm Similarity

http://arxiv.org/abs/2510.27063v1


本論文では、同じ問題に対する二つのアルゴリズムがどの程度異なるのかを判断することの難しさを扱っています。この問題は一般的には計算不可能であり、相似性の概念も多岐にわたります。しかし、クローン検出やプログラム合成などの応用分野では、実用的かつ一貫した相似性の指標が必要です。著者たちは、既存の等価性や相似性の概念をレビューし、EMOC(評価-記憶-操作-複雑性)というフレームワークを提案します。このフレームワークはアルゴリズムの実装を特徴空間に埋め込み、クラスタリングや分類、近似重複の検出、LLMによって生成されたプログラムの多様性の定量化に役立ちます。また、PACDという確認済みのPython実装からなるデータセットも構築し、再現性を促進するためにEMOCの埋め込み計算に必要なコードやデータが公開されています。