근사 알고리즘

NP-난해한 최적화 문제에서 최적해 대신, 최적값의 정해진 비율 이내임이 증명된 해를 다항 시간에 구하는 알고리즘이다. 정점 덮개는 2배 이내, 삼각 부등식을 따르는 외판원 문제는 1.5배 이내가 보장된다. 문제마다 가능한 비율이 다르다. 배낭 문제는 최적에 원하는 만큼 다가갈 수 있지만, 일반적인 외판원 문제는 P ≠ NP 인 한 어떤 상수 비율도 보장할 수 없다. PCP 정리는 이런 근사의 한계를 증명하는 도구다.