[발췌] 황제의 새 마음 / 2024-06-03 / 아주 어려운 것은 매우 느린 알고리즘으로 풀린다.

 

 

 

1. 비주기적인 패턴은 여러 놀라운 특성을 갖는데, 결정학적으로 불가능한 것처럼 보이는 5중 대칭 Fivefold symmetry의 준주기적 quasi-periodic 구조라는 것이다. 
2. 재귀적이지 않다면 알고리즘으로 도달할 수 없는 영역은 아주 섬세한 특성을 지닐뿐만 아니라 찾기도 어려울 것이다. 
3. 아주 어려운 것은 매우 느린 알고리즘으로만 풀릴 수 있다. 이런 종류의 문제와 관련된 이론을 복잡도 이론 comlexity theory이라 부른다. 
4. 한 집단 내에서도 문제들은 '크기'가 서로 다른데, 문제의 크기는 n을 측정 단위로 사용한다. 
5. 크기가 n인 모든 문제 가운데 알고리즘의 단계 중 가장 큰 수가 N이라고 하자. 
6. N의 증가율은 항상 같은 범주로 구분될 수 있게끔 하기 위한 것이다. 그러만 범주 중 P(다항식의 시간 Polynomial time을 상징)라고 불리는 것.