11.1 Reductions Flashcards
1
Q
What is a (many-to-one) reduction?
A
A reduction is a function which takes in a predicate and maps it to another predicate. A predicate is a decision problem (on natural numbers), maps one decision problem to another.
2
Q
If U reduces to V, what is the relationship between U and V’s decidability?
A
f reduces U to V (decision problems), hence if we can decide V we can also decide U.
3
Q
How to reduce HALT to ALL and hence prove ALL is undecidable
A
4
Q
When applying a reduction (from halt), if it is not straight forward what should you do?
A
Modify the program to ignore the input and use the Halt input instead
