하드웨어와 알고리즘 발전중 어느쪽이 더 빠를까?

- 일반적인 두 발전을 비교하는 것은 불가능
- 하지만 특정 알고리즘으로 한정한다면 비교가 가능할 것.
- 주어진 식을 만족하는 해가 존재하는지 판별하는 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년을 대표), 두가지가 비교대상.
- 200개의 인스턴스중 900초안에 풀리는 인스턴스의 개수를 측정함으로써 속도를 비교.

- SAT 문제에 한해서는, 알고리즘의 발전이 하드웨어 발전보다 빠르다.

- "2019년에 가장 좋은 알고리즘으로 알려진 Maple SAT solver가 1999년 하드웨어를 쓴 경우 다른 알고리즘보다 약간 더 못푸는 경우가 발생했다. 저자들도 정확한 이유를 알지는 못하고, 아마 좋은 알고리즘에서 사용한 특정한 자료구조가 현대 하드웨어에 훨씬 적합한게 아닐까.. 같은 추측을 한다."