컴퓨터 과학 전공에게 NP- 완전성을 가르치는 가장 좋은 방법에 대한 질문에 관심이 있습니다. 특히 Karp 축소를 사용하거나 Turing 축소를 사용하여 가르쳐야합니까?

NP- 완전성 및 축소 개념은 모든 컴퓨터 과학 전공이 배워야 할 개념이라고 생각합니다. 그러나 NP- 완전성을 가르 칠 때 Karp 감소의 사용에는 몇 가지 단점이 있음을 알았습니다.

우선, 일부 학생에게는 Karp 감소가 불필요하게 혼동되는 것 같습니다. 축소에 대한 직관적 인 개념은 “문제 X를 해결하는 알고리즘이 있다면 그것을 사용하여 문제 Y도 해결할 수 있습니다”입니다. 매우 직관적이지만 Karp 감소보다 Turing 감소에 훨씬 더 좋습니다. 결과적으로, NP- 완전성을 증명하려는 학생들은 직관에 의해 길을 잃고 잘못된 증거를 형성합니다. 두 종류의 감축을 가르치고 Karp 감축의 이러한 측면을 강조하려고하면 때로는 불필요한 형식주의처럼 느껴지고 불필요한 수업 시간과 불필요한 기술적 시간에 대해 학생들의주의를 기울입니다. 우리가 왜이 더 제한적인 축소 개념을 사용하는지는 자명하지 않습니다.

나는 Karp 감소와 Turing (Cook) 감소의 차이점과 이들이 어떻게 NP- 완전성의 다른 개념을 이끌어 내는지 이해합니다. 나는 Karp 감소가 복잡성 클래스 사이의 구별을 더 세밀하게 제공한다는 것을 알고 있습니다. 따라서 복잡성 이론에 대한 진지한 연구를 위해 Karp 감소는 분명히 올바른 도구입니다. 그러나 이것을 배우고 복잡한 이론에 빠지지 않을 컴퓨터 과학 학생들에게는, 이러한 미세한 구별이 중요한지 확실하지 않다.

마지막으로, 학생으로서, 나는 “길이 학”과 같은 문제를 겪었을 때 당황한 느낌을 기억합니다. 혼란 스러웠던 것은이 문제가 분명히 어렵다는 것입니다. 다항식 시간 알고리즘은 P=NP

; 이 문제를 해결하는 것은 팽팽한 문제를 해결하는 것만 큼 어렵습니다. 그러나, 직관적으로 타우 톨 로지가 만족 스럽기만큼 어렵지만, 타우 톨 로지가 NP-hard가 아닙니다. 그렇습니다. 나는 이것이 왜 그런지 오늘 이해합니다. 그러나 당시 나는 이것에 당황한 것을 기억합니다. (마지막으로 이해 한 후에 내 머릿속에 갔던 것은 : 어쨌든 우리는 왜 NP-hard와 co-NP-hard를 구별 할 수 있는가? 실제적인 관점에서, 공동 NP- 경도는 본질적으로 NP- 경도와 실질적으로 동일한 결과를 갖는 것으로 보인다. 그래서 우리는 왜이 차이에 매달리는가? 답이지만, 학생으로서, 이것은 단지 주제가 더 비전적이고 동기 부여가되게한다는 것을 기억합니다.)

제 질문은 이것입니다. 학생들에게 NP- 완전성을 가르 칠 때 Karp 축소 또는 Turing 축소를 사용하여 가르치는 것이 더 낫습니까? 튜링 감소를 사용하여 NP- 완전성 개념을 가르치려고 한 사람이 있습니까? 그렇다면 어떻게 되었습니까? Turing 축소를 사용하여 개념을 가르쳤고 Karp 축소와 관련된 개념적 문제를 건너 뛰면 명백한 함정이나 단점이 있습니까?

관련 : 참조 여기 와 여기 가 NP-경도와 공동 NP-경도를 구분하는 우리를 수 있기 때문에 우리가 문헌에서 카프 절감을 사용하는 이유가 있음을 언급한다. 그러나이 능력이 모든 CS 전공에서 취해야하는 알고리즘 클래스의 학습 목표에 중요한지 여부에 대한 교육적 관점에 초점을 맞춘 대답은 보이지 않습니다. 비슷한 토론이있는 cstheory.SE 도 참조하십시오 .

답변