0
$\begingroup$

I have been reading about how to test the undecidability of a problem, and some tests talk about the reduction technique. For what I could understand of this technique is that if I want to prove that problem X is undecidable I can take a problem Y which has already been proven to be undecidable. Then by using logic or mathematical manipulation, I try to reduce or get an instance of problem X by modifying problem X, am I right?

So for example, if I want to test the undecidability of problem X, it would be fair if I pick up, for example, the undecidability of the detection of computer viruses, as stated by Cohen, as an undecidable problem by applying reduction to it, would that be fine?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

To prove that problem X is undecidable you can reduce a problem Y (which has already been proved to be undecidable) to X. In fact if Y<mX then we know that X is at least as much hard as Y is. So what you have to do is to show a function f that maps instances of problem Y in instances of problem X, so that if y is an instance of Y with answer "yes" than f(y)=x is an instance of problem X with answer "yes", and if y is an instance of Y with answer "no" than f(y)=x is an instance of problem X with answer "no".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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