내 신청현황
종류	모집공고명	진행상태
신청내용이 없습니다.

알림마당

home

Reduction, 완전성과 근사가능성에서의 난이도

전문가 제언: ○ 연산 가능성과 복잡성 이론에 있어서 reduction은 결정 불가능성 또는 난해성 결과를 입증하기 위하여 세트를 다른 세트로 맵핑하는데 광범위하게 사용되어지고 있다. 난해한 불연속성 최적화 문제의 근사 해결 가능성의 연구에 있어서 근사 보존 reduction이라 불리는 적절한 긍정적인 결과도 또한 한 문제에서 긍정적인 결과(해석 기법) 또는 부정적인 결과(비-접근가능성 결과) 중의 하나를 갖고 다른 문제로 변환하는데 사용되어질 수 있다. 여러 가지 종류의 근사 보존 reduction이 조사되고 그 특성들에 대해 논의하였다. 근사 보존 reduction 하에서 완전성의 역할도 또한 분석되어졌고 근사가능성의 어려움에 대해 그것의 관계에 대해 설명하였다.

○ 컴퓨터 공학에서 reduction 개념과 순열 조합의 최초 적용은 70년대 초 Cook과 Karp에 의해서 진행되었다. 실질적으로 Cook과 Karp의 reduction 모두는 복잡성 이론 관점으로부터의 결정 문제에 대해 언급하고 있다. 어려운 최적화 문제에 대해 특성화 근사 문제 알고리즘이 논의될 때, 곧바로 그것의 근사 물성치를 연구하기 위하여 최적화 문제에 적용할 reduction의 적절한 개념이 필요하게 된다.

○ 강력한 근사 보존 reduction과 최적화 문제의 근사에 대한 구조적 이론의 시발점은 Crescenzi와 Panconesi(1991)의 논문인데, 여기에서 최초의 PTAS 보존 reduction(PTAS-reduction)이 소개되고, 이러한 형태의 reduction 하에 있는 APX에서의 최초의 완전한 문제가 제공 되어졌다. 그러나 불행하게도 논문에서 APX-완전으로 입증된 이 문제는 아주 부자연스러웠다.

저자: Ausiello, G; Paschos, VT
자료유형: 학술정보