KARP는 최적화 문제에서 의사 결정 문제로 인해 감소합니다

cs.stackexchange https://cs.stackexchange.com/questions/125328

문제

요리를 줄이면 문제의 결정과 최적화 버전은 서로 절감 할 수있는 다항식 시간입니다.

요리 절감에 초점을 맞추는 것은 문제의 결정 버전에서 최적화 버전으로 자연스러운 karp 감소가 존재합니다.대화도 사실입니까?

도움이 되었습니까?

해결책

Yuval Filmus의 의견 덕분에 KARP 감축이 결정 문제에 대해 정의되어 있기 때문에 제 질문이 의미가 없습니다.쿡 감소는 더 많은 freeness를 허용하기 때문에 의사 결정 문제에서 최적화 문제로 인해 쿡 감소에 대해 이야기하는 것이 좋습니다. 그러나 이것은 karp 감소에 해당하지 않습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top