Explicada una demostración incorrecta de MC.

La demostración que aparece en los apuntes de que SAT es NP-completo es
incorrecta y añadí las correcciones necesarias, pero los ejercicios
hacen preguntas muy específicas sobre la versión incorrecta y he tenido
que explicarla.

1 files changed, 39 insertions, 0 deletions

diff --git a/mc/n8.lyx b/mc/n8.lyx
index c301fba..41faeec 100644
--- a/mc/n8.lyx
+++ b/mc/n8.lyx
@@ -870,6 +870,45 @@ Si
 \end_inset
 
  se genera en tiempo polinómico.
+ La demostración vista en clase
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+La cual hay que saberse pese a que es incorrecta porque hacen preguntas
+ sobre ella.
+\end_layout
+
+\end_inset
+
+ asume que la cota de tiempo siempre es de la forma 
+\begin_inset Formula $n^{k}-3$
+\end_inset
+
+, pese a que para valores pequeños de 
+\begin_inset Formula $n$
+\end_inset
+
+ esto es imposible; añade una columa llena de 
+\begin_inset Formula $\#$
+\end_inset
+
+ a cada lado del tablón y dos filas al final inútiles para que este tenga
+ tamaño 
+\begin_inset Formula $n^{k}\times n^{k}$
+\end_inset
+
+, añadiendo dos proposiciones atómicas a 
+\begin_inset Formula $\Phi_{\text{start}}$
+\end_inset
+
+ para establecerlas a 
+\begin_inset Formula $\#$
+\end_inset
+
+ y que se propaguen al resto y extendiendo el resto de proposiciones a estas
+ nuevas columnas y filas, y llama proposiciones sólo a las proposiciones
+ atómicas.
 \end_layout
 
 \begin_layout Standard