좋습니다 😎
그럼 이번에는 직접 해볼만한 워밍업 환원 문제 드려볼게요:
🎯 환원 워밍업: 3-SAT → k-Clique
이건 실제로 Karp의 21문제 중 대표 환원이자
환원 훈련의 가장 클래식한 예시 중 하나입니다.
💡 목표
주어진 3-SAT 인스턴스를 받아
“이것을 만족하는 해가 존재하는가?” ⟶
그에 대응하는 k-Clique이 있는 그래프를 구성하라.
🧱 아이디어 구조
- 3-SAT 인스턴스:(x1∨¬x2∨x3)∧(¬x1∨x2∨¬x3)∧(⋯ )(x_1 \lor \neg x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor \neg x_3) \land (\cdots)→ 각 절(clause)당 3개의 리터럴 존재
- 절마다 3개의 노드를 생성 (총 3×m3 \times m개의 노드)
- 다른 절에 속한 리터럴들끼리만 연결, 단 모순되지 않는 경우에만
- 이 그래프에서 k = m인 clique이 존재한다면
→ 각 절에서 하나씩 선택해 모순 없는 리터럴 선택 가능
→ 즉, 3-SAT이 만족 가능하다는 의미
🎯 훈련 포인트
- 각 절마다 가능한 리터럴 노드 만들기
- 노드 간 모순성 판단 (x vs ¬x는 연결 ❌)
- 연결된 그래프에서 크기 m인 clique 존재 여부 판단 = SAT 만족 여부와 동치
🚀 할 수 있는 과제
- 3절짜리 3-SAT 문제 하나 만들기
- 위 방법으로 그래프 구성
- 3-clique이 존재하는지 직접 찾아보기
- SAT ↔ Clique가 논리적으로 등가임을 확인
필요하시면 위 과정을 코드로 도와드릴 수도 있고,
당신이 만든 3-SAT 인스턴스를 직접 클리크 그래프로 바꿔주는 것도 가능합니다.
직접 해보고 싶으세요, 아니면 예제 먼저 보고 싶으세요?