korean
[VLSI CAD] Two-Level Logic Minimization이 어려운 이유
TL;DR * Two-Level Logic Minimization을 “정확히” 풀려면 Quine–McCluskey(QM) 흐름을 타게 된다. * QM의 병목은 covering(minimum column cover) 단계다. * covering은 NP-complete라서, “최적해”는 값이 아니라 증명 문제가 된다. * SAT는 거의 큰 문제가 안 된다. 이유는 SAT가 본질적으로 decision 문제이기 때문이다. EDA는 heuristic + pruning+ branch-and-bound로 “충분히 좋은 답”을 빠르게