<보기>에서 설명하는 문제 부류에 속하지 않는 것으로 가장 … | [9급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[9급 서울시 알고리즘] 26년 1회차
<보기>에서 설명하는 문제 부류에 속하지 않는 것으로 가장 옳은 것은?• 현재 이 부류 문제에 대한 다항 시간의 알고리즘이 알려져 있지 않다.
• 이 부류의 문제 사이에는 다항 시간 환원(reduction)이 가능하다.
• 이 부류에 속하는 문제 중 어느 한 문제만 다항식 시간에 해결되면, 모든 다른 문제들이 다항 시간에 해결 가능하다.
1
만족성(SAT) 문제
2
부분 집합의 합(subset sum) 문제
3
0-1 배낭 결정(knapsack decision) 문제
4
모든 쌍 최단 경로(all pairs shortest paths) 문제
해설
등록된 해설이 없습니다.
오류나 개정된 내용이 보이면 알려주세요