보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
인용한 정리(Berman–Hartmanis, Mahaney, Fortune, Ogihara–Watanabe, Karp–Lipton, Ladner, Schöning, Joseph–Young, Kurtz–Mahaney–Royer, Fenner–Fortnow–Kurtz)는 저자·연도·명제가 대부분 맞다. 동형 추측을 「추측」, Mahaney·Ladner 를 「정리」로 그림 설명에서 갈라 둔 것도 좋다. 고칠 것은 장벽 판단의 앞뒤 모순 하나와 공로·용어 표기 몇 곳이다.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 |
|---|---|---|
| Berman–Hartmanis 동형 추측(1977): 모든 NP 완전 집합은 다항시간 동형 | 맞음 (SIAM J. Comput. 1977, STOC 1976) | https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture |
| P=NP 이면 유한 집합까지 NP 완전이 되어 SAT 와 동형일 수 없으므로 추측이 참이면 P≠NP | 맞음 (P=NP 이면 ∅·Σ* 를 뺀 P 의 모든 집합이 다대일 NP 완전) | https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture |
| 추측의 귀결: 희소 NP 완전 집합은 없다 | 맞음 (동형이면 SAT 와 같은 지수 밀도) | https://en.wikipedia.org/wiki/Mahaney%27s_theorem |
| Mahaney(1982): 다대일 기준 희소 NP 하드 집합이 있으면 P=NP | 맞음 (JCSS 1982). NP 에 속할 필요 없는 하드 집합판도 성립 | https://en.wikipedia.org/wiki/Mahaney%27s_theorem |
| Fortune: 희소 coNP 하드 집합이면 P=NP | 맞음 (Fortune, SIAM J. Comput. 1979) | https://en.wikipedia.org/wiki/Mahaney%27s_theorem |
| Ogihara–Watanabe: left-set 논법, btt 환원 확장 | 맞음 (SIAM J. Comput. 1991: SAT ≤btt 희소 ⇒ P=NP) | https://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf |
| Karp–Lipton: Turing 칸은 PH 붕괴 | 맞음 (NP ⊆ P/poly ⟺ SAT ≤T 희소, 이때 PH = Σ2) | https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem |
| 「Cai 의 S2p 강화」 | 공로 표기 부정확 — Karp–Lipton 붕괴를 S2P 까지 내린 것은 Sengupta 가 처음 관찰했고(Cai 논문에 수록), Cai 의 기여는 S2P ⊆ ZPP^NP 다. doc 22 는 같은 결과를 「Sengupta 의 S2P 버전」으로 적어 두 글이 어긋난다 | https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem · https://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.html |
| Ladner(1975): P≠NP 면 NP 중간 문제 존재, 환원 차수가 「조밀한 무한 격자」 | 앞 절반 맞음. 「격자(lattice)」는 부정확 — Ladner 가 보인 것은 계산 가능 집합의 다항시간 차수 구조가 조밀하다는 것이고, 그 구조는 상반격자(upper semilattice)이지 모든 쌍에 하한(meet)이 있는 격자가 아니다 | https://projects.csail.mit.edu/jacm/References/ladner1975:155.html · https://www.cs.auckland.ac.nz/~nies/talks/2017/NiesRodfestDegrees.pdf |
| Schöning 의 균일 대각화 | 맞음 (TCS 1982) | https://en.wikipedia.org/wiki/Ladner%27s_theorem |
| Hemaspaandra–Ogihara, Complexity Theory Companion 희소집합 장 | 맞음 (Springer 2002, 1장 자기 환원성 기법에서 Mahaney·Ogihara–Watanabe·Fortune 를 다룸) | https://www.cs.rochester.edu/~lane/low-information-sets.html |
| 다대일·btt 칸 P=NP 붕괴, 무제한 tt 는 미해결 전선(Arvind 등) | 대체로 맞음. 다만 ctt·dtt(접속·이접 tt) 칸은 이미 결과가 있다(Arvind 외 1993 「Reductions to sets of low information content」, Cai–Naik–Sivakumar 1995 dtt 희소 하드 ⇒ P=NP 계열). 3단계의 「로그 이하 질의 tt」를 미해결 칸으로 삼기 전에 이 선행 결과와 대조할 것 | https://uni-ulm.de/?id=40303 · https://ar5iv.labs.arxiv.org/html/cs/0011019 |
| Joseph–Young: k-creative 집합, 일방향 함수가 있으면 암호화된 완전 집합이 비동형일 수 있다 | 맞음(추측·시나리오로 적혀 있음, TCS 1985) | https://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf |
| Kurtz–Mahaney–Royer: 무작위 오라클 상대로 추측 실패 | 맞음 (JACM 1995) | https://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf |
| Fenner–Fortnow–Kurtz: 추측이 성립하는 오라클 | 맞음 (JCSS 1996) | https://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf |
| 「동형 추측의 유력 반례 시나리오가 일방향 함수의 존재와 직결」 | 지나친 단정 — Rogers(JCSS 1997)는 일방향 함수가 있으면서 동형 추측이 성립하는 오라클을 만들어 네 조합이 모두 상대화 세계에서 실현됨을 보였고, Agrawal–Watanabe(2009)는 정칙 일방향 함수가 있으면 NP 완전 집합이 1-1·길이 증가 P/poly 환원으로 서로 환원됨을 보였다. 4단계 지도에 이 둘이 빠져 있다 | https://www.datalearner.com/academic/journal-papers/0022-0000/volumes-and-issues/176/paper-detail/112660 · https://eccc.weizmann.ac.il/report/2009/019 |
| Babai 의 그래프 동형 준다항 알고리즘 | 맞음 (STOC 2016) | https://en.wikipedia.org/wiki/Graph_isomorphism_problem |
| 「이 계열 대부분은 상대화한다」 + 「대수화 장벽과도 무관한 조합적 기법」 | 앞뒤 모순 — 상대화하는 결과는 정의상 대수화도 한다(Aaronson–Wigderson: 대수화는 상대화의 확장). 따라서 상대화하는 기법은 대수화 장벽에도 그대로 걸린다 | https://eccc.weizmann.ac.il/report/2008/005/download |
고칠 곳
- 「왜 해볼 만한가」 장벽 문단과 장벽 표 대수화 칸
- 원문(본문): 「대수화 장벽과도 무관한 조합적 기법이다.」
- 제안: 「다만 상대화하는 기법은 정의상 대수화도 하므로(Aaronson–Wigderson), 이 계열은 대수화 장벽에도 그대로 걸린다.」
- 원문(표): 「조합적 기법이라 대수화 장벽과도 무관하다고 본다.」
- 제안: 「상대화하는 기법은 대수화도 하므로 대수화 장벽에도 걸린다 — 상대화 칸과 같은 한계다.」
- 1단계
- 원문: 「Karp–Lipton 붕괴 정리(및 Cai의 S2p 강화)」
- 제안: 「Karp–Lipton 붕괴 정리(및 Sengupta 의 S2P 붕괴 강화와 Cai 의 S2P ⊆ ZPP^NP)」
- 핵심 정리 3번째 줄 · 개요 셋째 문단(Ladner)
- 원문: 「다항시간 환원 차수들이 조밀한 무한 격자를 이룬다」
- 제안: 「다항시간 환원 차수들이 조밀한 무한 구조(상반격자)를 이룬다」
- 「암호학·메타복잡도와의 접점」 문단
- 원문: 「동형 추측의 유력 반례 시나리오가 일방향 함수의 존재와 직결되므로(Joseph–Young, Kurtz–Mahaney–Royer),」
- 제안: 「동형 추측의 유력 반례 시나리오가 일방향 함수의 존재와 맞닿아 있으므로(Joseph–Young, Kurtz–Mahaney–Royer — 다만 Rogers(1997)는 일방향 함수와 동형 추측이 함께 성립하는 오라클도 만들었다),」 — 4단계 지도 목록에도 Rogers(1997)·Agrawal–Watanabe(2009)를 더한다.
- 2단계 세로축(작은 표현)
- 원문: 「세로축을 희소성 수준(tally, sparse, 준다항 밀도, P-selective, P/poly 등)으로」
- 제안: 「세로축을 희소성·구조 수준(tally, sparse, 준다항 밀도, 그리고 밀도가 아닌 구조 성질인 P-selective, P/poly 등)으로」
- 3단계 — 「질의 수가 로그 이하로 제한된 tt 환원」 앞에 「(ctt·dtt 와 일부 제한 tt 칸의 선행 결과 — Arvind 외 1993, Cai–Naik–Sivakumar 1995 — 를 먼저 대조한 뒤)」를 넣는다.
- (작은 표현) 「희소 완전 집합 후보를 만들면 P=NP 증명이고」 → 「희소 집합의 NP 완전성을 증명하면 곧 P=NP 이고」(후보 제시만으로는 증명이 아니다).
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.