1
다음과 같은 NP 완전 문제가 있습니다. N x N 필드 및 m 노드 집합과 노드의 연결 그래프 (즉, 가장자리가 모든 쌍을 나타내는 무향 그래프 각 노드와 접촉하는 노드), 접촉 범위 R (N × N 필드와 동일한 길이 단위), 연결 그래프를 존중하는 필드에서 노드의 위치를 찾는다 접촉하지 않는 R과 Eny 쌍이 R보다 멀리 떨어져 있음), 또는 그러한 배치가 존재하지 않는다는 것을 보여 주어야한다.'노드 배치'문제를 줄일 수있는 잘 알려진 NP 완성 문제가 있습니까?
잘 알려진 NP 완전 문제가 있습니까?이 문제를 줄일 수 있습니까? (문제의 최적화 버전도 고려할 수 있습니다. 즉, 최적의 배치를 찾으려고합니다.)
흠. 당신은 당신의 문제가 NP 완전하다고 주장하는 사람입니다. 그래서 당신이 당신의 NP 문제를 얻을 수 있다는 증거를 가지고 있다는 것을 의미하지는 않습니까? –
NP-Complete의 "완전한"부분은 다른 Np-Complete 문제로 축소 될 수 있음을 의미합니다. 당신이 그걸 모를 경우, 당신의 문제는 단지 "NP"가 아니라 "NP- 완료"입니다. – SoapBox
@SoapBox - 아니요 : "완료"부분은 반대로 NP가 아닌 다른 문제를 줄일 수 있음을 의미합니다. (더 정확하게는 NP 경도이고 NP 완성은 NP와 NP입니다.) – sdcvvc