---
id: wiki-2026-0508-computer-science-and-theory
title: Computer Science and Theory
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [CS Theory, TCS, Theoretical Computer Science]
duplicate_of: none
source_trust_level: A
confidence_score: 0.9
verification_status: applied
tags: [index, theory, foundation, computability, complexity]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: N/A
  framework: index
---

# Computer Science and Theory

## 매 한 줄
> **"매 computation 의 fundamental limits + structures 의 systematic study"**. Turing 1936 → Church-Turing thesis → Cook-Levin 1971 NP-completeness → 2026 quantum supremacy + post-ML complexity. 매 folder 의 매 index — 매 child topics 의 navigation hub.

## 매 핵심

### 매 Pillars
- **Computability**: 매 무엇이 computable 인가 — 매 Turing machine, halting problem.
- **Complexity**: 매 얼마나 efficient 인가 — 매 P/NP/PSPACE/EXPTIME/BQP.
- **Algorithms**: 매 specific computational procedures — 매 design + analysis.
- **Logic & Formal Languages**: 매 syntax/semantics — 매 Chomsky hierarchy.
- **Information Theory**: 매 entropy, coding, compression bounds.
- **Cryptography Theory**: 매 reduction-based security, OWF.

### 매 Subdomain map
1. **Algorithms & Data Structures**: sorting, graphs, DP, randomized.
2. **Combinatorial Optimization**: TSP, scheduling, matching.
3. **Dynamical Systems**: chaos, control theory, stability.
4. **Theory of Computation**: automata, decidability, complexity classes.
5. **Type Theory**: simply-typed lambda, dependent types, HoTT.
6. **Quantum Information**: BQP, qubits, error correction.

### 매 응용 bridge
- 매 cryptography ← 매 complexity (OWF, hash functions).
- 매 ML theory ← 매 PAC learning, VC dimension, generalization bounds.
- 매 distributed systems ← 매 FLP impossibility, consensus lower bounds.
- 매 compilers ← 매 type theory, automata, lambda calculus.
- 매 databases ← 매 query complexity, join algorithms.

## 💻 패턴

### Folder Sub-topics (representative)
| Topic | Type |
|---|---|
| Bubble Sort | Algorithm — sorting |
| Combinatorial Optimization | Algorithm — discrete |
| Chaos Theory in Systems | Dynamical systems |
| Control Theory | Dynamical systems |
| Cross-Frequency Coupling | Neural information theory |
| Caetextia | Cognitive theory |
| Burnout Prevention in Professional Gaming | Applied cognitive |
| Climate Change Mitigation Frameworks | Applied modeling |

### Index Page Convention
```yaml
purpose: navigate child topics in this folder
canonical_id: self
duplicate_of: none
content:
  - 매 한 줄: domain summary
  - 매 핵심: pillars + subdomains
  - 매 패턴: child topic listing
  - 🔗 Graph: parent index + sibling folders
```

### Cross-Folder Bridge Pattern
```markdown
## Parent index
- [[10_Wiki Index]] · [[Programming Index]]
## Sibling folders (Topics/)
- [[AI_and_ML]] · [[Architecture]] · [[DevOps_and_Security]]
- [[Cognitive_Science_and_Neuroscience]] · [[Frontend]] · [[Backend]]
```

### Complexity Cheat Sheet
```text
P              ⊆ NP ⊆ PSPACE ⊆ EXPTIME
P              ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE
NP             — verifiable in poly-time
NP-complete    — TSP, SAT, 3-COLOR, Knapsack (decision)
NP-hard ∩ EXP  — Halting (undecidable)
```

### Theory → Practice Mapping
```yaml
theory_to_practice:
  - {theory: NP-completeness, practice: "use heuristics + approximation"}
  - {theory: P=NP open, practice: "assume P≠NP for crypto"}
  - {theory: FLP impossibility, practice: "consensus needs partial sync (Raft/Paxos)"}
  - {theory: CAP theorem, practice: "pick 2: CP or AP under partition"}
  - {theory: PCP theorem, practice: "hardness of approximation results"}
```

## 매 결정 기준
| Question | Direction |
|---|---|
| Sort/search basics | Algorithms & Data Structures |
| Discrete optimization | Combinatorial Optimization |
| System stability | Control Theory / Chaos |
| Compiler/PL design | Type Theory / Lambda Calculus |
| Crypto foundations | Complexity / Number Theory |
| Distributed system limits | Theory of Distributed Computing |

**기본값**: 매 child topic 의 specific 의 navigate — 매 index 의 entry point only.

## 🔗 Graph
- 자식: [[Bubble Sort]] · [[Combinatorial Optimization]] · [[Chaos Theory in Systems]] · [[Control Theory]] · [[Caetextia]] · [[Cognitive Neuroscience of Flow]] · [[Cross-Frequency Coupling (CFC)]] · [[Climate Change Mitigation Frameworks]] · [[Burnout Prevention in Professional Gaming]]
- Sibling 폴더: [[Architecture]] · [[DevOps_and_Security]]
- Adjacent: [[Entropy in Information Theory|Information Theory]] · [[Logic]]

## 🤖 LLM 활용
**언제**: 매 navigation hub — 매 child topic 의 discovery.
**언제 X**: 매 specific algorithm content — 매 child page 의 redirect.

## ❌ 안티패턴
- **Index 의 deep content**: 매 child page 의 duplicate — 매 stale risk.
- **Stale child link**: 매 deleted/moved page 의 broken wikilink.
- **Mixed scope**: 매 index 의 specific application 의 mix — 매 child page 의 belong.

## 🧪 검증 / 중복
- Verified (folder taxonomy 의 cross-checked, child pages exist).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — folder index with child taxonomy + theory-practice mapping |
