원문 보완판 — 사실 검토 반영

P≠NP 를 증명하려면 결국 다항 시간 알고리즘 전부를 배제해야 한다. 이 글은 그 전 단계로, 지금 알려진 가장 강력한 알고리즘 패러다임을 무조건적으로 배제하는 SoS 하한들을 부품으로 다시 짜 보자고 제안한다.

아이디어 개요

P≠NP를 증명하려면 결국 "다항 시간 알고리즘 전부"를 배제해야 하지만, 그 전 단계로 "현재 알려진 가장 강력한 알고리즘 패러다임 전부"를 무조건적으로 배제하는 일은 지금 당장 가능한 영역이다. Sum-of-Squares(SoS)/Lasserre 위계는 스펙트럴 방법, LP·SDP 완화, 그리고 조합 최적화의 대다수 근사 알고리즘을 하나의 준정부호 계획 위계로 포섭하는 통일 모델이며, 이 모델에 대한 차수·크기 하한은 그 위계로 표현되는 알고리즘들(해당 차수 이하)의 실패를 뜻한다. 스펙트럴 방법 전반이 저차 SoS 로 포획된다는 것은 많은 사례에서 확인된 경향이지 일반 정리는 아니다. 실제로 Grigoriev(2001, 패리티·3-XOR)와 Schoenebeck(2008, 3-SAT 포함)의 선형 차수 하한, 유사보정(pseudo-calibration)에 의한 심은 클리크(planted clique) 하한, Lee–Raghavendra–Steurer(LRS, STOC 2015)의 SDP 확장 정식화 하한처럼 "최대 CSP 근사와 cut·TSP·안정 집합 다면체에 대해 다항 크기 SDP 완화 전부"(대칭성 가정 없음)를 배제하는 무조건적 결과들이 이미 축적되어 있다.

본 아이디어는 이 성과들을 P vs NP 공략의 부품으로 재조립하는 프로그램이다. 즉 (1) 차수 하한을 크기 하한으로 승격하는 기계장치를 정비하고, (2) Raghavendra류 최적성 정리를 일반화해 "SoS가 어떤 알고리즘 클래스 C 안에서 최적인가"의 경계를 명확히 하며, (3) SoS를 준대수적(semialgebraic) 증명 체계로 보아 Cook–Reckhow 프로그램(NP≠coNP 경로)의 크기 하한 트랙으로 연결한다.

구체적 진행 방법

1. 기초 문헌 정독: Lasserre·Parrilo의 위계 정식화, Grigoriev의 패리티·냅색 차수 하한, Schoenebeck의 무작위 k-SAT 하한, Barak 등(BHKKMP)의 심은 클리크 유사보정 논문, Raghavendra의 UGC 하 CSP 최적성 정리, LRS의 SDP 확장 정식화 하한, Kothari–Meka–Raghavendra의 LP 하한, 그리고 Fleming–Kothari–Pitassi의 준대수 증명·알고리즘 설계 서베이를 정독하고, 각 결과의 가정(대칭성, 분포, 술어 종류)과 결론 강도를 한 장의 표로 정리한다.
2. 차수-크기 대장 작성: 알려진 하한을 "차수 하한인가, 크기 하한인가(SDP 확장 정식화의 차원과 증명 체계의 단항식 수를 구분하고, 비트 복잡도는 별도 축으로 둔다)" 기준으로 분류하고, LRS 기계장치가 차수 하한을 어떤 손실로 일반 SDP 의 크기 하한으로 변환하는지, 대칭성 가정이 필요했던 이전 결과(Lee–Raghavendra–Steurer–Tan, CCC 2014)와 무엇이 달라졌는지 명세화한다. 중간 마일스톤: LRS 하한이 덮지 않는 문제군과 크기 지수(2^(n^δ))의 손실을 서술한 기술 노트.
3. 유사보정 템플릿화: 심은 분포 대 귀무 분포 설정, 저차수 우도비(low-degree likelihood ratio) 휴리스틱과의 대응을 포함한 유사보정 절차를 재사용 가능한 표준 템플릿으로 문서화하고, 기존 하한 두어 개(심은 클리크, 무작위 CSP)를 템플릿 안에서 재증명해 검증한다.
4. 최적성 경계 규명: "클래스 C의 어떤 알고리즘도 기저 SoS 완화보다 낫지 않다"는 형태의 최적성 정리들을 수집해, UGC 같은 가정이 필요한 구간과 무조건적으로 성립하는 구간을 구분한 지도를 만든다. 중간 마일스톤: 무조건적 최적성이 성립할 법한 클래스 C 후보(예: 특정 대칭성·국소성을 가진 알고리즘군)에 대한 정밀 추측 목록.
5. 증명 복잡도 다리 놓기: SoS를 정적 Positivstellensatz 반박 체계로 정식화하고, NP 완전 문제의 자연스러운 부호화 식 계열에 대한 초다항 크기 하한이 Cook–Reckhow 관점에서 정확히 어떤 진전에 해당하는지, 기존 트랙(프레게 계열, IPS)과 겹치지 않는 준대수 축의 위치를 명시한다. 무작위 3-CNF·Tseitin 식에 대한 SoS 지수 크기 하한은 Atserias–Hakoniemi(CCC 2019)의 크기-차수 절충과 Grigoriev·Schoenebeck 차수 하한으로 이미 알려져 있다.
6. 장벽 감사: SoS 하한이 상대화·자연 증명·대수화 장벽 각각과 어떤 관계인지 문서화한다. 특히 이 하한들이 구체적 계산 모델에 대한 것이라 오라클 논법에 걸리지 않는 이유, 회로 하한이 아니어서 자연 증명 장벽의 직접 사정권 밖에 있는 이유, 반대로 프로그램을 회로 하한으로 승격하는 순간 장벽권에 재진입하는 지점을 구간별로 표시한다.
7. 부품 정리 도출: 앞 단계들을 결합해 "SoS가 클래스 C에서 최적이고, NP 완전 문제 X가 SoS에서 초다항 크기를 요구하면, C는 X를 풀 수 없다"는 형태의 조건부 부품 정리를 최대한 약한 가정으로 정식화하고, 남은 가정 각각을 독립 미해결 문제로 분리해 공개한다.
8. 역방향 산출물 회수: 하한 시도가 실패한 사례에서 유사보정이 깨지는 방식을 분석해 저차수 구별자, 즉 새 알고리즘 후보를 추출하는 절차를 병행 운영한다. 실패조차 알고리즘 쪽 성과로 회수되도록 파이프라인을 닫는다.

