- El Pensadero de Canek - https://aztlan.fciencias.unam.mx/pensadero -

Griego

Posted By Canek On abril 10, 2006 @ 8:28 PM In Academia | 4 Comments

Unicode es la neta. Lástima que no se vea tan bonito como $\LaTeX$ ; si no, lo usaría para este tipo de cosas:

CLIQUE es NP-completo

Primero, CLIQUE ∈ NP. Sencillamente verificamos que la adivinanza que nos de el oráculo sean k nodos, y además comprobar que cada nodo esté conectado a todos los demás. Verificarlo nos toma O(n²).

Segundo, vemos que SAT α CLIQUE. Dada una instancia de SAT (una fórmula lógica φ), la queremos reducir polinomialmente a una instancia de CLIQUE (una gráfica G y un entero k), de tal forma que φ sea satisfacible si y sólo si G tiene una subgráfica completa de k vértices.

Si φ tiene k cláusulas, por cada cláusula c_i de m literales, añadimos m vértices a G, y los nombramos v_i,1,…,v_i,m. Y añadimos aristas para cada par de vértices v_i,l, v_j,m excepto cuando i=j, y cuando v_i,l=¬v_j,m.

Ejemplo: dada la fórmula

φ=(v₁∨v₂∨v₃)∧(v₂∨¬v₁)∧(v₁∨¬v₃),

obtenemos la gráfica G

^[1]

Ejemplo CLIQUE

Donde

v_1,1 en G es v₁ en φ, v_2,1 es v₂, v_3,1 es v₁, etc.

Entonces sólo falta demostrar que φ (donde φ tiene k cláusulas) es satisfacible si y sólo si G tiene una subgráfica completa de k vértices.

⇒ φ (con k cláusulas) es satisfacible. Entonces para toda cláusula c_i al menos una de sus literales es verdadera. Sea V’ el conjunto de vértices correspondientes a esas literales (aunque es posible que haya más de una literal verdadera por cláusula, tomamos sólo una). Sean v_i y v_j cualesquiera dos vértices distintos en V’: v_i y v_j están en cláusulas distintas, porque tomamos sólo una literal por cláusula, y como todas las literales de V’ son verdaderas, no es posible que v_i=¬v_j. Por lo tanto, por construcción, v_i está conectado a v_j. Como esto ocurre para cualquier par de vértices en V’, entonces todos los vértices de V’ están conectados entre sí.
Por lo tanto, G tiene una subgráfica completa con k vértices.
⇐ G tiene una subgráfica completa de k vértices. Para cada uno de los vértices, le asignamos un valor de verdad a la literal correspondiente en φ. Como los vértices están conectados, por construcción están en cláusulas distintas de φ (y no hay v_i=¬v_j); entonces cada una de esas cláusulas se evalúa a verdadero. Pero como eran k vértices, esto ocurre con k cláusulas: o sea con todas las cláusulas de φ, y por lo tanto encontramos una asignación de variables tal que φ se evalúa a verdadero.
Por lo tanto, φ es satisfacible.

Pero es que es mucho más bonito con $\LaTeX$ (por no mencionar lo rápido):

CLIQUE es NP-completo

Primero, CLIQUE $\in$ NP. Sencillamente verificamos que la adivinanza que nos de el oráculo sean nodos, y además comprobar que cada nodo esté conectado a todos los demás. Verificarlo nos toma $O(n^{2})$ .

Segundo, vemos que SAT $\alpha$ CLIQUE. Dada una instancia de SAT (una fórmula lógica $\varphi$ ), la queremos reducir polinomialmente a una instancia de CLIQUE (una gráfica y un entero ), de tal forma que $\varphi$ sea satisfacible si y sólo si tiene una subgráfica completa de vértices.

Si $\varphi$ tiene cláusulas, por cada cláusula $c_{i}$ de literales, añadimos vértices a , y los nombramos $v_{i,1},\ldots,v_{i,m}$ . Y añadimos aristas para cada par de vértices $v_{i,l}$ , $v_{j,m}$ excepto cuando i=j , y cuando $v_{i,l}=\lnot{}v_{j,m}$ .

Ejemplo: dada la fórmula

$\varphi=(v_{1}\lor{}v_{2}\lor{}v_{3})\land(v_{2}\lor\lnot{}v_{1})\land(v_{1}\lor\lnot{}v_{3}),$

