보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
핵심 사실(Fagin·Immerman–Vardi·순서 구조 위 동치·CFI·Chandra–Harel/Gurevich·CPT·대칭 회로 문헌)은 정확하다. 고칠 것은 (1) 「Gurevich 추측」의 방향, (2) 「순서가 주어지면 자기동형이 사라져서 기법이 무력화된다」는 원인 설명, (3) 「두 프론트가 만나는 지점 = P vs NP 해결」의 조건 누락, (4) 장벽 관련 단정문이다.
확인한 사실
| 주장 | 사실 여부 | 근거 |
|---|---|---|
| Fagin 정리: NP = ∃SO | 맞음 — Fagin 1974, 순서 불필요 | Descriptive complexity (Wikipedia) |
| Immerman–Vardi: 순서 구조 위 P = FO(LFP) | 맞음 — Immerman 1982/1986, Vardi 1982 | 위와 같음 |
| 순서 구조 위 FO(LFP) 와 ∃SO 분리 ⇔ P ≠ NP | 맞음 | 위와 같음 |
| 순서가 주어지면 자기동형이 사라져 페블 게임·CFI 등 기법이 무력화 | 원인 설명 부정확 — 선형 순서가 있는 구조는 강성(자기동형 없음)인 것이 맞지만, 기법이 무력해지는 이유는 순서가 있으면 FO(LFP)가 P 전체를 표현해서(Immerman–Vardi) 하한이 곧 P 하한이 되기 때문이다. 순서 없는 강성 구조에서도 순서를 정의할 수 없으면 사정이 다르다. 페블 게임·CFI 는 자기동형이 아니라 「비동형 구조 쌍을 구별하지 못함」을 이용한다 | 위와 같음 |
| 순서 없는 구조에서 P 를 포획하는 논리 문제 = Chandra–Harel/Gurevich 문제, CPT 가 유력 후보 | 맞음 — Chandra–Harel 1982, Gurevich 1988. CPT 는 Blass–Gurevich–Shelah 1999. 또 다른 후보였던 순위 논리는 Lichter(LICS 2021)가 P 와 분리 | Pago 2023 서론 |
| 「순서 없는 구조에서 P를 포획하는 논리의 존재 여부」(Gurevich 추측) | 표현 부정확 — Gurevich 추측은 「그런 논리는 없다」이다. 이 추측이 참이면 Fagin 정리에 의해 P ≠ NP | Pago 2023 서론 |
| CPT 지지 정리(Blass–Gurevich–Shelah) | 맞음 — BGS 1999 의 작은 지지 결과(CPT 무카운팅은 짝수성 정의 불가). Rossman 2010 이 확장 | — |
| 대칭 회로 하한(Anderson–Dawar, Dawar–Wilsenach) | 맞음 — Anderson–Dawar(STACS 2014, ToCS 2017): 대칭 P-균일 회로 = FPC, Dawar–Wilsenach(CSL 2018, ICALP 2020) | — |
| CFI 문제·유한체 위 선형방정식계가 FPC 를 P 와 분리 | 맞음 — Cai–Fürer–Immerman 1992, Atserias–Bulatov–Dawar(TCS 2009) | — |
| 배제 마이너·유계 랭크폭 클래스의 포획 결과 | 맞음 — Grohe(J. ACM 2012/저서 2017) 배제 마이너에서 FPC 가 P 포획, Grohe–Neuen(LICS 2019) 유계 랭크폭. 둘 다 FPC 포획이며 FPC ⊆ CPT 이므로 CPT 에도 성립 | — |
| 어떤 NP 완전 문제의 CPT 정의불가능성은 중대한 미해결 문제 | 맞음 — CPT 에 대한 강한 하한은 아직 없음(Pago 2023 도 CFI 질의에 대한 부분 결과) | Pago 2023 |
| 대칭 회로·CPT 하한은 「largeness 조건을 우회하는 것으로 관찰된다」 | 근거 표기 없음 — 이 관찰의 출처가 없다. 더 정확히는, 대칭 회로·CPT 가 다루는 대상이 동형 불변 질의라 Razborov–Rudich 틀(임의 불리언 함수 위의 large 성질)이 직접 적용되지 않는다 | — |
| 표현력 하한은 오라클 문장으로 진술되지 않으므로 상대화 장벽이 적용되는 형태의 논증이 아니다 | 과장 — 순서 구조 위 분리는 P ≠ NP 와 정확히 동치이므로, 그 분리를 증명하는 논증은 무엇이든 비상대화여야 한다. 논리로 다시 쓴다고 장벽이 사라지지는 않는다(장벽 표에서는 「7단계에서 점검」이라고만 했는데 「왜」 첫 항목은 단정) | Aaronson–Wigderson |
| 두 프론트가 만나는 지점이 곧 P vs NP 의 해결 지점 | 조건 누락 — 그 단의 구조 클래스에서 ① 그 논리(CPT 등)가 P 를 포획하고 ② 목표 문제가 그 클래스로 제한해도 NP 완전일 때만 P ≠ NP 가 따라온다(예: 평면 그래프는 FPC 가 P 를 포획하고 평면 3-채색은 NP 완전) | — |
고칠 곳
- 핵심 정리 2번째 줄·개요 첫 문단
- 원문: 「장벽: 순서가 주어지는 순간 자기동형이 사라져 페블 게임·Cai–Fürer–Immerman 구성 같은 논리적 하한 기법이 무력해진다.」
- 제안: 「장벽: 순서가 주어지면 FO(LFP)가 P 전체를 표현하므로(그때 구조는 자기동형도 없다), 페블 게임·Cai–Fürer–Immerman 구성처럼 구별 불가능한 구조 쌍을 만드는 논리적 하한 기법이 곧 P 하한이 되어 버려 지금의 기법으로는 닿지 않는다.」
- 「왜」 4번째 항목
- 원문: 「"순서 없는 구조에서 P를 포획하는 논리의 존재 여부"(Gurevich 추측)」
- 제안: 「"순서 없는 구조에서 P를 포획하는 논리가 존재하는가"(Gurevich 는 존재하지 않는다고 추측했고, 그 추측이 참이면 Fagin 정리에 의해 P ≠ NP)」
- 「왜」 5번째 항목 끝
- 원문: 「두 프론트가 만나는 지점이 곧 P vs NP의 해결 지점이다.」
- 제안: 「두 프론트가 같은 구조 클래스에서 만나고 — 그 클래스에서 논리가 P 를 포획하며 목표 문제가 여전히 NP 완전이라면 — 그 지점이 곧 P vs NP 의 해결 지점이다.」
- 「왜」 1번째 항목·장벽 표 「상대화」 칸
- 원문: 「표현력 하한은 오라클 문장으로 진술되지 않으므로 상대화 장벽이 적용되는 형태의 논증이 아니다.」
- 제안: 「표현력 하한은 오라클 문장으로 진술되지 않아 상대화 장벽을 피할 여지가 있다고 본다. 다만 순서 구조 위 분리는 P ≠ NP 와 정확히 동치이므로, 그것을 증명하는 논증은 결국 비상대화여야 한다.」
- 「왜」 2번째 항목·장벽 표 「자연 증명」 칸
- 원문: 「지금까지의 증명들은 largeness 조건을 우회하는 것으로 관찰된다.」
- 제안: 「대칭 회로·CPT 가 다루는 것은 동형 불변 질의라 Razborov–Rudich 틀이 직접 적용되지 않는다고 본다(이 글의 판단).」
- (선택) 개요의 「입력 구조의 자기동형군이 얼마나 풍부한지를 매개변수로」 옆에, 대칭 회로 하한이 쓰는 「대칭」은 입력 구조의 자기동형군이 아니라 정점 이름바꾸기(대칭군 S_n)에 대한 회로의 불변성이라는 점을 한 줄 밝혀 두면 2단계 매개변수 설계와 혼동이 없다.
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.