질문, 건의, 요청 사항은 방명록(guest)에 올려 주십시오.


NP-completeness의 개념을 다룬다. 알고리즘의 개념, Turing Machine의 개념을 도입하면서, P와 NP에 대해 다루고, NP-hard 및 NP-completeness를 소개한다. NP-completeness의 증명에 필요한 reduction의 개념과, NP-completeness 문제 자체와 그 증명이 가지는 의의를 논한다.
NP-completeness 문제를 다루는 접근법 중 approximation 방법을 소개하며, TSP(Traveling Salesman Problem)의 special case를 그 예로 제시한다. 마지막으로 PTAS(Polynomial Time Approximation Scheme)와 FPTAS(Fully PTAS)의 class를 소개한다.
Posted by AALab