ハードウェアとアルゴリズムの進歩、より速いのはどちらか？

• 一般的にこの2つの進歩を比較することは不可能

• ただし、特定のアルゴリズムに限定すれば比較は可能。

• 与えられた式を満たす解が存在するかを判定する SAT 問題(https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) を基準に、アルゴリズムとハードウェアの進歩速度を比較。

• ハードウェアは Pentium III processor (467MHz) + 1.5GB RAM（1999年を代表）、Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM（2019年を代表）の2種類を比較対象とした。

• 200個のインスタンスのうち、900秒以内に解けるインスタンス数を測定することで速度を比較。

• SAT 問題に限れば、アルゴリズムの進歩はハードウェアの進歩より速い。

• 「2019年時点で最良とされるアルゴリズムである Maple SAT solver を1999年のハードウェアで使った場合、他のアルゴリズムよりわずかに解けないケースが発生した。著者たちも正確な理由は分かっておらず、おそらく優れたアルゴリズムで使われている特定のデータ構造が、現代のハードウェアにはるかに適しているのではないか、と推測している。」