지수 시간 가설은 거짓이다 [PDF]

모든 고정된 (k\ge2)에 대해 k-CNF의 만족 할당 수를 준지수 시간과 다항 공간으로 정확히 계산하는 결정적 알고리듬을 제안하며, 이를 통해 ETH를 반증한다고 주장하는 논문임 핵심은 변수들을 작은 그룹으로 나누고, 그룹 사이의 의존성을 소수의 공유 선형 요약값으로 제한하는 것임. 요약값을 고정하면 각 그룹의 기여를 독립적으로 합산할 수 있음 원래 계수 문제를 다항식 (H(0))의 계산으로 바꾸고, 계산하기 쉬운 다른 지점의 Taylor 계수와 Hermite 보간으로 복원함 정리의 일반 입력 시간 상한은 ((n+m)^{O_k(1)}2^{O_k(n\log\log n/\sqrt{\log n})})이며, 절 수가 변수 수에 비례하면 지수부를 (O_{k,D}(n/\sqrt{\log n})) 로 줄임 적용 범위는 고정된 절 너비 (k) 임. 일반적인 다항 시간 환원은 이 준지수 시간 상한을 보존하지 않으므로, 모든 NP 문제의 준지수 시간 알고리듬을 뜻하지는 않음 정확한 만족 할당 계수와 시간 상한 입력은 선언된 변수 (n)개와 절 (m)개로 구성된 k-CNF이며, 목표는 이를 만족하는 불리언 할당의 수 (#F)를 정확히 계산하는 것임 (k)는 (n)이 커져도 고정하며, 리터럴을 반복해 길이가 (k)보다 짧은 절도 표현함 (#F>0)인지 검사하면 만족 가능성도 결정할 수 있음 정리 1.1은 고정된 (k\ge2), (n\ge20)에 대해 다음 비트 연산 및 공간 상한을 제시함 일반 입력에서는 ((n+m)^{O_k(1)}2^{O_k(n\log\log n/\sqrt{\log n})}) 비트 연산이 필요함 고정된 (D>0)에 대해 (m\le Dn)인 입력에서는 ((n+m)^{O_{k,D}(1)}2^{O_{k,D}(n/\sqrt{\log n})}) 비트 연산이 필요함 공간 상한은 ((n+m)^{O_k(1)})비트임 유리수 보간을 사용하는 6.4절의 지수부는 더 약한 (O_k(\rho(n)))이며, (\rho(n)=n(\log\log n)^2/\sqrt{\log n})임 부록 D는 텐서 축약으로 정리 1.1의 두 시간 상한을 증명하는 구성을 담음 계산량은 산술 연산 수와 비트 연산 수를 구분함. 정수는 부호 있는 이진수로, 유리수는 정수 분자와 양의 정수 분모로 저장하며 공간도 비트 단위로 측정함 해 탐색, 균일 표본 추출, Max-k-SAT 정확한 계수 알고리듬으로 만족 할당 탐색과 정확한 균일 무작위 추출도 수...