The PCP theorem is the cornerstone of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems.
Теорема PCP является угловым камнем теории вычислительной сложности аппроксимации, которая исследует врождённую сложность при разработке эффективных аппроксимационных алгоритмов для различных задач оптимизации.