NP-Hardness and Reductions TODO
Concept
A reduction is a polynomial-time transformation of instances of problem A into instances of problem B; if A reduces to B, then B is no easier than A. NP-complete means a problem is in NP and every problem in NP reduces to it; NP-hard means a problem is at least that hard, regardless of whether it's in NP itself. The standard way to show a new problem is hard is to reduce a known NP-complete problem to it. If P != NP, no NP-complete problem has an exact polynomial-time algorithm. So in practice the choices become an algorithm with a proven approximation ratio, a heuristic, or an exact solver (ILP, SAT) that's exponential in the worst case.
Without knowing the source of the difficulty, you either keep tuning an optimization that's fundamentally impossible, or give up too early on a special structure that's actually easy to solve.
Code & Formula
# NP-난해와 환원 — subset-sum을 완전탐색(지수)과 그리디 근사로 풀어 오차를 비교한다.
# "환원" 감각: 정확한 다항 시간 해가 없다고 판단되면 근사/휴리스틱으로 전환하는 실무 지점을 보여준다.
def brute_force_subset_sum(nums, target):
n = len(nums)
best = []
for mask in range(1 << n): # 2^n 가지 부분집합을 전부 확인
subset = [nums[i] for i in range(n) if mask & (1 << i)]
s = sum(subset)
if s <= target and s > sum(best):
best = subset
return best
def greedy_approx_subset_sum(nums, target):
# 큰 값부터 넣을 수 있는 만큼 채우는 O(n log n) 휴리스틱 — 최적 보장은 없다
remaining = target
chosen = []
for x in sorted(nums, reverse=True):
if x <= remaining:
chosen.append(x)
remaining -= x
return chosen
nums = [23, 17, 41, 8, 15, 30, 4]
target = 60
exact = brute_force_subset_sum(nums, target)
approx = greedy_approx_subset_sum(nums, target)
print("입력:", nums, "목표:", target)
print(f"완전탐색(지수, 2^{len(nums)}={1 << len(nums)}가지 확인): {exact} 합={sum(exact)}")
print(f"그리디 근사(O(n log n)): {approx} 합={sum(approx)}")
print(f"근사 오차: {target - sum(approx)} (목표 대비 {sum(approx) / target:.1%} 달성)")
docs/code/algorithms/algorithms-16.py
Exercise
Pick one optimization problem from your own work, sketch a reduction from subset-sum or 3-SAT to it, and note the approximation ratio of a fallback approximation algorithm.
Practical Connection
Selecting transactions within a block or assembling MEV bundles has the NP-hard structure of a knapsack problem, so real builders rely on heuristics — Verex's batch-matching and batch-settlement optimization calls for the same judgment.
Where it lands in Jayverse
- Verex: document which specific heuristic batch-matching uses (e.g., greedy by price-time priority) along with its known approximation ratio, instead of an ad hoc matching loop; note that an exact ILP/SAT solver stays exponential-worst-case and isn't a real fallback at scale.
- Auditor: since P != NP, require the batch-matching module's doc to state its heuristic and rationale, so market-quality complaints don't turn into an attempt to optimize an impossible exact solution.
- OFA: identify which known NP-complete problem (e.g., knapsack, set packing) the solver/auction's bundle-selection reduces from, before choosing its heuristic.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| reduce to | 문제를 ~로 환원하다, 변환하다 · "A reduces to B" |
| no easier than | ~보다 결코 쉽지 않은 · "B is no easier than A" |
| regardless of whether | ~이든 아니든 상관없이 · "regardless of whether it's in NP itself" |
| keep tuning | 계속 손봐서 조정하다 · "you either keep tuning an optimization" |
| give up too early | 너무 일찍 포기하다 · "give up too early on a special structure" |
| special structure | 일반적이지 않은 특수한 구조 · "a special structure that's actually easy to solve" |
| ILP | 정수선형계획법(Integer Linear Programming) · 최적화 문제를 정수해로 푸는 완전탐색형 솔버, 최악의 경우 지수시간. "an exact solver (ILP, SAT) that's exponential in the worst case" |
| SAT | 충족가능성 문제(Boolean Satisfiability) · NP-완전 문제의 대표 예, 3-SAT 형태로 환원 증명에 자주 쓰임. "sketch a reduction from subset-sum or 3-SAT" |
| MEV | 최대추출가능가치(Maximal Extractable Value) · 블록 내 트랜잭션 순서·선택으로 얻는 추가 이익, 배낭 문제 구조를 가짐. "assembling MEV bundles has the NP-hard structure of a knapsack problem" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.