3-SAT 충족 (상전이 지점)
마스터의견: 0
부울 변수 \(x_1, x_2, \dots, x_n\)이 있다. \(m\)개의 절(clause)이 주어지며, 각 절은 세 개의 리터럴(literal)의 논리합(\(\lor\))이다. 리터럴은 \(x_i\) 또는 그 부정 \(\lnot x_i\)이며, 입력에서는 부호 있는 정수 \(\pm i\)로 표현된다(\(+i\)는 \(x_i\), \(-i\)는 \(\lnot x_i\)).
전체 식은 모든 절의 논리곱(\(\land\))이다. 모든 절을 동시에 참으로 만드는 변수 할당을 하나 찾아 출력하여라(각 절에서 최소 한 리터럴이 참이면 그 절은 참이다).
이 문제는 3-SAT로, 대표적인 NP-완전 문제이다. 다항 시간 알고리즘은 알려져 있지 않으며, 존재한다면 \(P = NP\)가 증명된다. 게다가 이 인스턴스들은 절/변수 비율 \(m/n \approx 4.26\), 즉 충족 가능성 상전이(phase transition) 부근에서 생성되어 탐색이 가장 어려운 영역에 놓여 있다. 모든 인스턴스는 충족 가능함이 보장된다.
모든 절을 만족시키는 어떤 할당이든 정답으로 인정된다.
\(3 \le n \le 400\)
\(1 \le m \le 2000\)
각 절은 세 리터럴로 이루어지며 \(1 \le |\ell_k| \le n\), \(\ell_k \ne 0\).
모든 인스턴스는 충족 가능함이 보장된다.
첫 줄에 변수의 수 \(n\)과 절의 수 \(m\)이 주어진다.
다음 \(m\)개의 줄에 각 절을 이루는 세 리터럴 \(\ell_1\ \ell_2\ \ell_3\)이 주어진다. 각 \(\ell_k\)는 \(0\)이 아닌 정수이며 \(1 \le |\ell_k| \le n\)이다.
모든 절을 만족시키는 할당을 출력한다. \(n\)개의 \(0\)/\(1\) 값을 공백으로 구분하여 한 줄에 출력하거나(왼쪽부터 \(x_1, \dots, x_n\)), 또는 길이 \(n\)의 \(0\)/\(1\) 문자열 한 줄로 출력해도 된다. \(1\)은 참, \(0\)은 거짓을 뜻한다.
3 3
1 2 3
-1 2 3
1 -2 3
1 1 1세 절 모두 리터럴 \(x_3\) 또는 \(x_2\)로 참을 만들 수 있다. 예를 들어 \(x_1=x_2=x_3=1\)이면 모든 절이 만족된다.
3 2
-1 -2 3
1 -2 -3
001\(x_1=0, x_2=0, x_3=1\)로 두면 첫 절은 \(\lnot x_1\)이 참, 둘째 절은 \(\lnot x_2\)가 참이 되어 모두 만족된다. 답은 문자열 001로도 출력할 수 있다.
riseoj 작성
출처 Original
평가 및 의견
3-SAT 충족 (상전이 지점)
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
3-SAT 충족 (상전이 지점)