Siguiente: Formas proposicionales y el Un nivel arriba: Completitud-NP Anterior: Reducibilidades

Problemas difíciles y completos en clases polinomiales

La clase de problemas resolubles en tiempo polinomial es ${\displaystyle \mbox{\rm P} = \bigcup_{i\geq 0}\mbox{\rm DTIME}(n^i)}$ y la clase de problemas comprobables en tiempo polinomial es ${\displaystyle \mbox{\rm NP} = \bigcup_{i\geq 0}\mbox{\rm NTIME}(n^i)}$. Similarmente, las clases de problemas resolubles en espacio polinomial es ${\displaystyle \mbox{\rm PSPACE} = \bigcup_{i\geq 0}\mbox{\rm DSPACE}(n^i)}$, en tanto que la de comprobables en espacio polinomial es ${\displaystyle \mbox{\rm NSPACE} = \bigcup_{i\geq 0}\mbox{\rm NSPACE}(n^i)}$. De acuerdo con el lema de Savitch (prop. 6.6.4) se tiene dos jerarquías en $\mbox{\rm PSPACE}$:

$$\bigcup_{i\geq 1}\mbox{\rm DSPACE}(\log^i n)=\mbox{\rm PSPACE}=\bigcup_{i\geq 1}\mbox{\rm NSPACE}(\log^i n).$$

Puede verse además que se tiene las contenciones siguientes

$$\mbox{\rm DSPACE}(\log n)\subset \mbox{\rm P} \subset \mbox{\rm NP} \subset \mbox{\rm PSPACE}$$

y aunque alguna de ellas es propia no se sabe cuál lo es. En lo sucesivo, consideraremos máquinas de Turing que calculan funciones $I\!\!N\rightarrow I\!\!N$. Cada una de tales máquinas actúa a partir de descripciones instantáneas iniciales de la forma $q_0\mbox{\bf x}$ donde $\mbox{\bf x}$ es la representación en base 2 de un número $x\in I\!\!N$ y, en el caso de converger, finaliza con una descripción final de la forma $\mbox{\bf y}q_h$ donde $\mbox{\bf y}$ es la representación en base 2 de la imagen de x bajo la función calculada por M. Sean pues A y B dos conjuntos en $I\!\!N$. Diremos que

• B se reduce en tiempo polinomial a A, $B\preceq_{\mbox{\scriptsize\it tp}} A$, si existe una máquina de Turing M de tiempo polinomial tal que $\forall x\in I\!\!N:\ x\in B\ \Leftrightarrow\ M(x)\in A.$
• B se reduce en espacio-logarítmico a A, $B\preceq_{\mbox{\scriptsize\it el}} A$, si existe un traductor logarítmico, es decir una máquina de Turing M tal que M converge en todas sus entradas, tiene una cinta de entrada, otra de salida y otras de trabajo, en la de entrada sólo se mueve en una dirección y ocupa un espacio logarítmico en las cintas que no son de entrada ni de salida, tal que $\forall x\in I\!\!N:\ x\in B\ \Leftrightarrow\ M(x)\in A.$

Naturalmente, se tiene que $\preceq_{\mbox{\scriptsize\it tp}}$ y $\preceq_{\mbox{\scriptsize\it el}}$ son reducibilidades, en el sentido definido en la sección 7.1.1. Se tiene las proposiciones siguientes:

Proposición 2.1   Si B se reduce a A en espacio-logarítmico entonces también B se reduce a A en tiempo polinomial. Es decir,

$$B\preceq_{\mbox{\scriptsize\it el}} A\ \Rightarrow\ B\preceq_{\mbox{\scriptsize\it tp}} A$$

En efecto, por un lado, todo traductor logarítmico ha de converger en todas sus entradas, y por otro lado, la única manera de evitar que ``se ciclen'' las descripciones instantáneas de cualquier máquina de Turing con espacio-logarítmico es teniendo un número polinomial de ellas en cada computación.

Proposición 2.2   Si B se reduce a A en tiempo polinomial entonces

• $A\in \mbox{\rm NP}\;\Rightarrow\;B\in \mbox{\rm NP}.$
• $A\in \mbox{\rm P}\;\Rightarrow\;B\in \mbox{\rm P}.$

Esto se debe solamente a que la composición de dos polinomios sigue siendo un polinomio.

Proposición 2.3   Si B se reduce a A en espacio-logarítmico entonces

• $A\in \mbox{\rm P}\;\Rightarrow\;B\in \mbox{\rm P}.$
• $A\in \mbox{\rm DSPACE}(\log^i n)\;\Rightarrow\;B\in \mbox{\rm DSPACE}(\log^i n).$
• $A\in \mbox{\rm NSPACE}(\log^i n)\;\Rightarrow\;B\in \mbox{\rm NSPACE}(\log^i n).$

Aunque la salida de un traductor logarítmico puede ser de longitud polinomial, si se tiene un tal traductor M₁ y un reconocedor en espacio logarítmico la composición de ellos se realiza en espacio logarítmico haciendo que la salida de M₁ se vaya aplicando símbolo a símbolo a la entrada de M₂.

Proposición 2.4   La composición de reducciones en espacio logarítmico es de espacio logarítmico. Lo mismo vale para reducciones de tiempo polinomial.

Sea ${\cal C}$ una clase de problemas, es decir, una clase de conjuntos en $I\!\!N$, y ``$\preceq$'' una reducibilidad. Sea $A\subset I\!\!N$ un problema.

• A es difícil-${\cal C}$, respecto a la reducibilidad ``$\preceq$'', si $\forall B:\left(B\in {\cal C}\;\Rightarrow\;B\preceq A\right).$
• A es completo-${\cal C}$, respecto a la reducibilidad ``$\preceq$'', si es difícil-${\cal C}$ y además está en la misma clase ${\cal C}$.

Así pues para ver que un problema dado es completo en una clase hay que probar que está en la clase y que todo otro problema en esa clase se reduce a él, respecto a la reducibilidad considerada. Un problema es completo- $\mbox{\rm NP}$ o difícil- $\mbox{\rm NP}$ si es completo o difícil en la clase NP, con respecto a la reducción en espacio logarítmico. Un problema es completo- $\mbox{\rm PSPACE}$ o difícil- $\mbox{\rm PSPACE}$ si es completo o difícil en la clase PSPACE, con respecto a la reducción en tiempo polinomial.

Proposición 2.5   Si un problema completo-NP estuviera también en la clase P entonces necesariamente $\mbox{\rm P}=\mbox{\rm NP}$.

Siguiente: Formas proposicionales y el Un nivel arriba: Completitud-NP Anterior: Reducibilidades