I know that Turing reductions, function reductions and aproximation algorithms can produce good results and aproaches to the solution of a problem, but sometimes they lost the exact solution. Is there a clasification, notation or name for this sort of functions or functors that produce a reduction of the problem (or a non determistic solution) that can be used as well as an aproaching never losing the exact solution?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Las Vegas algorithms? It is hard to see in what sense Turing reduction loses the exact solution. And what is "function reduction"? $\endgroup$– ConifoldCommented Aug 31, 2019 at 7:09
-
$\begingroup$ Yep,I'm not sure if a Turing reduction don't lost the exact solution never. A function reduction as well as an approximation can lost the exact solution. $\endgroup$– Izar UrdinCommented Aug 31, 2019 at 7:24
Add a comment
|