NP-완전 문제

NP-완전 문제(NP-Complete Problem)는 계산 복잡도 이론에서 NP(Non-deterministic Polynomial time) 클래스에 속하면서, 동시에 NP-난해(NP-Hard)한 문제를 의미한다. NP-완전 문제는 "어떤 문제의 답이 주어졌을 때, 다항 시간 안에 검증할 수 있지만, 최적해를 찾는 것은 어려운 문제"를 말한다.

개요

NP-완전 문제는 다항 시간 내에 해결 가능한 알고리즘이 존재하는지 아직 밝혀지지 않은 문제이다. 이러한 문제를 효율적으로 해결할 수 있는 알고리즘이 존재한다면, P vs NP 문제에서 P = NP가 성립하게 된다.

NP-완전 문제는 다음 두 가지 속성을 만족해야 한다.

• NP에 속함 → 어떤 주어진 해답을 다항 시간 내에 검증할 수 있음.
• NP-난해(NP-Hard) → NP의 모든 문제를 다항 시간 내에 변환(귀환)할 수 있음.

NP-완전 문제의 예시

다음은 대표적인 NP-완전 문제들이다.

• 여행하는 외판원 문제(TSP, Traveling Salesman Problem)
  • 여러 도시를 한 번씩 방문하여 최소 거리를 찾는 문제.
• 배낭 문제(Knapsack Problem)
  • 제한된 무게 내에서 최대 가치를 얻도록 아이템을 선택하는 문제.
• 빈 패킹 문제(Bin Packing Problem)
  • 최소 개수의 빈(bin)에 아이템을 효율적으로 배치하는 문제.
• 부분 집합 합 문제(Subset Sum Problem)
  • 주어진 숫자 집합에서 특정한 합을 만드는 부분 집합이 존재하는지 판별.
• 3-SAT 문제(3-Satisfiability Problem)
  • 논리식을 만족시키는 변수 조합이 존재하는지 확인하는 문제.
• 그래프 색칠 문제(Graph Coloring Problem)
  • 최소한의 색을 사용하여 인접한 정점들이 다른 색을 가지도록 색칠하는 문제.

NP-완전성 증명 (귀환, 리덕션)

어떤 문제가 NP-완전임을 증명하려면, 이미 NP-완전임이 알려진 문제에서 다항 시간 내에 변환(귀환, reduction)될 수 있음을 보여야 한다.

예를 들어:

• 3-SAT 문제가 NP-완전임이 증명됨.
  • 이를 이용해 여행하는 외판원 문제가 NP-완전임을 증명할 수 있음.

코드 예제

다음은 NP-완전 문제인 배낭 문제(0/1 Knapsack Problem)의 예제이다.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# 예제 실행
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))

출력 결과 예시:
7

NP-완전 문제의 해결 방법

NP-완전 문제는 일반적으로 다항 시간 내에 해결할 수 없기 때문에, 다음과 같은 방법이 사용된다.

• 근사 알고리즘(Approximation Algorithm)
  • 최적해에 가까운 해를 빠르게 찾음.
• 휴리스틱 알고리즘(Heuristic Algorithm)
  • 탐색 공간을 줄여 현실적인 해를 구함.
• 지수적 알고리즘(Exponential Algorithm)
  • 완전 탐색(Brute Force) 기반.
• 동적 계획법(Dynamic Programming)
  • 부분 문제를 해결하여 전체 문제를 해결.

응용

NP-완전 문제는 다음과 같은 분야에서 활용된다.

• 물류 및 최적화
  • 경로 최적화, 스케줄링 문제.
• 네트워크 및 보안
  • 데이터 라우팅, 암호학 문제.
• 운영체제 및 컴퓨터 과학
  • 메모리 할당, 작업 스케줄링.

같이 보기

• P vs NP 문제
• NP-난해 문제
• 그리디 알고리즘
• 배낭 문제
• 여행하는 외판원 문제

참고 문헌

• Garey, Michael R., and David S. Johnson. "Computers and Intractability: A Guide to the Theory of NP-Completeness." W. H. Freeman, 1979.
• Cook, Stephen. "The Complexity of Theorem-Proving Procedures." Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971.