본 논문은 신경망의 효율성에 중요한 요소로 여겨지는 중첩(superposition) 현상의 계산 이론적 기반을 조사하여 명시적이고 증명 가능한 정확한 알고리즘에 대한 복잡도 한계를 설정합니다. 특히, 중첩 상태에서 계산하는 신경망에 대한 최초의 하한선을 제시하며, 순열 및 쌍별 논리 연산을 포함한 광범위한 문제에 대해 $m'$개의 특징을 중첩 상태로 계산하려면 적어도 $\Omega(\sqrt{m' \log m'})$개의 뉴런과 $\Omega(m' \log m')$개의 파라미터가 필요함을 보입니다. 이는 중첩 용량에 대한 최초의 아지수적(subexponential) 상한선, 즉 $n$개의 뉴런을 가진 네트워크는 최대 $O(n^2 / \log n)$개의 특징을 계산할 수 있음을 의미합니다. 반대로, 거의 근접한 구성적 상한선을 제공하며, 쌍별 AND와 같은 논리 연산은 $O(\sqrt{m'} \log m')$개의 뉴런과 $O(m' \log^2 m')$개의 파라미터를 사용하여 계산될 수 있음을 보입니다. 따라서 중첩 상태에서의 계산(본 연구의 주제)의 복잡성과 Johnson-Lindenstrauss Lemma에 기반하여 $O(\log m')$개의 뉴런만 필요할 수 있는 특징 표현 간에는 기하급수적인 차이가 있습니다. 연구진은 이 결과가 신경망 해석성 연구에 복잡도 이론적 기법을 사용하는 길을 열어줄 것이라고 기대합니다.
