We adopt consequence systems as a highly suitable framework for introducing logical (decision) problems such as the Consequence Problem, the Theoremhood Problem and the Consistency Problem. Reductions play a key role in the reflection and preservation of decidability and non decidability, respectively. We consider two levels of reduction: reduction between decision problems and between consequence systems. Then, we establish sufficient conditions for the existence of reductions between problems over the same consequence system as well as across different consequence systems. We also analyze the relationship between the two levels of reductions. Several examples are presented covering paraconsistent, intuitionistic, and modal logics.