P-완전 문제 및 근사 솔루션

우리는 P-완전 문제의 클래스를 연구하고 다음과 같은 내용을 보여준다: i) 모든 상수 ε ≫0에 대해 ε-근사 솔루션을 선형 시간 내에 찾을 수 있는 P-완전 문제가 존재한다. ii) 최적해에 점점 가까워지는 선형 시간 근사 솔루션을 찾을 수 있는 P-완전 문제가 존재한다 (문제 크기가 증가함에 따라). iii) 근사 문제가 또한 P-완전인 P-완전 문제가 존재한다.