본 논문은 대규모 언어 모델(LLM)의 추론 능력 평가를 위한 새로운 벤치마크인 비결정적 다항시간 문제 챌린지(NPPC)를 제안합니다. 기존 벤치마크의 한계인 빠른 성능 저하 및 취약성 문제를 해결하기 위해, NPPC는 25가지 잘 알려진 NP-완전 문제를 통합 인터페이스로 제공하는 npgym, 온라인 및 오프라인 모델 평가를 위한 npsolver, 그리고 LLM 성능 분석을 위한 npeval의 세 가지 모듈로 구성됩니다. 실험 결과, NPPC는 최첨단 LLM의 성능을 10% 미만으로 낮추는 등, '깨지지 않고(uncrushable)', '해킹되지 않는(unhackable)', '자동 검증 가능하고(auto-verifiable)', '범용적인(general)' 벤치마크로서의 기능을 성공적으로 입증했습니다. DeepSeek-R1, Claude-3.7-Sonnet, o1/o3-mini 등이 우수한 성능을 보였으며, 특히 DeepSeek-R1이 대부분의 NP-완전 문제에서 가장 뛰어난 성능을 나타냈습니다. 또한, 고급 LLM에서 토큰 수와 'aha moment'는 문제의 난이도가 증가함에 따라 증가하다가 감소하는 경향을 보였습니다. NPPC는 인공 일반 지능(AGI)을 향한 LLM의 척도로서, 최초의 '끊임없이 확장되는(ever-scaling)' 추론 벤치마크가 될 것으로 기대됩니다.
