NP-완비(complete) 이론에 대한 설명으로 가장 옳지 않은 것은? | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
NP-완비(complete) 이론에 대한 설명으로 가장 옳지 않은 것은?
1
문제 A가 어떤 알려진 NP-하드(hard) 문제 B로 다항 시간 내 환원된다면 문제 A는 NP-하드이다.
2
N개의 노드, M개의 간선이 있는 그래프의 최소 신장 트리를 찾는 문제는 NP에 속한다.
3
NP-complete에 속하는 문제 중 하나를 푸는 다항식 시간 알고리즘이 발견된다면 P=NP가 된다.
4
무방향 해밀토니안 사이클(Hamiltonian-cycle) 문제는 NP에 속한다.
해설

옳지 않은 설명은 A가 NP-하드 문제 B로 환원되면 A가 NP-하드라는 것이다.

환원 방향이 반대다. 알려진 NP-하드 문제 B를 A로 다항 시간에 환원할 수 있어야 A가 B만큼 어렵다고 할 수 있으며, A를 B로 환원하는 것은 A가 B보다 어렵지 않다는 뜻일 뿐이다.

  • 최소 신장 트리: 크루스칼·프림 알고리즘으로 다항 시간에 풀리는 P 문제이고, P는 NP에 포함되므로 NP에 속한다.
  • NP-완비 문제의 다항 시간 해법: 모든 NP 문제가 그 문제로 다항 시간 환원되므로 P=NP가 된다.
  • 해밀토니안 사이클: 주어진 정점 순서가 해밀토니안 사이클인지 다항 시간에 검증할 수 있으므로 NP에 속한다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기