**PEC3: Grafos y Complejidad** Ejercicio 1 =============================================================================== Apartado a ------------------------------------------------------------------------------- Vamos a fijarnos en las valoraciones (filas de la tabla de verdad) que hacen falsa a $F$, y a partir de ellas podemos ver que: $$\neg F = (x \wedge \neg y \wedge z) \vee (x \wedge \neg y \wedge \neg z) \vee (\neg x \wedge \neg y \wedge z)$$ Por tanto, negando lo anterior (y aplicando las leyes de De Morgan dos veces): $$F = (\neg x \vee y \vee \neg z) \wedge (\neg x \vee y \vee z) \wedge (x \vee y \vee \neg z)$$ que ya está en Forma Normal Conjuntiva. Apartado b ------------------------------------------------------------------------------- Aplicando la propiedad distributiva entre conjunción y disyunción al primer paréntesis, y teniendo en cuenta que podemos quitar los últimos paréntesis por la propiedad asociativa: $$G= ((x \wedge y) \vee z) \wedge (x \wedge \neg z) = (x\vee z) \wedge (y\vee z) \wedge x \wedge \neg z$$ que ya está en Forma Normal Conjuntiva. Apartado c ------------------------------------------------------------------------------- Si nos fijamos en $G$, es necesario que se verifique $x=1$ y $z=0$ (porque debe verificarse $x \wedge \neg z$). Pero si $z=0$, como también debe verificarse $(x \wedge y) \vee z$, se deduce que debe verificarse $x=1$ (que ya sabíamos) e $y=1$. Por lo tanto, $G$ solo tiene una solución, y es $x=1,\ y=1,\ z= 0$, que vemos que también es solución de $F$ (en su tabla de verdad). En consecuencia, sí hay un conjunto de valores que hacen ciertas a $F$ y $G$ simultáneamente. Ejercicio 2 =============================================================================== Sean $A$, $B$ y $C$ tres problemas que satisfacen $A \leq_p B$ y $B \leq_p C$. Justifica si las siguientes afirmaciones son ciertas o falsas: a) $A \leq_p C$. Cierto. Es la propiedad transitiva de la reducción. b) Si $B \leq_p A$ entonces $A$ es polinómicamente equivalente a $B$. Cierto. Es la definición de polónicamente equivalente. c) Si $C \leq_p B$ entonces $A$ y $C$ son polinómicamente equivalentes. Falso. $B$ y $C$ serían polinómicamente equivalentes, pero $A$ no tiene porqué serlo. Por ejemplo: $A\in P$, $B,\ C\notin P$, con $C=B$ (más concreto: $A=PAR$, $B=C=AJEDREZ$). d) Si $A$ es NP-completo entonces $C$ es NP-completo. Falso. $C$ no tiene porqué estar en $NP$, aunque es cierto que $C$ sería NP-difícil, no tenemos la seguridad de que $C\in NP$. e) Si $B \in P$ entonces $A \in P$. Cierto. Es el apartado 1 de la Propiedad 22. f) Si $B$ es NP entonces $A$ puede resolverse en tiempo polinómico. Sabemos que en este caso $A$ es NP (por el apartado 2 de la Propiedad 22), pero solo puede asegurarse en general que $A$ se puede resolver en tiempo polinómico si P=NP. g) Si $B$ es NP entonces $C$ puede resolverse en espacio polinómico. Falso. Basta tomar $B$ en P (entonces sería NP también) y $C$ en EXPSPACE pero no en PSPACE (sabemos que $C$ existe por la propiedad 20). h) Si $A$ es verificable en tiempo polinómico entonces $B$ y $C$ tienen que ser NP-Completos. Falso. No se imponen más condiciones en $A$, así que podría ocurrir que $A=B=C$ y triviales (por ejemplo, el problema que siempre responde SÍ). Entonces, se tiene que $A$ es verificable en tiempo polinómico, se cumple la cadena de reducciones, pero ninguno es NP-completo. Ejercicio 3 =============================================================================== Dada una expresión booleana $E$ con $n$ variables $x_1$, $x_2$, ..., $x_n$, el problema TRUE-SAT consiste en preguntarnos si $E$ es verdadera cuando todas las variables son verdaderas o bien existe alguna otra asignación de verdad que hace que $E$ sea verdadera. Se pide: Apartado a ------------------------------------------------------------------------------- Probar que el problema TRUE-SAT es NP. Basta probar que TRUE-SAT es verificable en tiempo polinómico. POR HACER. Apartado b ------------------------------------------------------------------------------- Probar que el problema TRUE-SAT es NP-completo. Indicación: Basta con reducir SAT a TRUE-SAT. Para ello se puede construir la función de reducción f definiéndola en primer lugar sobre las expresiones que cumplen la condición de ser verdadera cuando lo son todas sus variables, y en segundo lugar sobre las que no lo cumplen. POR HACER. Ejercicio 4 =============================================================================== Problema 1 ------------------------------------------------------------------------------- Es equivalente al problema TSP del Viajante de comercio, donde los nodos del grafo (ciudades) serían los diferentes sistemas del procesador junto con un nodo adicional que representa a la fuente de alimentación. Las aristas que se consideran serían aqeullas que conectan nodos que tienen un cable de datos entre ellos, ya que se explicita que solo en ese caso es posible pasar un cable de alimentación. Los pasos a seguir serían: 1. **Entrada Problema 1**: mapa del procesador, donde vienen representados en 2D los sistemas, la fuente de alimentación, y las conexiones con cables de datos. 2. **Entrada TSP**: Grafo equivalente en el que los nodos ocupan las posiciones de los sistemas y la fuente de alimentación, y las aristas son las conexiones posibles. 3. **Formato de salida**: sucesión de nodos que forman el ciclo hamiltoniano óptimo (de recorrido mínimo). 4. **Interpretación de la salida**: por cada par de nodos conectados, se añade una conexión con hilo de plata que conecta los sistemas (o fuente de alimentación) correspondientes. Problema 2 ------------------------------------------------------------------------------- Teniendo en cuenta una representación de grafo similar a la que se ha comentado en el problema anterior (pero esta vez no se considera la fuente de alimentación como nodo, sino únicamente los sistemas del procesador), el problema que ahora nos plantean sería equivalente a encontrar un conjuno dominante del grafo formado por los procesadores (nodos) y las conexiones (aristas) entre ellos. *Un conjunto dominante de un grafo $G = (V,A)$ es un sub-conjunto $S\subseteq V$ tal que cada vértice de $G$ se encuentra en $S$ o es adyacente al menos a un vértice de $S$.* De esta forma, si $S$ representa los sistemas con refrigerador, cada sistema o bien tendría un refrigerador, o sería adyacente por una conexión de la circuitería a un sistema con refrigerador, como pide el problema. Los pasos a seguir serían: 1. **Entrada Problema 2**: mapa del procesador, donde vienen representados en 2D los sistemas del procesador y las conexiones con cables de datos. 2. **Entrada Conjunto Dominante**: Grafo equivalente en el que los nodos ocupan las posiciones de los sistemas y las aristas son las conexiones posibles. 3. **Formato de salida**: conjunto de nodos que forman el conjunto dominante, $S$. 4. **Interpretación de la salida**: por cada nodos de $S$, se añade un refrigerador en el sistema correspondiente. Aunque no lo piden, se puede tratar con el problema de optimización asociado y considerar el cálculo de un conjunto dominante minimal (en número de nodos), lo que se traduciría en el gasto minimal de componentes de oro.