1. Cook-Levin 정리에 의하면 3-SAT은 NP-hard입니다. (증명은 겁나 어렵습니다)

2. 다른 문제들은 보통 3-SAT에서 환원 가능(reducible)한 것을 보임으로써 증명합니다.

어떤 문제를 풀기 위해 다른 문제를 끌고 온다고 생각해 봅시다. 즉 문제 A를 문제 B의 특수 케이스로 변형하는 것입니다. 이제 문제 B를 풀 수 있다면 A도 당연히 풀 수 있습니다. 이것을 환원 (reduction) 이라고 합니다.

이제 문제를 "효율적으로", 즉 "다항 시간 안에" 푼다고 생각해 봅시다. 다항 시간 안에 풀 수 있는 문제를 P 문제라고 합니다. A를 B로 변형하는 게 다항 시간 안에 가능하고, B를 다항 시간 안에 풀 수 있다면, A도 다항 시간 안에 풀 수 있습니다. 반대로 A를 다항 시간 안에 풀 수 없다면 B도 다항 시간 안에 풀 수 없습니다. 특수 케이스조차 다항 시간 안에 안 풀리니까요.

SAT이라는 문제가 있습니다. 간단히 말하면 "이 논리식이 TRUE가 되도록 변수에 TRUE/FALSE 값을 지정할 수 있는가?" 입니다. 놀랍게도 다항 시간 안에 답을 검증할 수 있는 문제 (NP 문제)는 전부 다항 시간 안에 SAT로 환원할 수 있습니다. 그런 문제를 NP-Hard 문제라고 하고, 이 정리를 Cook-Levin 정리라고 합니다. 이 정리의 증명은 꽤 복잡하기 때문에 학부 수준에서도 별로 다뤄지지 않습니다. NP-Hard 문제를 아무거나 다항 시간 안에 풀 수 있으면 모든 NP 문제를 다항 시간 안에 풀 수 있습니다. NP-Hard 문제로 환원한 다음 그걸 다항 시간 안에 풀면 됩니다. 안타깝게도 NP-Hard 문제들 중 지금까지 다항 시간 안에 풀린 것은 아무것도 없고, 반대로 그게 불가능하다는 증명도 발견되지 않았습니다.

어떤 문제 A가 NP-Hard임을 증명하려는데 위의 정의에 입각해서 하려면 너무 골치아프기 때문에, 이미 NP-Hard임이 증명된 다른 문제 B를 끌고 와서 A로 환원합니다. 그러면 B도 NP-Hard임이 자연스럽게 유도되는데, 어떤 NP 문제든 A로 환원할 수 있고, A를 B로 환원할 수 있으니까 그 방법으로 NP 문제를 B를 환원할 수 있기 때문입니다.

마지막 문단에 오타가 있습니다.

어떤 문제 A가 NP-Hard임을 증명하려는데 위의 정의에 입각해서 하려면 너무 골치아프기 때문에, 이미 NP-Hard임이 증명된 다른 문제 B를 끌고 와서 A로 환원합니다. 그러면 A도 NP-Hard임이 자연스럽게 유도되는데, 어떤 NP 문제든 B로 환원할 수 있고, B를 A로 환원할 수 있으니까 그 방법으로 NP 문제를 A를 환원할 수 있기 때문입니다.