쿡-레빈 정리 (Cook–Levin theorem)

한 줄 정의: 불리언 논리식의 충족 가능성을 판정하는 SAT 문제가 NP-완전임을 증명한 정리로, NP-완전성 개념을 최초로 확립한 결과.

쉽게 풀면

쿡-레빈 정리는 'SAT라는 논리식 문제가 NP 안에서 가장 어려운 문제 중 하나'라는 것을 증명한다. 이 정리가 중요한 이유는, 이후 다른 문제가 NP-완전임을 보이려면 매번 처음부터 증명할 필요 없이 SAT로부터 다항 시간 환원만 보이면 되기 때문이다. 스티븐 쿡과 레오니드 레빈이 독립적으로 증명하여 오늘날 계산 복잡도 이론의 초석이 되었다.

왜 중요한가

쿡-레빈 정리는 계산 복잡도 이론에서 NP-완전성이라는 개념 자체를 처음으로 성립시킨 결과입니다. 이 정리 덕분에 이후 연구자들은 새로운 문제가 어렵다는 것을 매번 처음부터 증명하지 않고, SAT나 다른 이미 알려진 NP-완전 문제로부터 다항 시간 환원만 보이면 되는 방법론을 갖게 되었습니다. 그래서 알고리즘 설계, 조합 최적화, 암호학 등 여러 분야의 논문이 특정 문제의 난이도를 논할 때 이 정리를 출발점으로 인용합니다.

논문에서는 이렇게 쓰입니다

"쿡-레빈 정리에 의해 SAT가 NP-완전임이 확립된 이후, 수천 개의 문제가 SAT로부터의 환원을 통해 NP-완전으로 분류되었다."

NP-완전성 증명의 역사적 출발점을 설명하거나, 해당 문제가 SAT류로부터 환원됨을 보이는 논거로 사용된다.

"제안한 자원 스케줄링 문제가 3-SAT로부터 다항 시간 환원 가능함을 보임으로써, 쿡-레빈 정리에 근거해 해당 문제 역시 NP-완전임을 증명하였다."

운용과학이나 시스템 설계 분야의 논문에서 새로운 최적화 문제가 다루기 어려운 문제임을 형식적으로 입증할 때, SAT 계열 문제로의 환원을 통해 쿡-레빈 정리의 결과를 재사용하는 방식을 보여줍니다.

"회로 만족 문제(circuit-SAT)와의 동치성을 통해 쿡-레빈 정리를 재조명하며, 논리 회로 기반 암호 프로토콜의 안전성 분석에 이를 응용하였다."

이론 컴퓨터과학과 암호학이 교차하는 논문에서는 쿡-레빈 정리의 증명 아이디어(임의의 NP 문제를 논리식으로 인코딩하는 방식) 자체가 회로 기반 시스템의 어려움을 논증하는 도구로 쓰이기도 합니다.

조금 더 깊게 보면

쿡-레빈 정리의 증명은 비결정론적 튜링 기계가 다항 시간 안에 어떤 입력을 받아들이는 계산 과정 전체를, 그 계산이 성립하기 위한 조건을 나타내는 하나의 거대한 불리언 논리식으로 인코딩하는 방식으로 이루어집니다. 이 논리식이 충족 가능하다는 것과 원래의 비결정론적 계산이 해당 입력을 받아들인다는 것이 동치가 되도록 구성하는 것이 핵심입니다. 이후 카프(Karp)는 이 정리를 기반으로 여러 대표적인 조합 문제들이 서로 다항 시간 환원으로 연결되어 있음을 보여, NP-완전 문제들의 목록을 크게 확장했습니다.

주의할 점

이 정리가 증명하는 것은 SAT가 'NP 문제 중 가장 어려운 축'에 속한다는 것이지, P=NP인지 여부를 결정해주지는 않는다.