Planar 3-SAT

Planar 3-SAT

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

  • format_list_bulleted NP-Complete
  • · 2025. 6. 26.
Exact Cover

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 이다.

  • format_list_bulleted NP-Complete
  • · 2025. 6. 26.
3-D Matching

3-D Matching

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

  • format_list_bulleted NP-Complete
  • · 2025. 6. 26.
NP-Complete

NP-Complete

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

  • format_list_bulleted NP-Complete
  • · 2025. 6. 24.
P=NP? P≠NP?

P=NP? P≠NP?

P 대 NP 문제에 대한 정확한 설명은 Stephen Cook 이 그의 선구적 논문 “The Complexity of Theorem‑Proving Procedures” (1971) 과 같은 시기에 러시아 학자인 Leonid Levin 논문으로 부터 출발했다. Cook-Levin 정리 발표 이후 Richard Karp가 “Reducibility Among Combinatorial Problems” (1972) 논문을 통해 21가지 문제가 NP-완전임을 증명하였다. P=NP는 모든 NP 문제를 P 문제처럼 다항 시간 안에 해결할 수 있는지를 묻는 문제이다. 클래스 P는 결정론적 튜링 기계로 다항 시간 안에 해를 찾을 수 있는 문제들의 집합이고, NP는 해답이 주어졌을 때 그 해를 다항 시간 안에 검증할 수..

  • format_list_bulleted General
  • · 2025. 6. 24.