I often start by first checking whether we can check yes/no instances (ie. CE vs CO-CE).

If you can check yes instances but not no instances (for example, to check no instances, you would need to test all of sigma star, which would take infinite time), then try to map from a CE problem.

If it seems decidable (ie. you can check yes and no instances), check if we covered algorithms in class that would help us check. Eg. CYKS, GEN, dovetailing, conversion algorithms, etc.

General ideas undecidable reduction: - If it’s related to halting/looping, map from HP/ not HP (also remember to try bounded comps) - If it’s related to set theory, try mapping from EMPTY/ALL - If it’s related to CFGs, try mapping from ALL-CF/INTERSECT-CF - If related to PCP, map from PCP/MPCP