obtenemos la gráfica

^[1]

Ejemplo CLIQUE

Donde $v_{1,1}$ en es $v_{1}$ en $\varphi$ , $v_{2,1}$ es $v_{2}$ , $v_{3,1}$ es $v_{1}$ , etc.

Entonces sólo falta demostrar que $\varphi$ (donde $\varphi$ tiene cláusulas) es satisfacible si y sólo si tiene una subgráfica completa de vértices.

$\Rightarrow$ $\varphi$ (con cláusulas) es satisfacible. Entonces para toda cláusula $c_{i}$ al menos una de sus literales es verdadera. Sea el conjunto de vértices correspondientes a esas literales (aunque es posible que haya más de una literal verdadera por cláusula, tomamos sólo una). Sean $v_{i}$ y $v_{j}$ cualesquiera dos vértices distintos en : $v_{i}$ y $v_{j}$ están en cláusulas distintas, porque tomamos sólo una literal por cláusula, y como todas las literales de son verdaderas, no es posible que $v_{i}=\lnot{}v_{j}$ . Por lo tanto, por construcción, $v_{i}$ está conectado a $v_{j}$ . Como esto ocurre para cualquier par de vértices en , entonces todos los vértices de están conectados entre sí.
Por lo tanto, tiene una subgráfica completa con vértices.
$\Leftarrow$ tiene una subgráfica completa de vértices. Para cada uno de los vértices, le asignamos un valor de verdad a la literal correspondiente en $\varphi$ . Como los vértices están conectados, por construcción están en cláusulas distintas de $\varphi$ (y no hay $v_{i}=\lnot{}v_{j}$ ); entonces cada una de esas cláusulas se evalúa a verdadero. Pero como eran vértices, esto ocurre con cláusulas: o sea con todas las cláusulas de $\varphi$ , y por lo tanto encontramos una asignación de variables tal que $\varphi$ se evalúa a verdadero.
Por lo tanto, $\varphi$ es satisfacible.

^[2] Imprimir entrada ^[2]

4 Comments (Open | Close)

4 Comments To "Griego"

#1 Comment By diego On abril 11, 2006 @ 12:07 AM

¡EHHHHH! :o

#2 Comment By Andrés Romero Mier y Terán On abril 11, 2006 @ 10:45 PM

El dia de ayer gracias a una liga que encontre a tu sitio en el de Chimal, pude leer el artículo que hiciste en respuesta al señor de apellido Sánchez sobre los peligros apocalípticos que traería López (para ser congruente) de llegar a la presidencia. La verdad me gustó mucho como escribes pienso muy parecido a ti y te envidio por la capacidad que tienes de poder plantear tus ideas en una forma tan amena y sin caer el provocativos violentos, eso es algo que yo desearía en muchos casos poder hacer al toparme con tanta gente de un partido que detesto, no diré el nombre, pero sólo mencionaré que es el que supuestamente ésta en el poder y que utiliza una combinación de colores que particularmente se ve horrible en las obras públicas (la mayoría no hechas por ellos).

Bueno eso fue algo que no tiene nada que ver con lo que te escribo, el punto es que yo soy muy adepto al uso de LaTex y quería preguntarte como fue que hiciste el texto en html con fórmulas de LaTex. Yo uso para esto un programa que se llama LyX que en su versión más nueva lo permite pero quisiera saber si existe alguna forma mas sencilla.

También te quiero preguntar si la gráfica que obtuviste de los nodos la hiciste con algún software en especial, porque la verdad no entendí lo que hablaba tu “post”. Para hacer ese tipo de diagramas yo he visto una cosa que se llama graphviz, quizás lo has usado.

Lo que te pregunto me imorta mucho porque estoy dando clases en la facultad de ingeniería y quiero poner una página con fórmulas sobre la materia que sea muy agradable para los alumnos.

Bueno, reitero mis felicitaciones por tu sitio, suerte.

#3 Comment By Canek On abril 11, 2006 @ 11:42 PM

La verdad utilicé todos los trucos que me sé para hacer esta entrada; realmente no fue sencillo.

Para la versión HTML sencillamente utilicé Unicode: cada carácter es un símbolo; en Unicode están definidos las implicaciones, los conectivos lógicos y todo el alfabeto griego, entre muchas otras cosas.

