2-sat1 투셋(2-sat) 2-SAT 문제를 해결하기 앞서 먼저 용어 정리부터 필요하다. CNF (Conjunctive Normal Form) $(x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3) \wedge (x_2 \vee \neg x_3 \vee x_4)$... $\vee$로 이루어진 절이 최대 k개이면 k-CNF 모든 k-CNF 는 3-CNF로 변형 가능 k-SAT(k-satisfiability problem) k-SAT 문제는 $\vee$(OR)로 이루어진 k개의 논리 변수가 $\wedge$(AND) 로 묶인 논리식을 만족(True)시키는 조합을 찾는 문제이다. k-SAT은 3-SAT으로 변형 가능하기 때문에 3-SAT과 2-SAT만 의미가 있음 3-SAT은 NP-compl.. 2019. 10. 18. 이전 1 다음
