En
ciencia computacional teórica, un
problema abstracto o
problema computacional es una
relación entre un conjunto de
instancias y un conjunto de
soluciones. Un problema abstracto permite establecer formalmente la relación deseada entre la entrada de un algoritmo y su salida. Una
solución algorítmica a un problema abstracto consiste de un algoritmo que por cada instancia del problema calcula al menos una solución correspondiente –en caso de haberla– o expide un certificado de que no existe solución alguna. Un problema abstracto se convierte en un
problema concreto cuando las instancias y soluciones están codificadas en forma de
lenguajes formales.