주요 접근
연구자들이 걸어 온 길.
- 주요 접근의 지도 — P ≠ NP 로 가려던 여덟 갈래 길
대각선 논법, 회로 하한, 산술화, 증명 복잡도, 알고리즘에서 하한으로, 기하적 복잡도 이론, 메타복잡도, 평균적 복잡도까지 P ≠ NP 를 향한 주요 접근을 한 표로 정리하고, 각 접근의 핵심 생각·대표 결과·걸리는 장벽을 짚는다.
- 회로 하한 — 제한된 회로에서의 성공, 일반 회로에서의 정체
P ⊆ P/poly 이므로 NP 문제에 초다항 크기의 회로가 필요함을 보이면 P ≠ NP 다. AC⁰·AC⁰[p]·단조 회로에서는 강한 하한이 증명되었지만, 제한이 없는 회로에 대해 알려진 하한은 3.1n 수준에 머물러 있다.
- 기하적 복잡도 이론 — 퍼머넌트 대 행렬식을 표현론으로
Mulmuley 와 Sohoni 의 기하적 복잡도 이론(GCT)은 퍼머넌트가 행렬식보다 본질적으로 어렵다는 추측을 궤도 폐포와 표현론의 문제로 옮긴다. 대칭성을 써서 알려진 장벽을 피하려는 계획이지만, 가장 단순한 형태는 불가능함이 증명되었고 매우 긴 호흡의 계획으로 평가된다.
- 증명 복잡도 — 짧은 증명이 없는 항진식을 찾아서
Cook 과 Reckhow 는 NP ≠ coNP 가 「어떤 증명 체계에도 짧은 증명이 없는 항진식이 있다」와 같은 말임을 보였다. 분해 체계에서는 Haken 이 지수 하한을 증명했지만, 교과서의 명제 논리 체계인 프레게 체계부터는 하한이 알려져 있지 않다.
- 알고리즘에서 하한으로 — Williams 의 방법
회로의 만족 가능성을 전수 탐색보다 조금만 빨리 푸는 알고리즘이 있으면 회로 하한이 따라 나온다. Williams 는 이 연결로 NEXP ⊄ ACC⁰ 를 증명했고, Murray 와 Williams 는 그것을 비결정적 준다항 시간 NQP 까지 내렸다.
- 메타복잡도 — 어려움을 판정하는 일은 얼마나 어려운가
최소 회로 크기 문제(MCSP)와 시간 제한 콜모고로프 복잡도는 「함수나 문자열의 복잡도를 구하는 문제」다. 이 문제들의 복잡도를 묻는 메타복잡도는 자연 증명, 최악과 평균의 관계, 일방향 함수의 존재를 한데 잇는 고리로 다시 주목받고 있다.
- 평균적 복잡도와 다섯 세계 — P ≠ NP 너머의 물음들
P ≠ NP 는 최악의 경우에 관한 명제이고, 암호에는 평균적으로 어려운 문제와 일방향 함수가 필요하다. Impagliazzo 는 이 가정들 가운데 어디까지가 참이냐에 따라 가능한 세계를 Algorithmica·Heuristica·Pessiland·Minicrypt·Cryptomania 다섯으로 나누었다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.