Exponential Time Hypothesis

지수 시간 가설

3-SAT 같은 k-SAT 문제를 준지수 시간에 풀 수 없다고 보는 계산 복잡도 이론의 추측이다.

기사 1편최근 언급

Exponential Time Hypothesis(ETH, 지수 시간 가설)는 변수가 n개인 3-SAT 문제를 2^{o(n)} 시간, 곧 준지수 시간에 푸는 알고리즘이 없다는 계산 복잡도 이론의 추측이다. 1990년대 말 Russell Impagliazzo와 Ramamohan Paturi가 k-SAT의 복잡도를 다룬 연구에서 제안했고, Francis Zane과 함께 발표한 후속 연구의 희소화 보조정리(sparsification lemma)를 통해 여러 문제에 적용할 수 있게 됐다.

ETH는 P ≠ NP보다 강한 가정이다. P ≠ NP는 NP-완전 문제에 다항 시간 알고리즘이 없다는 주장이고, ETH는 지수 시간보다 의미 있게 빠른 알고리즘조차 없다고 본다. 이 가정을 전제로 그래프 문제, 매개변수화 복잡도, 세밀 복잡도(fine-grained complexity) 등 여러 분야에서 조건부 하한이 도출됐다. 3-SAT를 2^{(1-ε)n} 시간에 풀 수 없다는 더 강한 추측은 강한 지수 시간 가설(SETH)이라 부른다.

이 설명은 AIPOST 기사와 널리 알려진 사실을 바탕으로 정리했습니다. 잘못된 내용이 있으면 정정 요청으로 알려 주세요.

이 항목을 다룬 기사

  • OpenAI의 AI가 ETH 반증, P 대 NP와 암호 체계는 어떻게 되나AI 뉴스 ·

    AI 모델이 계산 복잡도 이론의 기둥으로 여겨지던 Exponential Time Hypothesis(ETH, 지수 시간 가설)를 반증했고, 그 증명이 Lean(컴퓨터가 증명의 논리를 한 단계씩 검사하는 정리 증명 보조 도구)으로 형식 검증까지 마쳤다는 내용입니다.

    기사 읽기

설명이 잘못되었거나 찾는 항목이 없나요?

위키 설명은 AIPOST 기사와 널리 알려진 사실을 바탕으로 정리합니다. 잘못된 설명은 정정 요청으로 알려 주시면 확인해 고칩니다. 새 기사에 나온 이름은 기사가 올라온 뒤 위키에 더해집니다.