- P vs NP 문제 풀기
- 1. P vs NP 문제는 무엇인가?
- 1-3 개념 사전
- 기하적 복잡도 이론
1-3
기하적 복잡도 이론
geometric complexity theory (GCT)
대수기하와 표현론으로 복잡도 하한을 증명하려는 장기 연구 계획
멀물리(Mulmuley)와 소호니(Sohoni)가 2001년 논문에서 시작한 접근이다. permanent 를 determinant 로 표현할 수 있는지를 두 다항식의 대칭성이 만드는 기하적 대상(궤도 폐포) 사이의 포함 문제로 바꾸고, 포함이 불가능함을 보여 주는 표현론적 증거(장애물)를 찾으려 한다. 다항식의 특별한 대칭성을 쓰기 때문에 알려진 장벽들을 피할 수 있으리라는 기대를 받는다. 다만 매우 긴 시간이 걸릴 것으로 여겨지는 계획이고, 아직 기존 방법을 넘는 하한을 내지는 못했다. 처음 구상한 가장 단순한 형태의 장애물(occurrence obstruction)만으로는 안 된다는 것이 2016년에 밝혀졌다(Bürgisser·Ikenmeyer·Panova).