연산 이론상의 문제 유형에 대한 설명으로 옳지 않은 것은? | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 24년 1회차
연산 이론상의 문제 유형에 대한 설명으로 옳지 않은 것은?
1
P는 다항식 시간에 해결할 수 있는 문제군이다.
2
NP는 비결정론적 다항식 시간에 해결할 수 있는 문제군이다.
3
어떤 NP-Complete 문제에 대해서 다항식 시간에 해결할 수 있는 알고리즘을 찾아내면, 다른 모든 NP-Complete 문제도 다항식 시간에 해를 구할 수 있다.
4
NP-Complete 문제들 중에는 NP에 속하지 않는 문제도 있다.
해설
옳지 않은 것은 NP-Complete 문제 중에 NP에 속하지 않는 문제가 있다는 설명이다.
NP-Complete는 정의상 NP에 속하면서 모든 NP 문제가 다항식 시간에 환원되는 문제이므로, 모든 NP-Complete 문제는 NP에 속한다. NP에 속하지 않을 수 있는 것은 NP-Hard 문제이다.
- P를 다항식 시간에 해결할 수 있는 문제군으로 설명한 것은 옳다.
- NP를 비결정론적 다항식 시간에 해결할 수 있는(해를 다항식 시간에 검증할 수 있는) 문제군으로 설명한 것은 옳다.
- 모든 NP 문제가 각 NP-Complete 문제로 환원되므로, 하나를 다항식 시간에 풀면 다른 NP-Complete 문제도 다항식 시간에 풀린다는 설명은 옳다.
오류나 개정된 내용이 보이면 알려주세요