Pero para hacer cosas como x² sí fue un desmadre; en código es <em>x</em><sup>2</sup>… y es una hueva hacerlo para cada una de las fórmulas. Y los símbolos Unicode tampoco fueron sencillos; tuve que utilizar un applet de GNOME para insertarlos.

La versión donde las fórmulas salen como imágenes la hice con ^[3], un programa en PHP que toma la salida de $\LaTeX$ y la convierte en una imagen GIF. Hay un plugin para WordPress, que es el que yo uso, pero si usas PHP en tu sitio puedes utilizar el programa directamente.

Por último, la gráfica es lo más sucio de todo. Sí conozco Graphviz, pero los hombres de verdad utilizamos PStricks… o al menos eso me enseñaron y así hago yo mis gráficas (no me he pasado a ^[4], que es lo nuevo). Con PStricks, la gráfica la hice con el siguiente código (directamente en mi archivo $\LaTeX$ ):

\begin{center}\tiny
  \pspicture(0,0)(4,4)
  \cnode(.5,3.5){8pt}{v1}\rput{0}(.5,3.5){$v_{1,1}$}
  \cnode(2,4){8pt}{v2}\rput{0}(2,4){$v_{1,2}$}
  \cnode(3.5,3.5){8pt}{v3}\rput{0}(3.5,3.5){$v_{2,2}$}
  \cnode(0,2){8pt}{v4}\rput{0}(0,2){$v_{2,1}$}
  \cnode(1,.5){8pt}{v5}\rput{0}(1,.5){$v_{2,2}$}
  \cnode(4,2){8pt}{v6}\rput{0}(4,2){$v_{3,1}$}
  \cnode(3,.5){8pt}{v7}\rput{0}(3,.5){$v_{3,2}$}
  \ncline[arrows=-,linewidth=1pt]{v1}{v4}
  \ncline[arrows=-,linewidth=1pt]{v1}{v6}
  \ncline[arrows=-,linewidth=1pt]{v1}{v7}
  \ncline[arrows=-,linewidth=1pt]{v2}{v4}
  \ncline[arrows=-,linewidth=1pt]{v2}{v5}
  \ncline[arrows=-,linewidth=1pt]{v2}{v6}
  \ncline[arrows=-,linewidth=1pt]{v2}{v7}
  \ncline[arrows=-,linewidth=1pt]{v3}{v4}
  \ncline[arrows=-,linewidth=1pt]{v3}{v5}
  \ncline[arrows=-,linewidth=1pt]{v3}{v6}
  \ncline[arrows=-,linewidth=1pt]{v4}{v6}
  \ncline[arrows=-,linewidth=1pt]{v4}{v7}
  \endpspicture
\end{center}

Eso lo compilé a un PostScript, lo abrí en ^[5] (el visor de documentos de GNOME), le puse el máximo zoom (400%), y le saqué un screenshot. Lo corté con el GIMP, y es lo que aparece en la entrada.

Hay formas mucho más elegantes de hacer todo el relajo; pero yo sólo quería utilizar caracteres griegos en mi blog, y lo más a la mano que tenía era mi tarea de Complejidad. Y la demostración se ve más bonita con el ejemplo, y por eso tomé el screenshot de la gráfica.

Si quieres dejarles fórmulas a tus estudiantes, te recomiendo que les des un PDF para que lo bajen de tu página. Si no, puedes utlizar LatexRender; funciona muy bien. Otra opción que también utiliza $\LaTeX$ es ^[6]; es lo que utilizan en la Wikipedia y que también genera imágenes a partir de $\LaTeX$ , como puedes ver ^[7]. No necesitas ser root para instalar ninguno de esos programas; sólo poder utilizar PHP, y acceso a una base de datos MySQL.

#4 Comment By Canek On abril 13, 2006 @ 11:22 PM

Omar me hizo notar que por omisión MediaWiki no usa $\LaTeX$ sino unicode. Cuando uno tiene cuenta en MediaWiki, puede definir qué método quiere para hacer las fórmulas, sólo usar $\LaTeX$ , nunca usarlo, o mixto. Yo lo tengo que siempre.

Como sea, MediaWiki puede también hacer fórmulas.