# The complexity of checking the correctness of the problem solution on the Turing machine

There is a powerful simulation of Turing machine. At the input it takes problems of class P. At the output it gives solution for the problem. So, is it easier (in complexity theory) to test the correctness solution of the given problem than to solve this problem? If checking the solution is really easier than solving the problem, how much?

The practical side of my question is based on the fact that there is a large network of distributed computing. People for the award offer the power of their computers (their GPUs) to solve various problems from other people (from customers). We need an effective algorithm of protection against fraud when a person sends the wrong solution. If checking the correctness of the solution is really much easier than solving the problem, the customers themselves could easily check on their computers the correctness of the sent answers for which they pay. The most common problems are related to the solution of linear homogeneous integral equations and solved in a fraction of seconds, but in general the problem can be any of the class P. Thank you! I really hope for an answer.

• I don't understand the premise of your question. Your "powerful simulation of Turing machine" sounds like it's just a universal Turing machine. But what do you mean by the input being a problem in P and the output being a solution? Problems, in the CS sense of the word, don't have solutions: instances of problems have solutions. So what does your "powerful simulation" actually do? If you want to take a general problem as input (e.g., by encoding as a Turing machine) you probably can't do anything faster than simulate that machine. But for specific problems, you can surely do better, ... Feb 8, 2018 at 16:19
• ... by analogue of NP problems being seemingly easier to verify than solve. For example, one would imagine that it's easier to verify a perfect matching (just check that it's a set of edges that includes every vertex exactly once) than to compute one, even though both can be done in P. Feb 8, 2018 at 16:21
• Thank you for discussion! Of course, I am referring to special cases of general problems. Given example. Rendering equation (en.wikipedia.org/wiki/Rendering_equation) is often used to process 3d graphics. This is a homogeneous integral equation that is computed on the GPU. At the input, the Turing machine receives this equation and a set of several specific variables. How many times is it more difficult to solve this integral equation is harder than checking the correctness of the solution? Feb 8, 2018 at 17:22
• That will surely vary massively from problem to problem. If you want to ask about that specific problem, then I think you should make your question be specific to that problem. As I said, for the general case where you have to be able to accept any polytime Turing machine as the definition of the problem, I really don't think you can do anything better than just simulating the TM until it gives the answer and then checking if the answer it gave was the one you were expecting. Feb 8, 2018 at 18:01