k-Clique Problem

SAT

Partition Problem

부분집합 A의 합=전체 합/2. 즉, Subset Sum 문제에서 목표 합 K = total/2로 두고 풀면 Partition 문제와 동일하다. S={3,1,1,2,2,1}합 T=10T = 10T=10 → 짝수 → 목표: Subset 합 = 5가능한 부분집합: {3, 2}, {1,1,2,1} 등→ Subset Sum 문제로 변환 완료

Subset Sum / Knapsack

Subset Sum: NP완전에서 아주 직관적인 문제중 하나다. 집합의 부분집합 중에서 그 합이 0인 경우가 존재하면 참이 된다 {-1, 3, -2, 4} -1+3-2=0 이 집합은 참이다. 부분집합의 합이 0이 아니라 특정 수로 정하면 Knapsack 문제가 된다.Knapsack: 배낭의 용량이 C이고, n개의 물건의 각각의 무게와 가치가 주어질 때, 배낭에 담을 수 있는 최대 가치를 찾는 문제print("fsd")

Planar 3-SAT

간선이 서로 겹치지 않고 그려질 수 있는가의 문제. ​

Exact Cover

A = {1, 4, 7};B = { 1 , 4 };C = {4, 5, 7};D = { 3 , 5 , 6 };E = {2, 3, 6, 7}; 그리고F = { 2 , 7 }.A가 선택되면 B의 원소 1과 교집합이 생기므로 B는 선택될 수 없다. B를 선택할때는 A를 선택할 수 없다. { B , D , F }는 유일한 Exact Cover 이다.

3-D Matching

X, Y, Z 가 겹치지 않게 묶여진 집합의 수가 K 개를 만족시키면 OK

NP-Complete

3-SAT3-충족 가능성 문제(3-SAT, Boolean satisfiability problem)는 NP-완전의 대표주자이고 모든 문제 환원의 기준이다. 이 문제는 참 또는 거짓의 진리 값을 가질 수 있는 3개의 문자 또는 변수 p,q,r 이 있다. 그리고 논리합으로 연결된 절 몇 개가 논리곱으로 구성된 부울 수식 f가 참이 되도록 문자의 진리 값을 구할 수 있는가를 묻는다.Hamiltonian Path / CycleHamiltonian Path: 그래프의 모든 정점을 한번씩 방문하는 알고리즘Hamiltonian Cycle: 시작점과 끝점이 동일한 헤밀턴 경로Graph Coloring그래프의 각 정점에 같은 색깔이 인접하지 않게 칠하는 방법이다. 이것으로 그래프의 불변성을 정의할 수 있다.Vertex ..