A decision problem is a question in computational theory that requires a simple 'yes' or 'no' answer based on a given input. It explores whether an Algorithm can reliably find this answer for all possible inputs, deeply connecting to concepts of Computability.