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.
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/.