P와 NP: 답을 찾는 일과 확인하는 일의 차이

P와 NP를 비교할 때의 질문은 “정답 후보를 효율적으로 확인할 수 있는 문제를 효율적으로 풀 수도 있는가?”입니다. NP를 단순히 어렵거나 느린 문제의 이름으로 쓰면 의미가 달라집니다.

선수 지식: 입력 크기와 다항·지수 증가의 차이, 그래프의 정점·간선을 알아야 합니다.

• 찾기와 검증을 다른 작업으로 구분합니다.
• 결정 문제와 최소 비용을 구하는 최적화 문제를 구분합니다.

제시된 방문 순서를 확인하는 일부터 해 봅니다

도시를 모두 한 번씩 지나 출발점으로 돌아오는 순서가 있는지 묻는다고 해 보겠습니다. 누군가 [0,1,2,0]을 후보로 내놓으면 모든 순서를 새로 찾지 않고도 각 도시가 한 번씩 나오는지, 이어지는 간선이 있는지, 마지막이 출발점인지 확인할 수 있습니다. 이 후보처럼 정답 확인에 함께 제공하는 자료를 증명서라고 부릅니다.

검사 함수가 true를 돌려줬다는 것은 제시된 후보가 조건을 만족한다는 뜻입니다. false이면 그 후보가 틀렸다는 뜻일 뿐, 다른 후보까지 모두 없다는 증거는 아닙니다. 이 차이를 놓치면 검증 함수를 전체 해법처럼 오해하게 됩니다.

P도 NP에 포함됩니다

여기서는 예·아니요로 답하는 결정 문제를 이야기합니다. P는 입력 크기에 대한 다항 시간 알고리즘으로 풀 수 있는 문제들의 부류입니다. NP는 예라는 답에 대해 다항 크기의 증명서를 다항 시간에 확인할 수 있는 문제들의 부류입니다. P 문제는 답을 계산해 확인할 수 있으므로 P에 속하면 NP에도 속합니다.

P=NP인지는 아직 해결되지 않았습니다. 따라서 어떤 알고리즘을 아직 모른다는 이유만으로 그 문제에 빠른 알고리즘이 존재하지 않는다고 단정하면 안 됩니다. 여기서 “빠름”은 특정 PC의 몇 밀리초보다 입력이 커질 때의 점근적 다항 시간 의미입니다. 높은 차수나 큰 상수 때문에 다항 알고리즘도 실용적으로 느릴 수 있습니다.

가장 싼 경로와 예산 안의 경로 존재는 다른 질문입니다

외판원의 최소 비용을 직접 구하는 것은 최적화 문제입니다. “비용 K 이하의 순환이 존재하는가?”는 결정 문제입니다. P·NP의 정의를 적용할 때는 이처럼 어떤 질문을 분류하는지 먼저 밝혀야 합니다. NP-hard라는 말도 “NP와 똑같다”거나 “컴퓨터가 못 푼다”는 일상적 표현으로 바꿀 수는 없습니다.

아래 코드는 3개 이상 정점의 Boolean 인접 행렬과 후보 순환을 받는 작은 검증 예제입니다. 그래프 모양을 확인하는 부분까지 포함하면 O(n²), 후보 자체의 방문·간선 확인은 O(n)입니다. 이것은 P와 NP의 관계를 증명하는 코드가 아니라 찾기와 확인의 입력·작업이 어떻게 다른지 경험하기 위한 예제입니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function checkHamiltonianCycle(graph, route) {
  if (!Array.isArray(graph) || graph.length < 3 || !Array.isArray(route)) return false;
  const n = graph.length;
  for (let i = 0; i < n; i++) {
    if (!Array.isArray(graph[i]) || graph[i].length !== n) return false;
    for (let j = 0; j < n; j++) if (typeof graph[i][j] !== 'boolean') return false;
  }
  if (route.length !== n + 1 || route[0] !== route[n]) return false;
  const seen = new Set();
  for (let i = 0; i < n; i++) {
    const from = route[i], to = route[i + 1];
    if (!Number.isInteger(from) || from < 0 || from >= n || !Number.isInteger(to) || to < 0 || to >= n) return false;
    if (seen.has(from) || graph[from][to] !== true) return false;
    seen.add(from);
  }
  return seen.size === n;
}

const graph = [[false, true, true], [true, false, true], [true, true, false]];
console.log(checkHamiltonianCycle(graph, [0, 1, 2, 0]));
console.log(checkHamiltonianCycle(graph, [0, 1, 1, 0]));

node cycle-certificate.mjs

true
false

비용과 적용 범위

시간: 예제의 행렬 형식 검사 O(n²), 후보 경로 검사 O(n)입니다.

공간: 방문 집합 O(n) 추가 공간입니다.

분석 조건: n≥3의 Boolean 정사각 행렬과 도시 인덱스 순환 후보입니다. 결정 문제의 효율적 후보 검증을 보여 주며 탐색 알고리즘이나 미해결 문제의 해답은 아닙니다.

직접 확인해 보기

후보 [0,1,2,0]이 실패했다면 모든 정점을 방문하는 순환이 없다고 결론내릴 수 있나요?

함께 읽을 글

• 그래프 이론 기본 개념 — 정점과 간선, 경로를 나타내는 뜻부터 확인합니다.
• 평면 그래프·오일러·해밀턴 경로 — 모든 정점을 방문하는 조건과 간선을 방문하는 조건을 구분합니다.

참고 자료

• Clay Mathematics Institute — P vs NP — 후보 검증과 답 찾기의 관계, P 대 NP 문제가 미해결임을 확인합니다. 예제는 별도로 작성했습니다.