The Longest Increasing Subsequence Problem revisited

이 논문은 최장 증가 부분 수열 문제가 다항 시간 내에 해결 가능함에도 불구하고, 저온 상태에서는 에너지 장벽 때문이 아니라 접근 가능한 구성의 부족으로 인해 국소 탐색 알고리즘이 준안정 상태에 갇히게 되는 유리 역학(glassy dynamics)과 열역학적 희소성을 보인다는 점을 밝히고 있다.

핵심

당신에게 셔플된 카드 한 덱이 있다고 상상해 보세요. 당신의 목표는 카드의 순서를 건너뛰지 않고 값이 계속 커지는(예: 2, 5, 8, 10) 가장 긴 시퀀스를 찾는 것입니다. 이것은 수학과 컴퓨터 과학에서 **최장 증가 부분 수열(Longest Increasing Subsequence, LIS)**이라고 불리는 유명한 퍼즐입니다.

보통 컴퓨터는 이 문제를 아주 잘 해결합니다. 이 문제를 완벽하게 찾아낼 수 있는 알려진 "지름길"(알고리즘)들이 있으며, 거대한 카드 덱에 대해서도 즉각적으로 답을 찾아낼 수 있습니다.

하지만 이 논문은 다른 질문을 던집니다: 만약 우리가 '시행착오' 방식, 즉 인간이 추측하고 확인하는 것과 같은 방식으로 이 퍼즐을 풀려고 한다면, 그리고 이를 다양한 "온도"에서 수행한다면 어떻게 될까?

물리학에서 온도는 단순히 열기를 의미하는 것이 아닙니다. 그것은 시스템이 가진 "떨림" 또는 무작위성의 정도를 나타내는 척도입니다. 저자들은 이 수학 퍼즐을 하나의 물리학 실험으로 바꾸어, "해답 공간"(가능한 모든 답이 존재하는 풍경)이 어떻게 행동하는지 관찰했습니다.

다음은 일상적인 비유를 통해 설명한 그들의 발견입니다:

1. 두 가지 "온도 구역"

연구자들은 "시행착오" 시스템을 냉각시킴에 따라, 마치 산을 내려가는 자동차가 두 종류의 교통 체증을 만나는 것처럼 두 개의 뚜렷한 장벽에 부딪힌다는 것을 발견했습니다.

• 첫 번째 정지 지점 ("쇼트키" 크로스오버, T ≈ 0.38):
  이 현상은 전자 소음과 같은 '시끄러운' 현상이 아니라, 물리학에서 매우 보편적인 **두 단계 시스템(Two-Level System)**의 고전적인 특징인 '쇼트키 이상(Schottky anomaly)'에서 비롯됩니다.

  이 퍼즐의 해답 공간은 서로 독립적으로 행동하는 수많은 작은 '서브 시스템'들로 구성되어 있다고 상상해 보세요. 각 서브 시스템은 마치 계단처럼 두 가지 상태만 가질 수 있습니다: 낮은 에너지 상태(바닥)와 약간 높은 에너지 상태(계단 위).

  온도가 높을 때는 이 시스템들이 두 상태 사이를 자유롭게 오가며 활발히 움직입니다. 하지만 온도가 T ≈ 0.38 부근까지 떨어지면, 시스템들은 높은 에너지 상태를 버리고 낮은 에너지 상태로 넘어가기 시작합니다. 이때 시스템이 열을 흡수하거나 방출하는 능력(비열, specific heat)이 급격히 변하며 특징적인 '뾰족한 봉우리'를 보입니다. 마치 많은 사람들이 한꺼번에 계단 아래로 내려오다가 잠시 멈추었다가 다시 조용해지는 것과 같습니다.

  이 논문에서 이 현상은 LIS의 '골격'을 따라 존재하는 약 O(ln N)개의 독립적인 두 단계 시스템들에서 비롯됩니다. 이는 시스템이 완전히 멈추거나 위상이 변하는 것이 아니라, 수많은 작은 시스템들이 낮은 에너지 상태로 차분히 정착해 가는 매끄러운 전환(crossover) 과정입니다.