왜 해볼 만한 가치가 있는가

1. 무조건적 성과의 축적: 이 경로의 중간 결과는 가정 없는 정리다. LRS형 하한은 "다항 크기 SDP 완화 전부의 실패"라는, P≠NP의 축소판이라 할 만한 무조건적 배제를 실제로 달성했고, 같은 종류의 확장(더 넓은 문제군, 더 강한 크기 지수)은 그 자체로 일급 성과가 된다. P vs NP가 끝내 미해결이어도 손실이 없다.
2. 장벽 프로필이 유리하다: 이 글은 SoS 하한이 특정 구체 모델에 대한 조합적·스펙트럴 논증이므로 오라클을 타지 않아 상대화 장벽과 무관하고, 회로에 대한 판별 성질을 만들지 않으므로 자연 증명 장벽의 직접 적용 대상도 아니라고 본다. IP=PSPACE의 산술화가 상대화 장벽 밖에서 작동했듯(산술화 자체는 대수화 장벽 안에 있다) "장벽 밖에서 실제로 작동하는 기법"을 키우는 일이라고 본다. 장벽권 재진입 지점을 6단계에서 미리 지도화하므로 낭비를 줄인다.
3. 알고리즘·하한 양면 보상: SoS에서는 하한 증명 실패가 곧 새 알고리즘의 단서가 되는 쌍대성이 실제로 작동해 왔다(강건 통계·텐서 분해 등에서의 SoS 알고리즘 발굴). 8단계의 회수 절차 덕분에 프로그램의 어느 가지도 헛수고로 끝나지 않는다.
4. 평균 사례·암호와의 접점: 유사보정과 저차수 방법의 대응은 심은 문제의 평균 사례 난이도와 연결되며, 원웨이 함수류 가정과도 이어질 수 있다는 것이 이 글의 기대다. 본 프로그램의 산출물은 평균 사례 복잡도와 암호학적 하한 연구에 그대로 재사용된다.
5. 기존 등록 아이디어와의 상보성: 게시판의 프레게 트랙이 카운팅 명제 증명 체계를 공략한다면, 본 프로그램은 준대수 증명 체계와 볼록 완화 알고리즘 클래스라는 다른 축을 맡아 Cook–Reckhow 프로그램을 두 방향에서 협공한다. UGC(유일 게임 추측)의 지위를 명확히 하는 부수 효과도 있어, 어느 쪽으로 결론이 나든 근사 복잡도 지형 전체가 선명해진다.