NP-난해성은 실무 실패 보장이 아니다, SAT·최적화 도구 사례와 반론

SAT이 NP-완전이라는 사실은 실무 SAT 인스턴스가 전부 풀기 어렵다는 뜻이 아님. 쓸모없는 탐색 공간을 피하도록 사람이 추가 절을 넣어 솔버를 유도할 수도 있음.

어려움은 대개 특정 구성에서 생기는 조합 폭발임. 일상적인 문제의 SAT 솔버는 잘 풀지만 SHA256 같은 암호 설계는 휴리스틱에 버티는 지수적 경우를 의도적으로 만들기 때문에 다름.

큰 그래프의 일부 종류에서는 외판원 문제가 O(N)이라는 관점도 있음. 난 O(log N) 아이디어보다 분기 없는 O(N) 전처리 뒤 연속 메모리와 벡터 연산에 맞는 문제로 바꾸는 쪽이 더 빠른 경우를 자주 봄.

NP-난해성 이론은 모든 입력에 좋은 알고리즘이 없다고 말할 뿐임. 그래서 병적인 경우를 드물게 만들도록 문제 공간을 제한하고, 남은 경우를 감시하는 게 필요함.

패키지 관리자는 NP-난해성에도 불구하고 설계된 게 아니라 그 난해성 때문에 제약을 둔 것임. npm과 yarn은 패키지 이름당 버전 하나라는 조건을 버리고, Go는 최소 버전 선택으로 선형 시간 해법을 얻으며, Cargo는 복수 메이저 버전과 휴리스틱으로 경우를 줄임.

글쓴이가 잘못 배운 것보다 애초에 잘못 가르침받았을 가능성이 더 커 보임.

대형 Python 환경을 처리해 보면 실제로 지수적으로 꺾이는 구석을 만남. 더 빠른 해석기로 바꾸면 지수적 경우도 벽시계 시간은 줄지만, Python 의존성 명세 자체가 이런 상황에 좋지 않음.

최대 버전 제한 같은 음성 의존성을 없애면 패키지 관리 문제를 NP-난해하지 않게 만들 수 있음.

실무의 첫 번째 해법은 어려운 경우를 허용하지 않는 것임. 의존성 관리와 타입 시스템은 NP-난해 공간의 큰 부분을 명시적으로 잘라내며, 남은 문제에는 최선을 다하거나 더 제약을 넣는 식임.

의존성 해석에서 N은 대개 큰 상수로 묶임. 생태계 전체 후보 의존성도 보통 100개에서 1만개쯤이라면 성장 차수는 사실상 O(1)처럼 작동할 수 있음.

어려운 입력을 막아 P로 만드는 건지, 단지 실무에서 만나지 않게 하는 건지는 구분해야 함. 심플렉스법처럼 어려운 인스턴스를 금지하지 않아도 실제로 들어오는 문제는 안 어려운 경우도 있음.

근사해를 허용하면 손실과 복잡도 사이의 파레토 경계가 더 흥미로운 문제가 됨.

근사 가능성 자체도 이론 문제임. 삼각 부등식이 성립하는 metric TSP는 최소 신장 트리를 두 번 쓰면 2-근사 해법이 있지만, 일반 TSP는 P=NP가 아닌 한 다항 시간 상수비 근사가 불가능함.

오래된 Debian 설치를 aptitude로 여러 메이저 버전 업그레이드해 봤다면 탐색 공간에서 길 잃는 일을 봤을 것임. 다운그레이드, 제거, 추천 패키지 미설치 각각이 새 조합을 만들고, 사람이 충돌 패키지 일부를 좁혀 줘야 할 때가 있음.

그 apt 묘사는 사실상 SAT이고, 최근 apt의 --solver 3.0은 그 방식으로 동작함.

iOS 앱을 빌드해 보면 Swift 타입 검사 시간이 너무 길어 컴파일러가 포기하는 경우가 있음.