1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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, ... $\endgroup$ – David Richerby Feb 8 '18 at 16:19
  • 2
    $\begingroup$ ... 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. $\endgroup$ – David Richerby Feb 8 '18 at 16:21
  • $\begingroup$ 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? $\endgroup$ – John W. Feb 8 '18 at 17:22
  • $\begingroup$ 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. $\endgroup$ – David Richerby Feb 8 '18 at 18:01
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.