모든 NP 문제보다 풀기 쉽지 않은 문제를 NP-complete 문제라 하는데
최초의 NP-complete 문제를 억떡계 찾아냈을까용??

모든 NP 문제를 다항시간 내에 풀 수 있는 비결정론적 튜링머신을 다항길이의 boolean expression으로 환산해서
Boolean satisfiability problem으로 풀어버릴수 있다는걸 보이는데
이게 모든 NP문제를 boolean satisfiability problem으로 다항시간 내에 환산할수 있음을 증명하기에
Boolean satisfiability problem이 NP-complete함을 증명할수 있었답니당

다행히 이 이후로 어떤 문제가 NP-complete한지 증명하려면 모든 NP문제를 그 문제로 환산할 필요없이
Boolean satisfiability problem과 같은 시간복잡도인지만 증명하면 되기땜에 수고를 덜수있죵

비결정론적 튜링머신을 Boolean expression으로 환산하는 과정은 Cook-Levin theorem을 찾아보세용