• 두 번째 정지 지점 ("응축" 전이, T ≈ 0.10):
  이것은 결정적인 단계입니다. 시스템을 더 낮게 냉각시키면, 마법 같고 기묘한 일이 일어납니다. 수많은 사람들(모든 가능한 해답들)로 가득했던 군중이 갑자기 줄어드는 것을 상상해 보세요. 산 정상으로 향하는 수백만 개의 서로 다른 경로 대신, 군중은 "응축"되어 매우 작은 하위 지수적(sub-exponential) 집단으로 변합니다.

  이것은 눈 결정이 형성되는 것과 같습니다. 처음에는 물 분자가 도처에 널려 있습니다(많은 해답). 하지만 충분히 차가워지면, 그들은 모두 하나의 단단하고 고정된 결정 구조로 결합됩니다. 이 퍼즐에서 "해답"들은 매우 작고 특정한 "바닥 상태(ground states)"로 응축됩니다. 좋은 답의 수가 급격히 줄어드는 이유는 답을 찾기 어려워서가 아니라, 남겨진 좋은 답 자체가 극도로 적기 때문입니다.

2. "유리질(Glassy)" 함정

여기 이 논문을 유명하게 만든 역설이 있습니다:

• 쉬운 방법: 만약 당신이 똑똑한 단계별 수학적 트릭(동적 계획법)을 사용한다면, 즉각적으로 완벽한 답을 찾을 수 있습니다.
• 어려운 방법: 만약 당신이 "지역 탐색(local search)"(주변의 이웃만을 살펴보고 개선을 시도하는 단순한 컴퓨터 방식)을 사용한다면, 길을 잃고 갇히게 됩니다.

저자들은 낮은 온도에서 이 단순한 컴퓨터가 **메타스테이블 상태(metastable state, 준안정 상태)**에 갇힌다는 것을 발견했습니다. 이것은 마치 등산객이 작은 골짜기에 갇힌 것과 같습니다. 등산객은 멀리서 산봉우리(완벽한 답)를 볼 수 있지만, 그들이 내딛는 모든 국소적인 발걸음은 결국 다시 골짜기 바닥으로 이어집니다.

이러한 행동을 "유리질 역학(glassy dynamics)"(겉보기에는 고체처럼 보이지만 실제로는 얼어붙은 액체인 창유리와 같은 상태)이라고 부릅니다. 이 시스템은 다음을 보여줍니다:

• 2단계 완화(two-step relaxation): 처음에는 빠르게 움직이다가 거의 완전히 멈춰버립니다.
• 에이징(Aging, 노화): 기다리면 기다릴수록 움직이기가 더 어려워집니다. 시스템은 점점 "늙어가며" 더 갇히게 됩니다.
• 지속적인 중첩(Persistent Overlap): 만약 같은 골짜기에 두 명의 등산객을 출발시킨다면, 그들은 봉우리를 찾지 못한 채 서로 가까이 머물며 영원히 그곳에 갇혀 있을 것입니다. 왜냐하면 그들은 동일한 작은 해답 클러스터에 갇혀 있기 때문입니다.

3. 성공의 비결: "느린 어닐링(Slow Annealing)"

논문은 이 함정에서 벗어나는 방법이 있으며, 여기에는 인내심이 필요하다는 것을 보여줍니다. 이것을 **시뮬레이티드 어닐링(Simulated Annealing, 담금질)**이라고 합니다.

미로 속에서 최적의 경로를 찾으려고 노력한다고 상상해 보세요.

• "퀜치(Quench, 급랭)": 만약 온도를 즉각적으로 떨어뜨린다면(뜨거운 금속을 얼음에 담그는 것처럼), 시스템은 나쁜 위치에서 얼어붙습니다. 시스템은 국소적인 골짜기에 갇혀 빠져나올 수 없습니다.
• "어닐링(Annealing, 서냉)": 만약 온도를 매우 천천히(로그 함수적으로) 낮춘다면, 시스템은 아직 따뜻할 때 전체 미로를 탐색할 수 있도록 충분히 "유동적"인 상태를 유지합니다. 시스템은 길이 얼어붙기 전에 완벽한 해답으로 향하는 주요 고속도로를 찾아냅니다.

저자들은 시스템을 천천히 냉각하면 완벽한 경로를 따라 끝까지 추적할 수 있다는 것을 발견했습니다. 하지만 너무 빨리 냉각하면 "유리질"의 엉망진창인 상태에 갇히게 됩니다.

핵심 요약

