O Um Programador está certo na resposta dele.
Eu fiquei curioso e fui atrás de mais material. Encontrei isso na Wikipedia:
Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não. Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão. (...)
Então, para todos os fins práticos, a gente pode interpretar isso como "qualquer coisa que você possa representar com uma função/método que considere uma condição e retorna booleano".
Na verdade existem muitas implicações sobre isso para quem estuda matemática cientificamente, ou para quem faz pesquisa sobre a história da computação. Mas para a maioria de nós acaba por ser apenas uma curiosidade.
P.s.: isso não quer dizer que isso não seja de grande importância. Alan Turing desenvolveu todo seu trabalho sobre máquinas de computar para resolver problemas como o problema de decisão. Se esses problemas não tivessem sido propostos, nós não teríamos toda a tecnologia que temos hoje.