Buenas noches Ignacio.
En el reciproco del ejercicio 7 parte a), se pide probar que existe una MT M que cumpla ESTRICTAMENTE la definicion 7.7 del libro para la clase ZPP:
1) M tiene un tiempo esperado de ejecucion polinomial
2) Si M para, tiene error 0, es decir que M(x) = L(x)
En el ejercicio 8, en la version 2016 del libro figura como teorema 7.19. De cualquier forma es el teorema que tiene como titulo " ÜPATH pertenece a RL" , y debe estar muy cerca de ahí en la nueva edicion.
Saludos.
En el reciproco del ejercicio 7 parte a), se pide probar que existe una MT M que cumpla ESTRICTAMENTE la definicion 7.7 del libro para la clase ZPP:
1) M tiene un tiempo esperado de ejecucion polinomial
2) Si M para, tiene error 0, es decir que M(x) = L(x)
En el ejercicio 8, en la version 2016 del libro figura como teorema 7.19. De cualquier forma es el teorema que tiene como titulo " ÜPATH pertenece a RL" , y debe estar muy cerca de ahí en la nueva edicion.
Saludos.