OpenAI의 증명을 단순화해 ETH가 거짓임을 보인 논문
A simplified proof of ETH is False [pdf]
Shiva Kintali가 OpenAI의 증명을 단순화해 ETH(지수 시간 가설)를 반박하는 논문을 공개했다. 고정된 ε > 0마다 3-SAT을 2^εn 시간에 푸는 결정론적 알고리즘을 제시하며, 이는 ETH의 표준 정식화와 모순된다. 희소화, 발생 횟수 제한, 스펙트럼 치환, 유리 보간을 결합한 구성으로, 변수들을 그룹으로 분리하고 다항식 보간으로 해의 개수를 복원한다.
Theorem 1.1 contradicts this assertion by taking, for example, ε = δ/2.