주어진 후보 솔루션의 품질을 평가하는 것보다 최적의 솔루션을 생성하는 것이 훨씬 쉬운 최적화 문제의 알려진 자연적인 예가 있습니까?
구체성을 위해, 우리는 폼의 다항식 시간 풀수 최적화 문제를 고려할 수있다 : “특정 X를 최소화 “여기서, F : { 0 , 1 } * × { 0 , 1 } * → N # P-hard입니다. 이러한 문제는 분명히 존재합니다 (예를 들어, f 를 계산할 수없는 경우에도 모든 x에 대해 f ( x , 0 ) = 0 을 가질 수 있음 ).하지만이 현상을 나타내는“자연적인 ”문제를 찾고 있습니다.
f(x,y)f:{0,1}∗×{0,1}∗→N
f(x,0)=0
x
f
답변
논문 [1]에서 목적 함수 값을 계산하는 것이 NP-hard 임에도 불구하고 최적의 요소를 찾는 데 다항식 시간이 걸린다는 특성에 문제가있다 (이는 주어진 후보 솔루션의 품질을 평가하는 것도 NP-hard임을 의미한다) ).
[1] TCECheng, Y.Shafransky, CTNg. 최적화 문제의 NP-hardness를 증명하기위한 대체 방법. 유럽 운영 연구 저널 248 (2016) 52–58.
야코프 샤프란 스키
답변
다음은 다항식 시간에 솔루션을 생성 할 수 있지만 주어진 솔루션을 평가하는 것은 NP- hard입니다.
n,k
k≤n
n
k
T(n,k) k
참고 : 솔루션이 최적 인지 여부 만 확인하려는 경우 Turan 그래프가 고유 한 최적 인 것으로 알려져 있으므로 후보 구조를 간단한 구조의 Turan 그래프와 비교하기에 충분합니다. . 다른 한편으로, 우리 는 질문에서 요청한대로 후보 솔루션 의 품질 , 즉 그것이 가능한지 여부와 그것이 최적의 거리와 얼마나 떨어져 있는지 평가하려면, 그것이 최대 도당을 만족시키는 지 확인해야합니다 강제.