가장 놀라운 결론은 이 문제가 지역 탐색자들에게 어려운 이유는 "에너지 장벽"(넘을 수 없는 높은 벽) 때문이 아니라, "열역학적 희소성(thermodynamic sparsity)" 때문이라는 점입니다.

이렇게 생각해보세요:

• 에너지 장벽: 뛰어넘기에는 너무 높은 벽이 있는 상황입니다.
• 열역학적 희소성: 오직 작은 오아시스만이 존재하는 광활한 사막을 상상해 보세요. 당신이 무작위로 헤매고 있다면, 벽이 있어서가 아니라 "좋은" 지점이 믿기 힘들 정도로 드물고 희소하기 때문에 통계적으로 그곳을 우연히 발견할 확률이 매우 낮습니다.

이 논문은 최장 증가 부분 수열 문제가 두 세계를 잇는 가교임을 결론짓습니다:

1. 쉬운 최적화: 수학이 즉각적으로 해결할 수 있는 문제.
2. 유리질 물리학: 단순한 지역 탐색 알고리즘이 갇히기 쉬울 정도로 복잡하고 희소한 문제.

이는 어떤 문제가 수학적으로는 "쉬울(easy)" 수 있지만(똑똑한 알고리즘에 의해 해결 가능), 동역학적으로는 "어려울(hard)" 수 있음(단순한 지역 탐색이 갇히지 않고는 해결할 수 없음)을 증명합니다.

기술 요약

기술 요약: 최장 증가 부분 수열(Longest Increasing Subsequence, LIS) 문제의 재조명

문제 정의
본 논문은 고전적인 조합 최적화 과제인 최장 증가 부분 수열(LIS) 문제의 열역학적 특성과 동역학적 거동을 조사한다. LIS 문제의 바닥 상태(ground state)는 동적 계획법(dynamic programming)을 통해 다항 시간 내에 해결 가능하다는 것이 알려져 있고, 그 점근적 변동은 무작위 행렬 이론 및 카르다노-파리시-집(Kardar–Parisi–Zhang, KPZ) 보편성 클래스와 연결되는 베이크-데프트-요한슨(Baik–Deift–Johansson) 정리의 지배를 받지만, 저자들은 통계 역학적 관점에서 이 문제를 탐구한다. 온도 매개변수를 도입함으로써, 저자들은 증가하는 부분 수열의 길이를 에너지 함수($E = -\ell$)로 취급하여 해 공간(solution space)의 구조와 국소 탐색 알고리즘의 효용성을 조사한다.

방법론
저자들은 정확한 열역학적 형식론과 확률적 시뮬레이션을 결합한 이중 접근 방식을 채택한다:

1. 열역학적 형식론:

   • 그래프 표현: 이 문제는 무작위 그래프(Ulam graph) 상의 유향 폴리머(directed polymer)로 매핑된다. 여기서 정점은 위치 $(i, s_i)$이며, $i < j$이고 $s_i < s_j$일 때 에지가 존재한다.
   • 계수 및 엔트로피: 동적 계획법을 사용하여 길이가 $\ell$인 증가 부분 수열의 개수($N_\ell$)를 계산한다. 이를 통해 미시 정준 엔트로피 $S(\ell)$와 정준 분배 함수 $Z_N(\beta)$를 구성할 수 있다.
   • 비열: 상전이 또는 교차(crossover)를 식별하기 위해 미시 정준 및 정준 비열($c_v$)을 모두 계산한다.

2. 몬테카를로 동역학:

   • 상세 균형(detailed balance)을 만족시키기 위해 국소 메트로폴리스(Metropolis) 알고리즘을 구현한다. 이 알고리즘은 기본 이동(elementary moves)을 수행한다: 순서가 유지되는 경우 임의의 원소를 현재 부분 수열에 삽입하거나, 확률 $\exp(-1/T)$로 원소를 제거한다.
   • 시뮬레이션: 저자들은 무한 온도에서 다양한 목표 온도 $T$로 급격한 퀜치(quench)를 가한 후, 에너지와 동역학적 중첩(dynamical overlap) $Q(t)$의 시간 진화를 분석한다. 또한 이러한 결과를 시뮬레이티드 어닐링(simulated annealing) 궤적과 비교한다.

주요 결과

