# Complexity Theory

• 2026년 4월 5일 알고리즘
  알고리즘 오리엔테이션 — 알고리즘이란 무엇인가

  알고리즘의 정의와 올바름(Correctness)을 살펴보고, 수학적 귀납법과 루프 불변식으로 알고리즘을 증명한다. 정지 문제(Halting Problem)로 알고리즘의 근본 한계를 확인하고, RAM 모델과 점근적 표기법(Big-O, Θ, Ω)으로 효율을 분석한다.

• 2026년 3월 23일 암호학
  NP-Complete — NP에서 가장 어려운 문제들

  NP 내에서 가장 어려운 문제들의 집합인 NP-Complete를 정의하고, Reduction(귀착) 개념과 Cook의 정리를 통해 SAT가 최초의 NP-Complete 문제임을 증명하는 과정을 살펴본다.

• 2026년 3월 22일 암호학
  NP의 다른 정의 — 검증자와 증명서

  NTM 기반의 NP 정의와 검증자(Verifier) 기반의 NP 정의가 동치임을 보인다. '힌트가 있을 때 빠르게 검증할 수 있는 문제'라는 직관이 어떻게 수학적으로 엄밀해지는지 탐구한다.

• 2026년 3월 22일 암호학
  Alice and Bob — 계산 복잡도 클래스 P, NP, PSPACE

  암호화의 안전성을 계산 복잡도로 정의한다. P, NP, EXP, PSPACE 클래스를 소개하고, P ⊆ NP ⊆ PSPACE ⊆ EXP 계층 관계와 PSPACE = NPSPACE를 설명한다.

• 2026년 3월 21일 계산 이론
  Classes — 계산 가능성 클래스 D, E, co-E

  결정 가능한 문제의 집합 D, 열거 가능한 문제의 집합 E, 그리고 co-E를 정의하고, D = E ∩ co-E를 증명한다. 정지 문제를 통해 E ≠ D임을 확인한다.

• 2026년 3월 21일 계산 이론
  Turing Machine — 계산의 극한

  현대 컴퓨터의 이론적 모델인 튜링 머신의 구조를 살펴보고, 2-Tape DTM, Universal Turing Machine, 그리고 DTM과 NTM의 계산 능력이 동일함을 정리한다.

• 2026년 3월 21일 계산 이론
  DPDA와 NPDA — 스택을 가진 오토마타

  DFA에 스택을 추가한 DPDA가 해결할 수 있는 문제와 없는 문제를 살펴보고, NPDA와의 계산 능력 차이를 분석한다. 스택 2개로 튜링 머신을 시뮬레이션하는 원리까지 다룬다.

• 2026년 3월 20일 계산 이론
  NFA — 비결정론적 유한 오토마타

  DFA를 확장한 계산 모델인 NFA의 구조와 accept 조건을 살펴보고, Powerset Construction을 통해 NFA와 DFA의 계산 능력이 동일함을 설명한다.

• 2026년 3월 20일 계산 이론
  DFA — 결정론적 유한 오토마타

  튜링 머신을 단순화한 계산 모델인 DFA의 구조와 동작 원리를 살펴보고, Pumping Lemma를 통해 DFA로 풀 수 없는 문제가 존재함을 증명한다.

• 2026년 3월 19일 계산 이론
  Problem & Solution — Complexity Theory의 수학적 정의

  Complexity Theory에서 '문제'와 '풀이'는 어떻게 정의될까? Decision Problem, Language, 튜링 머신을 통해 풀리지 않는 문제가 왜 대부분인지를 살펴본다.

• 2026년 3월 18일 계산 이론
  집합의 크기(Cardinality) — 무한의 크기를 비교하다

  무한집합에도 크기가 있을까? 자연수, 정수, 유리수, 실수의 크기를 비교하고, 칸토어의 대각선 논법을 통해 무한에도 '더 큰 무한'이 있음을 증명한다.

• 2026년 3월 17일 암호학
  Toss Coin over Telephone

  전화로 공정하게 동전 던지기를 할 수 있을까? Manuel Blum이 제안한 암호학적 동전 던지기 프로토콜과 그 수학적 배경을 다룬다.

• 2026년 3월 16일 계산 이론
  Interesting Number Paradox

  수학적 증명에서 '정의(definition)'의 엄밀함이 왜 중요한지를 보여주는 패러독스. 암호학 Complexity Theory 도입부.