The complexity of checking the correctness of the problem solution on the Turing machine
What you might be looking for is an application of probabilistically checkable proofs (PCPs) for verifying computation. People have been working lately on making this practical, see for example Computational integrity with a public random string from quasi-linear PCPs, and other works by Eli Ben-Sasson and Alessandro Chiesa. At the moment this is unfortunately still a mostly theoretical concept.