Segundo Parcial 2018, Ejercicio 3

Segundo Parcial 2018, Ejercicio 3

de Ian Ignacy Arazny Casanovas -
Número de respuestas: 6

Hola buenas tardes, adjunto la solución propuesta para este problema y sobre la cual surge mi duda, 


En este tipo de problemas basta con solamente esta demostración sobre el tiempo que insume el algoritmo bajo cierta implementación que proponga? Puesto que, para probar que un problema es NP debe haber un certificado eficiente B que cumpla lo siguiente según el libro: 


Pero en la solución propuesta no se estaría probando únicamente la primer parte de estos dos puntos? 

Saludos, 

Ian.

En respuesta a Ian Ignacy Arazny Casanovas

Re: Segundo Parcial 2018, Ejercicio 3

de Rodrigo Alejandro Aguillon Stoletniy -
Me adhiero a la consulta del compañero
En respuesta a Rodrigo Alejandro Aguillon Stoletniy

Re: Segundo Parcial 2018, Ejercicio 3

de Javier Baliosian -
hola
la respuesta incluye la segunda parte también, aunque de forma un poco diluída en el texto, cuando dice "Es claro que dicho certificado ..."
en una respuesta reciente a una consulta de un compañero pusimos lo que esperamos que contesten en este tipo de ejercicios: https://eva.fing.edu.uy/mod/forum/discuss.php?d=256283#p567810

saludos
J

En respuesta a Javier Baliosian

Re: Segundo Parcial 2018, Ejercicio 3

de Rodrigo Alejandro Aguillon Stoletniy -
Buenas, con respecto a la respuesta que vi en el foro se aclara que no es importante aclarar que B sea de tiempo polinomico, pero, no se si me estoy confundiendo, en muchas soluciones de parciales, lo que se hace para probar que un algoritmo es NP, lo que se hace es brindar el algoritmo certificador, y luego probar que si s pertenece al conjunto de soluciones SI de X si y solo si existe una cadena t tal que B(s,t)=SI. Por lo que entendi en el mensaje del foro, no es tan relevante como brindar el algoritmo certificador de hecho, y probar que satisface determinado orden, explicando un poco "en el aire" por que es correcto, que vendria a ser la cadena de si y solo si.
En respuesta a Rodrigo Alejandro Aguillon Stoletniy

Re: Segundo Parcial 2018, Ejercicio 3

de Javier Baliosian -

hola Rodrigo 

si te referís a este mensaje 

https://eva.fing.edu.uy/mod/forum/discuss.php?d=256283#p567985

leelo con atención por favor. 

Lo que dice es que debes aclarar que B es de tiempo polinómico. lo que no es necesario es que lo demuestres formalmente. 

saludos,

J