Ejercicio 7)a) y Ejercicio 8)

Ejercicio 7)a) y Ejercicio 8)

de Orlando Ignacio Olivan Silva -
Número de respuestas: 1

Buenas, tenia una consulta del Ejercicio 7) parte a). En el reciproco de la demostracion, si demuestro que una probabilidad tiende a 1, puede considerarse que esta definicion es equivalente a la definicion 7.7 del libro, en el cual la probabilidad es 1?


En cuanto al Ejercicio 8), en la letra hace referencia a un Teorema 7.19, sin embargo, cuando fui al libro, no encontre este Teorema. El libro tenia hasta el Teorema 7.18. No se si esto sera porque tengo una version distinta del libro a la de los docentes. Podrian subir la version del libro en la que se encuentra este teorema, o subir un screenshot del teorema en cuestion? Gracias

En respuesta a Orlando Ignacio Olivan Silva

Re: Ejercicio 7)a) y Ejercicio 8)

de Julian Viera -
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.