Continuando…

Sí Miguel Angel sigo con mi blog pa lante aunque no pueda prestarle toda la atención que deba. Y es que mi compañero de trabajo en Gonzalez Byass me preguntaba hoy o ayer (ya no recuerdo, me toi haciendo mayor) si seguía con mi blog y mi respuesta es afirmativa. En realidad ahora mismo pienso que qué hago aquí escribiendo cuando una persona normal estaria apurando cada resquicio del papel ya que hoy es mi día previo al exámen de ADAI. Si señores/-as mañana es el día y lo llevo otra vez cogio con pinzas como en Diciembre. Miro los apuntes y todo me suena pero no me siento con los conocimientos suficientes para aprobar, hay problemas de esos teóricos a los que no seria capaz de enfrentarme, lo confieso, pero tambien puedo decir que lo que miro en los apuntes lo sé hacer. Total mañana veremos como sale la cosa, que sea lo que dios quiera (es una forma de hablar, no creo que dios pueda hacer el examen por mí 😛 ). Y es que me toi rayando mucho, le doy vueltas a muchas cosas en mi cabeza. Ella me llamó hoy, quería quedar conmigo mañana. Ha venido de Sevilla un par de días y quiere quedar conmigo, esto me pone muy contento y hace que resurjan mis sentimientos pero yo trato de ahogarlos, esconderlos dentro de mí. Y para colmo… para colmo esta pregunta de ADA I me raya más:

Conteste razonadamente a las siguientes cuestiones.
a) ¿Qué característica fundamental posee la clase de problemas NP?
La característica fundamental de la clase NP es que está formada por aquellos problemas de decisión que poseen algoritmos de vericación polinómicos. Esto signica que el problema de decisión acepta un ejemplar x si, y sólo si, existe un testigo y que ocupa un espacio polinómico en el tamaño de x tal que el algoritmo de vericación acepta el par formado por x e y en tiempo polinómico.
b) ¿Qué se deduce, en términos de dicultad relativa, del hecho de que un problema de decisión sea reducible polinómicamente a otro?
Si un problema de decisión se reduce polinómicamente a otro, entonces es igual o más fácil que él, ya que si supiéramos resolver el segundo sabríamos resolver el primero. Podría obtenerse un algoritmo para el primer problema transformando cada ejemplar del primer problema en otro del segundo y resolviendo este último con un algoritmo para el segundo problema.
Que la transformación pueda realizarse en tiempo polinómico es importante: si el segundo problema es tratable también lo será el primero. Visto de otro modo, el segundo problema es al menos tan difícil como el primero: si el primer problema es intratable, también lo será el segundo.
c) ¿Qué ocurriría si el problema del árbol de Steiner pudiera reducirse polinómicamente a un problema NP dado?
El problema del árbol de Steiner es un problema NPC. Esto quiere decir que es un problema NP y que todos los problemas NP se reducen polinómicamente a él. Si un problema NPC se puede reducir polinómicamente a un problema NP, automáticamente todos los demás problemas NP se podrán reducir polinómicamente a él. En consecuencia, dicho problema no sólo sería NP, sino NPC.

Bueno pues en la próxima ya os contaré que tal fue todo 😉