지수 시간 가설은 틀렸다
OpenAI 명의의 논문은 임의의 고정 절 너비 k에 대해 k-CNF의 만족 할당 수를 결정론적 부분지수 시간과 다항 공간으로 정확히 계산하는 알고리즘을 제시합니다. 이 결과가 성립하면 ETH와 SETH를 비롯한 여러 계산 복잡도 가설이 반박되지만, 일반 NP 문제 전체에 부분지수 알고리즘이 생기는 것은 아닙니다.
OpenAI 명의의 논문은 임의의 고정 절 너비 k에 대해 k-CNF의 만족 할당 수를 결정론적 부분지수 시간과 다항 공간으로 정확히 계산하는 알고리즘을 제시합니다. 이 결과가 성립하면 ETH와 SETH를 비롯한 여러 계산 복잡도 가설이 반박되지만, 일반 NP 문제 전체에 부분지수 알고리즘이 생기는 것은 아닙니다.