Exponential Time Hypothesis

Definition

• 이며, . 역방향은 증명되지 않음. ETH가 거짓이어도 P=NP가 증명되는 것은 아님.

• 3-SAT는 NP-complete. 모든 NP 결정 문제를 다항시간에 3-SAT로 환원할 수 있으므로, 3-SAT를 다항시간에 풀면 .

• NP-hardness는 다항시간 환원을 사용하지만 ETH 기반의 정밀한 시간 하한에는 환원 후 입력 크기의 증가도 중요함.

2026-10-26: OpenAI의 ETH 반증 주장 (검증 진행 중)

• 논문 시간 상한: , 다항 공간. 은 절(clause) 수.

• 공개 Lean 형식화는 이보다 다소 약한 상한을 검증하지만 여전히 이며, ETH를 반박하기에 충분한 형태.

• 상태 (2026-10-27): OpenAI가 원고와 Lean 코드를 공개했지만 Impagliazzo·Paturi·Williams 등이 이끄는 외부 독립 검토는 진행 중. 학계 최종 검증 완료로 단정하지 않음.

• 의미: ETH/SETH 기반 조건부 하한 재검토 가능. 다항시간 3-SAT, , RSA/ECC의 실용적 해독은 이 결과만으로 입증되지 않음.

Working with academic communities to build scientific understanding

OpenAI shares model results on the Kakeya conjecture, Exponential Time Hypothesis, and quantum chromodynamics—and how researchers can verify and build on them.

https://openai.com/index/building-scientific-understanding-with-academic-communities/