1. 두 가지 뚜렷한 에너지 척도:
   연구는 두 가지 임계 온도 영역을 식별한다:

   • 쇼트키 유사 교차 ($T_{cross} \approx 0.38$): 비열의 피크가 관찰되며, 이는 시스템 크기 $N$에 대해 로그 스케일로 변화한다. 이는 상전이가 아니라, LIS 백본(backbone)을 따라 발생하는 $O(\ln N)$개의 독립적인 이준위 계(two-level systems)와 관련된 쇼트키 교차로 해석된다.
   • 응축 전이 ($T_{cond} \approx 0.10 \pm 0.02$): 이 온도 아래에서 시스템은 응축 전이를 겪는다. 최대 길이 구성의 개수는 시스템 크기에 대해 지수 함수적이 아니라 아지수 함수적(sub-exponential)으로 감소한다 ($\Omega_{gs}(N) \sim e^{s_0 \sqrt{N}}$ 이며, $s_0 \approx 0.35$). 이는 엔트로피 밀도의 포화와 참여 비율(participation ratio)의 스케일링을 통해 입증된다.

2. 국소 탐색에서의 유리질(Glassy) 동역학:
   바닥 상태를 위한 다항 시간 알고리즘이 존재함에도 불구하고, 국소 몬테카를로 동역학은 유리질 거동의 징후를 보인다:

   • 2단계 완화: $T_{cond}$와 $T_{cross}$ 사이의 온도에서, 시스템은 퇴행적 매니폴드(degenerate manifold) 내에서의 빠른 완화와 서로 다른 구성들 사이의 느린 터널링을 보여준다.
   • 에이징(Aging) 및 중첩: $T \approx 0.2$에서 동역학적 중첩 $Q(t)$는 대기 시간 $t_w$에 강한 의존성을 보이며, 이는 시스템이 특정 메타스테이블 경로로 에이징됨을 나타낸다.
   • 동역학적 정지(Arrest): $T \approx T_{cond}$에서 시스템은 동역학적으로 정지된다. 깁스 측도(Gibbs measure)는 희소한(sparse) 지배적 구성들의 부분집합에 집중되며 ($N_{eff} \sim e^{\Sigma_{eff}\sqrt{N}}$), 국소 이동은 시뮬레이션 시간과 관계없이 이러한 상태를 탈출하는 데 실패한다.

3. 어닐링과 퀜치의 역할:

   • 퀜치(Quenches): $T < T_{cond}$로의 급격한 퀜치는 시스템이 바닥 상태보다 높은 에너지를 가진 메타스테이블 상태에 갇히게 만든다.
   • 시뮬레이티드 어닐링: 로그 스케일의 어닐링 스케줄은 평형 곡선을 바닥 상태까지 성공적으로 추적한다. 저자들은 이 알고리즘이 $T > T_{cond}$(동역학이 빠른 구간) 동안 부분 수열을 단조롭게 구축함으로써, 응축으로 인한 희소성이 탐색을 얼리기 전에 근사 최대 길이에 도달한다고 주장한다.

의의 및 주장
본 논문은 LIS 문제가 정확히 풀 수 있는 최적화 문제와 복잡한 유리질 시스템 사이의 가교 역할을 한다는 것을 입증한다. 주요 기여는 **열역학적 희소성(thermodynamic sparsity)**이 에너지 장벽이 아닌, 국소 탐색 알고리즘을 동역학적으로 다루기 어렵게 만들 수 있음을 보여준 것이다.

• 알고리즘적 난해성: 이 연구는 문제가 형식적으로는 다항 시간 내에 해결 가능(동적 계획법을 통해)하지만, 해 공간의 "엔트로피적 크기"와 그에 따른 응축으로 인해 국소 탐색에는 동역학적으로 어려운 역설을 강조한다.
• 이산 vs 연속: 저자들은 관찰된 유리질 현상과 응축이 이산 Ulam 격자 공식(특히 고정된 에너지 간격 $\epsilon_0 = 1$)의 산물이라고 상정한다. 연속체 극한(continuum limit)에서는 이러한 특징들이 사라지고 표준 KPZ 보편성이 우세해질 것이다.
• 복잡성의 구분: 결과는 계산 복잡도(최적해를 찾는 능력)와 물리적 유리질성(국소 탐색의 동역학적 불가능성) 사이의 구분을 제안하며, LIS 문제를 이 차이를 연구하기 위한 전형적인 모델로 위치시킨다.