알고리즘서지만 확인
On the Complexity of k-SATRussell Impagliazzo, Ramamohan Paturi · 2001Journal of Computer and System Sciences 62(2), 367–375쪽 (2001) · 학회 발표 CCC 1999 (Fourteenth Annual IEEE Conference on Computational Complexity), 237–240쪽 — 학회판 제목은 「Complexity of k-SAT」3-SAT 는 변수 수의 지수보다 본질적으로 빠르게 풀 수 없다는 지수 시간 가설(ETH)의 출전으로 널리 인용된다. ETH 는 P ≠ NP 보다 강한 가설이다. P ≠ NP 는 「다항 시간에 안 된다」만 말하지만 ETH 는 「2^(o(n)) 시간에도 안 된다」고 말한다. 세밀한 복잡도와 매개변수 알고리즘의 하한이 이 가설에 기대므로, P ≠ NP 너머의 가설을 소개하는 글에 필요하다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 서지를 확인했다(본문은 열지 못함).