2 - SAT 문제 (백서)

1. 정의
불 방정식 을 지정 하여 불 변수의 진가 할당 이 전체 방정식 을 진짜 문제 로 만 들 었 는 지 판단 하고 불 방정식 의 만족 성 문제 (SAT) 라 고 불 린 다.SAT 문 제 는 NP 가 완전 하지만 일정한 제한 조건 을 충족 하 는 SAT 문제 에 대해 서 는 효과적으로 풀 수 있다.
범례 를 합 친 각 자구 의 문자 개수 가 두 개 를 넘 지 않 는 다 면 대응 하 는 SAT 문 제 를 2 - SAT 문제 라 고 할 수 있다.
(a ∨ b) ∨ a (a ∨ b) ∨ a 령 a 는 가짜 이 고 b 는 진짜 이 며 (a ∨ b) ∨ (b ∨ c) ∨ (€ c ∨ a) ∨ (a ∨ b) ∨ (b ∨ c) ∨ a 와 b 는 진짜 이 고 c 는 가짜 이 며 만족 할 수 있다. ， 2-SAT
우선 『 (함 축 됨) 을 이용 하여 각 자구 (a ∨ b) (a ∨ b) 를 등가 의 (€ a ∨ b) ∧ (€ b ∨ a) (€ a ∨ b) ∧ (€ b ∧ a) ∧ (€ b ∨ a) ∨각 불 변수 x 에 대해 서 는 구조 두 개의 정점 이 각각 x 와 € x € x 를 대표 하 며, ▲ 관 계 를 방향 변 으로 하여 방향 도 를 만 듭 니 다. 이때 a 점 이 b 점 에 도달 할 수 있다 면 a 가 진실 일 때 b 도 진실 임 을 나타 냅 니 다. 따라서 그림 의 같은 강 한 연결 분량 의 모든 불 값 은 같 습 니 다.
만약 에 어떤 불 변수 x, x 와 € x 와 € x 가 같은 강 한 연결 분량 에 존재 한다 면 전체 불 공식 값 을 진실 하 게 할 수 없습니다. 반대로 이런 불 변수 가 존재 하지 않 는 다 면 모든 불 변수 x 에 대해 서 는
x 가 있 는 강 한 연결 분량 의 토폴로지 순 서 는 € x 가 있 는 강 한 연결 분량 에 있 습 니 다.
이 공식 값 을 정말 적합 한 불 변수 할당 으로 만 드 는 것 이다.
2. 제목 설명
(1)POJ 3683