Editing Openai/6946a016-c660-8009-b7f1-a8cf4a1f3426 (section)

==== 4) 제일 구체적인 예시 1: SAT (논리식 만족 가능성) ====

===== 문제(SAT) =====

입력: 어떤 불리언 논리식 FFF (AND/OR/NOT으로 만든 식)
질문: 변수들에 참/거짓을 잘 넣어서 FFF를 참으로 만들 수 있나?

예를 들어:

F=(x∨y) ∧ (¬x∨z) ∧ (¬y∨¬z)F=(x \lor y)\ \land\ (\lnot x \lor z)\ \land\ (\lnot y \lor \lnot z)F=(x∨y) ∧ (¬x∨z) ∧ (¬y∨¬z)
===== “검증”은 왜 쉽나? =====

누가 이렇게 답을 줬다고 하자(이게 증거/certificate):
* x=참, y=거짓, z=참x=\text{참},\ y=\text{거짓},\ z=\text{참}x=참, y=거짓, z=참

그러면 우리는 논리식을 그냥 대입해서 각 괄호가 참인지 확인하면 끝이야.
* (x∨y)=(참∨거짓)=참(x \lor y) = (\text{참} \lor \text{거짓}) = \text{참}(x∨y)=(참∨거짓)=참
* (¬x∨z)=(거짓∨참)=참(\lnot x \lor z) = (\text{거짓} \lor \text{참}) = \text{참}(¬x∨z)=(거짓∨참)=참
* (¬y∨¬z)=(참∨거짓)=참(\lnot y \lor \lnot z) = (\text{참} \lor \text{거짓}) = \text{참}(¬y∨¬z)=(참∨거짓)=참

모두 참이니까 FFF는 만족 가능!
이 검증 과정은 논리식 길이에 비례해서 끝나므로 다항시간에 가능해.

그래서 SAT는 NP에 속해. “예”의 증거로 만족시키는 변수 할당을 그냥 보여주면 된다는 식으로 설명돼. Complexity Zoo<ref>{{cite web|title=Complexity Zoo|url=https://complexityzoo.net/Complexity_Zoo%3AN|publisher=Complexity Zoo|access-date=2025-12-21}}</ref>

===== 그런데 “찾기”는 왜 어려워 보이나? =====

변수가 nnn개면 가능한 할당이 '''2n2^n2n'''개야.
* 가장 단순한 방법(무식하게 전부 시도)은 최악의 경우 2n2^n2n개를 다 확인해야 해서 지수시간이 돼.

즉,
* 정답 후보를 받으면 채점(검증)은 빠른데
* 정답 후보를 처음부터 만들어내는 건 경우의 수 폭발 때문에 엄청 어려워 보이는 상황이 생겨.

이게 NP의 “감각”이야.