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