Я знаком со многими результатами, в которых используется теорема PCP (главным образом в приближенных алгоритмах), но я никогда не сталкивался с четким объяснением теоремы PCP (то есть, что ).N P = P C P (O(log( н ) ) , O ( 1 ) )Nпзнак равнопСп(О(журнал(N)),О(1))\mathsf{NP} =...