0
제목은 전체 질문을 다루고 있습니다. NP 완전 문제에 대한 제안 된 해결책이 정확할 확률이 m %라는 것을 확실하게 말할 수있는 함수를 도출 할 수 있습니까?NP 완성 문제의 해답 확률을 찾는 것이 가능합니까?
제목은 전체 질문을 다루고 있습니다. NP 완전 문제에 대한 제안 된 해결책이 정확할 확률이 m %라는 것을 확실하게 말할 수있는 함수를 도출 할 수 있습니까?NP 완성 문제의 해답 확률을 찾는 것이 가능합니까?
나는 의심 스럽다. 예를 들어 임의 함수의 최적 확률은 numberOfOptimalSolutions/searchSpace
입니다. 그래서 당신이 그 해답을 알고 있다면 numberOfOptimalSolutions (NP 완전 문제에 대한 최적 해를 찾는 것보다 IIRC가 항상 더 어려움)를 추론 할 수 있습니다.
"여행 세일즈맨을 찾는 중"책은 TSP의 각 구성 휴리스틱에 대해 최적의 솔루션에서 최악의 시나리오에 얼마나 가까운지 (또는 멀리) 있는지 나열합니다. 그것은 또한 algo의 (일부)에 대한 올바른 평균 비율을 언급하지만 IIRC는 아마도 샘플링을 기반으로하고 문제가 클수록 악화됩니다.