From c9318dc3d71c51b5d0b9213e6c5bb885ece905d3 Mon Sep 17 00:00:00 2001
From: Juan Marin Noguera <juan@mnpi.eu>
Date: Mon, 17 Oct 2022 00:20:44 +0200
Subject: Explicada una demostración incorrecta de MC.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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.
---
 mc/n8.lyx | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

(limited to 'mc/n8.lyx')

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
-- 
cgit v1.2.3