문제가 실제로 더 어려워졌는가? 적대적 다중 에이전트 재작성을 통해 난이도가 높아진 쌍을 이루는 P 및 NP-완전 문제에 대한 LLM 테스트
요약
본 연구는 P와 NP-완전(NPC) 문제 쌍의 난이도 차이를 테스트하기 위해 P2NPCBench라는 새로운 벤치마크를 제안합니다. 적대적 다중 에이전트 프레임워크인 AgentGAN을 사용하여, 기존 모델들이 실패하는 방식으로 문제를 재작성하여 총 2,114개의 난이도가 높아진 진술을 생성했습니다. 테스트 결과, 모든 평가 모델은 NPC 문제에서 P 쌍둥이보다 현저히 낮은 성능을 보였습니다.
핵심 포인트
- P2NPCBench를 통해 P와 NP-완전 문제의 실제 난이도 차이를 측정함.
- AgentGAN 프레임워크로 문제를 재작성하여 기존 벤치마크의 한계를 극복함.
- 모델들은 NPC 진술에서 P 쌍둥이보다 유의미하게 낮은 성능을 보였음.
- 난이도 증가는 복잡도 클래스 차이보다는 문구 친숙도에 기인하는 부분이 많음을 시사함.
많은 NP-완전(NPC) 문제는 그래프의 3색칠하기와 2색칠하기처럼 단일 구조적 세부 사항에서 차이가 나는 다항 시간(P) 쌍둥이를 가지고 있습니다. 추론하는 모델이라면 이 경계 중 어느 쪽에 문제가 속하는지 알아차려야 하지만, 기존 벤치마크는 각 작업의 문구를 고정하거나 그 복잡도 클래스를 무시하기 때문에 두 가지를 분리할 수 없습니다. 우리는 P2NPCBench라는 벤치마크를 소개합니다. 이 벤치마크에는 12개의 문제군이 포함되어 있으며, 모든 NPC 문제는 동일한 표면 위에서 제시된 P 쌍둥이와 쌍을 이루고 있습니다. 기억에 의존하는 것을 가능하게 하는 교과서적인 단서를 제거하기 위해, 우리는 AgentGAN이라는 적대적 다중 에이전트 프레임워크로 이를 구축했습니다. 이 프레임워크에서는 생성기(generator)가 패널의 고정된 코드 모델들이 실패할 때까지 각 진술을 재작성하며, 실행 가능한 유효성 게이트(validity gate)는 모든 재작성 결과가 답변과 클래스를 보존하도록 유지합니다. 그 결과, 수동으로 검증된 참고 인간 솔버와 함께 2,114개의 난이도가 높아진 진술이 만들어졌습니다. 12개의 독점 및 오픈 소스 모델을 평가한 결과, 모든 모델이 NPC 진술에서 P 쌍둥이보다 낮은 점수를 얻는 것(35.4% 대 63.8% pass@1)을 발견했으며, 모델군 쌍의 95.1%가 NPC 측면에서 더 자주 실패한다는 것을 알았습니다. 시간 제한을 10배 늘려도 NPC 정확도는 28.5%에서 31.9%로만 증가하므로, 실패는 느린 프로그램보다는 잘못되었거나 충돌하는 프로그램에 기인합니다. 또한 난이도를 높이는 과정은 클래스 격차를 24.8점에서 14.6점으로 좁혔으며, 이는 명백한 격차의 일부가 복잡도 클래스보다는 교과서적 문구에 대한 친숙함에 반영된다는 것을 보여줍니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.CL의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기