30년 미해결 계산복잡도 논문 공개…저자 "핵심 증명은 GPT-5.6 Pro"

연구자 원문에 따르면 계산복잡도 연구자 미하일 바빈은 함의 규칙으로 정의된 유한 폐쇄 시스템과 정준 목록이 같은 대상을 표현하는지 판정하는 문제가 coNP-완전하다는 증명을 공개했다. 7월 18일 연구자료 저장소 Zenodo에 올라온 단독 저자 원고로, 학술지나 학회의 동료평가를 통과한 논문은 아니다.

폐쇄 시스템은 전체 집합을 포함하고 교집합 연산에 닫혀 있는 부분집합의 모음이다. 같은 구조를 ‘A가 있으면 b도 따라온다’는 함의 규칙으로 적을 수도 있고, 더 이상 분해하기 어려운 정준 폐쇄 집합의 목록으로 표현할 수도 있다. 문제는 두 표현이 실제로 정확히 같은 구조를 가리키는지, 특히 정준 목록에서 빠진 항목이 없는지를 효율적으로 판정할 수 있느냐는 것이다.

이 문제는 여러 연구 분야에서 서로 다른 이름으로 이어져 왔다. 1995년 로니 카돈은 혼 공식과 특성 모델 사이의 변환 문제가 정준 모델 목록의 완전성을 확인하는 판정 문제와 다항시간 환원 아래 동등하다는 결과를 제시했다. 2025년 ISAAC에 발표된 후속 연구도 비순환 함의 기저에서 기약 폐쇄 집합을 열거하는 문제의 일반적인 계산복잡도 상태가 여전히 널리 열린 문제라고 정리했다.

바빈은 이번 원고에서 함의 기저와 교집합으로 생성되는 목록이 같은 폐쇄 시스템을 정의하는지 묻는 ‘Imp–MI Equality’를 다뤘다. 저자의 주장에 따르면 이 문제는 coNP에 속하며, 3-UNSAT으로부터의 환원을 통해 coNP-난해함도 성립한다. 함의 관계가 비순환이고 각 규칙의 전제 크기가 세 개 이하인 제한된 경우에도 난해성이 유지된다는 것이 핵심이다.

결과가 검증된다면 혼 논리의 특성 모델 식별뿐 아니라 형식개념분석의 의사 의도와 뒤켄–기그 기저, 관계형 데이터베이스의 함수 종속성과 암스트롱 관계에도 영향을 준다. P와 NP가 같지 않다는 통상적인 가정 아래서는 입력과 전체 출력 크기의 다항시간 안에 모든 정준 목록을 생성하는 일반 알고리즘이 존재하지 않는다는 결론으로 이어진다. 다만 저자는 이 결과가 하이퍼그래프 횡단 집합 열거 문제 자체를 해결하지는 않는다고 범위를 제한했다.

이번 원고가 주목받는 또 다른 이유는 인공지능 사용 공개 문구다. 바빈은 핵심 증명을 ChatGPT에서 OpenAI의 GPT-5.6 Pro가 도출했고 자신이 이를 검토했다고 밝혔다. 수학적 주장과 최종 원고의 책임은 저자에게 있다고 명시했다. 논문에는 환원의 구성과 보조정리, 분야별 결과 이전 과정을 포함한 증명 전문이 실려 있다.

그러나 ‘AI가 30년 난제를 해결했다’고 확정하기에는 검증 단계가 남아 있다. 현재 공개된 자료는 단독 저자가 Zenodo에 올린 원고이며 독립적인 동료평가나 재현 검토 결과는 확인되지 않는다. GPT-5.6 Pro의 기여 방식도 대화 기록이나 별도 검증 자료가 공개되지 않아 저자의 공개 문구 이상으로 판단할 수 없다. 이번 결과의 학술적 효력은 관련 분야 연구자들이 환원과 분야별 귀결을 검토한 뒤 평가해야 한다.

출처: Zenodo 연구 원고 https://zenodo.org/records/21431468
출처: ISAAC 2025 논문 https://doi.org/10.4230/LIPIcs.ISAAC.2025.24
출처: Roni Khardon 1995년 원논문 https://arxiv.org/abs/cs/9512105