거짓인 Exponential Time Hypothesis [pdf]

Hacker News 의견들 놀랍고 예상 밖의 결과지만, NP 전체가 준지수 시간에 풀린다는 뜻은 아님. 논문도 “2^o(n) 형태의 시간 상한은 일반적인 다항 시간 환원에서 보존되지 않으며, 그러려면 2^n^o(1)이 필요하므로 일반적인 NP 문제의 준지수 시간 알고리즘을 함의하지 않는다”고 명시함. 모든 NP 문제를 3SAT로 다항 시간에 환원할 수 있지만, 입력 크기도 다항식만큼 커질 수 있고 환원한 문제는 여전히 풀어야 함. 3SAT가 다항 시간에 풀린다면 다항식의 합성도 다항식이지만, 준지수 함수에 다항식을 합성한 결과가 준지수라는 보장은 없음. 다만 변수 수가 선형으로 증가하는 3SAT 환원이 가능한 문제에는 적용되는 듯함. 논문에서는 독립 집합 개수 세기, 올바른 q-색칠 개수 세기, 완전 매칭 개수 세기를 열거함. k-CNF의 해 개수를 준지수 시간과 다항 공간으로 셀 수 있다면, x_1에 0과 1을 대입했을 때의 해 개수를 각각 구하고 더 큰 쪽이나 0이 아닌 쪽을 선택하면 되지 않나? 이어서 x_2=0인 경우를 세는 식으로 진행하면 될 듯함. 그러면 k-SAT의 실제 해를 찾는 데 필요한 시간은 N×준지수 시간이고 공간은 다항 공간이 되는 것 아닌가? 상수 접기까지 하면 반복마다 N도 1씩 줄어듦. 내가 놓친 당연한 사실이 무엇인지 궁금함. 지수 시간 가설(ETH) 이 거짓이라니 놀라움. 2022년 논문에는 “강한 지수 시간 가설(SETH)이 거짓이 아니라면 자기 주의(self-attention)의 시간 복잡도는 입력 길이에 대해 반드시 이차식”이라는 결과가 있음. OpenAI의 증명이 맞다면 자기 주의를 이차 시간보다 빠르게 구현할 수 있다는 뜻인가? 결국 저렴한 하드웨어에서도 최첨단 LLM을 돌릴 수 있게 될까? 장난스럽게 표현하면 ETH가 거짓이라는 건 Nvidia에 악재인가? https://arxiv.org/abs/2209.04881 SETH가 참이면 이차 시간이라는 명제에서 SETH가 거짓이면 이차 시간이 아니라는 결론은 나오지 않음. SETH는 ETH보다 훨씬 강한 명제임. 복잡도 클래스의 분리는 정말 드문 결과임. SAT 풀이 전문가가 이 논문의 기법에 당장 쓸 만한 응용이 있는지 알려주면 좋겠음. 실제 SAT 풀이는 보통 최악의 실행 시간과 거리가 멀어서, 실용화하기 어려운 이론적 알고리즘에 해당하는 건가? SAT 풀이 전문가인데, 당장 활용할 방법은 없음. 논문의 결과는 실용적...