AUTOMATAS

En el campo de la complejidad algorítmica (problemas de algoritmos y de lógica) se presenta la “Decibilidad de teorías lógicas”. Una técnica para resolver problemas de este tipo es reducir un problema a otro para comprobar si tiene o no solución efectiva. Al hacer uso de esta estrategia en el caso que la respuesta sea negativa, se da:

Seleccione una:

a. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, se determina la clase de complejidad siendo esta la solución

b. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces es probable que solo se solucione usando una Máquina de Turing (MT).

c. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces este nuevo problema tampoco tendrá solución efectiva.

d. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, se convierte en un problema parcialmente soluble (existe una Máquina de Turing que resuelve el problema, pero puede no parar)

Retroalimentación

La respuesta correcta es: Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces este nuevo problema tampoco tendrá solución efectiva.