There are interesting results of the form $PCP[a(n), b(n)] = \texttt{SOMECLASS(n)}$ for multiple classes in the exponential hierarchy: the most famous one is probably $PCP[O(log(n)), O(1)] = NP$.

Are there similar theorems for larger complexity classes, such as PR, $F_\omega$, and other beyond ELEMENTARY? Do these theorems cover the complexity classes implied by proof assistants that only accept total functions?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.