korean
[VLSI CAD] 최적해가 어려운 이유: NP-hard, heuristic, AI EDA
TL;DR * 반도체 설계의 핵심 최적화 문제들은 대부분 NP-hard / NP-Complete / PSPACE-complete라서, “최적해”를 보장하는 알고리즘은 스케일이 커지면 사실상 못 돈다. (예를들어 2가지 경우의 수가 40개만 되어도, 1조개의 경우의 수이다.) * 그래서 EDA 툴은 처음부터 끝까지 heuristic + 근사 + 반복 개선로 설계된다. 이건 “툴이 구려서”가 아니라 문제 성질 때문이다. * AI/ML은 NP-hard를