Siguiente: Algunos otros problemas Un nivel arriba: Problemas en teoría de Anterior: Enteros algebraicos

Solubilidad de DSP

Consideremos la versión de DSP consistente en decidir a validez de la fórmula

$$\exists \mbox{\bf x}\in N^n:\;\bigwedge_{i=1}^m [f_i(\mbox{\bf x})\vert g_i(\mbox{\bf x})]$$

donde para cada $i\leq m$ $f_i(\mbox{\bf X}),g_i(\mbox{\bf X})$ son polinomios lineales con coeficientes enteros (racionales).

1. En esta sección $\phi$ siempre denotará una fórmula de la forma

$$\phi(\mbox{\bf x})\equiv\bigwedge_{i=1}^m [f_i(\mbox{\bf x})\vert g_i(\mbox{\bf x})].$$

$\phi(\mbox{\bf x})$ se dice ser positiva si puede expresarse de manera que todos los coeficientes que aparezcan en los polinomios son números naturales.

2. En lo sucesivo

$$\begin{array}{lcl} \mbox{\bf A}\in Q^{n\times n} &:& \mbox{\... ...etermina una {\em traslaci\'on} }N^n\rightarrow N^n \end{array}$$

$\mbox{\bf u}\mapsto \mbox{\bf x}=\mbox{\bf A u}+\mbox{\bf b}$ es una transformación afín. Para una fórmula $\phi(\mbox{\bf x})$ definimos

$$\psi(\mbox{\bf u})\equiv \phi(\mbox{\bf A u}+\mbox{\bf b})\land h(\mbox{\bf u})$$

donde $h(\mbox{\bf u})$ es una fórmula tal que se tenga

$$\psi(\mbox{\bf u})\;\Leftrightarrow\;\phi(\mbox{\bf A u}+\mbo... ...\mbox{\bf A u}+\mbox{\bf b}\mbox{\rm es un entero algebraico].}$$

Escribiremos $\psi=S_{\mbox{\bf A,b}}(\phi)$, y diremos que $\psi$ se obtiene de $\phi$ mediante el cambio de variable $\mbox{\bf x}=\mbox{\bf A u}+\mbox{\bf b}$.

3. Un cono en Rⁿ es un conjunto $C\subset R^n$ tal que

• Contiene al cero: $\mbox{\bf0}\in C$.
• Es cerrado bajo la suma:
  
  $$\mbox{\bf x},\mbox{\bf y}\in C\;\Rightarrow\;\mbox{\bf x}+\mbox{\bf y}\in C.$$
  
  

• Contiene al semisegmento positivo de cada uno de sus elementos:
  
  $$\mbox{\bf x}\in C, t>0\;\Rightarrow\;t\mbox{\bf x}\in C.$$
  
  

• No contiene parejas simétricas:
  
  $$\forall \mbox{\bf x}:\;-\mbox{\bf x},\mbox{\bf x}\in C\;\Rightarrow\;\mbox{\bf x}=\mbox{\bf0}.$$
  
  

Por ejemplo, el primer ``2<sup>n</sup>-ante'' es un cono. Si C es un cono la relación ``$\leq_{C}$'' definida como

$$\mbox{\bf x}\leq_{C}\mbox{\bf y}\;\Leftrightarrow\;\mbox{\bf y}-\mbox{\bf x}\in C,$$

es una relación de orden. Si C está definido por un predicado

$$C=\{\mbox{\bf x}\vert\chi(\mbox{\bf x})\},$$

diremos que $\chi(\mbox{\bf x})$ define un orden.

4. Lema: Sea

$$\omega(\mbox{\bf x})\equiv \chi(\mbox{\bf x})\land (\mbox{\bf Bx}\leq \mbox{\bf c}),$$

donde $\chi(\mbox{\bf x})$ define un orden, $\mbox{\bf B} \in Q^{m\times n}$ y $\mbox{\bf c} \in Q^{m}$. Entonces existe un conjunto de transformaciones afines

$$\left\{\mbox{\bf u}\mapsto \mbox{\bf x}=\mbox{\bf A}_i\mbox{\bf u}+\mbox{\bf b}_i\right\}_{1\leq i \leq I}$$

tal que

$$\exists \mbox{\bf x}\in N^n(\phi(\mbox{\bf x})\land\omega(\mb... ...}\in N^n(S_{\mbox{\bf A}_i,\mbox{\bf b}_i}(\phi)(\mbox{\bf u}))$$

y

$$\forall i\in[1,I]:\;S_{\mbox{\bf A}_i,\mbox{\bf b}_i}(\phi)(\mbox{\bf u})\mbox{\rm es positivo}.$$

5. Lema: Dada una fórmula $\phi(\mbox{\bf x})$ con coeficientes en Z se puede encontrar algorítmicamente un conjunto $\left\{\chi_i(\mbox{\bf x})\right\}_{1\leq i \leq I}$ de predicados que definen órdenes y un conjunto de transformaciones afines

$$\left\{\mbox{\bf u}\mapsto \mbox{\bf x}=\mbox{\bf A}_i\mbox{\bf u}+\mbox{\bf b}_i\right\}_{1\leq i \leq I}$$

tales que

$$\exists \mbox{\bf x}\in N^n\phi(\mbox{\bf x})\Leftrightarrow ... ...{\bf b}_i}(\phi)(\mbox{\bf u})\land \chi_i(\mbox{\bf x})\right)$$

y

$$\forall i\in[1,I]:\;S_{\mbox{\bf A}_i,\mbox{\bf b}_i}(\phi)(\mbox{\bf u})\mbox{\rm es positivo}.$$

6. Utilizaremos la notación siguiente

$$\begin{eqnarray*}\phi(\mbox{\bf x})&\equiv&\bigwedge_{i=1}^m [f_i(\mbox{\bf x})\... ...d }p^k &\Leftrightarrow&\exists c: ac\equiv b\mbox{\rm mod }p^k \end{eqnarray*}$$

Lema: Si para algún exponente k y algún primo p tenemos que

$$\phi(\mbox{\bf x})\mbox{\rm posee una soluci\'on mod }p^k$$

y

$$\forall i:\; f_i(\mbox{\bf x})\not\equiv0\mbox{\rm mod }p^k$$

entonces

$$\phi(\mbox{\bf x})\mbox{\rm posee una soluci\'on mod }p^{k(\phi,p)}.$$

7. Lema: Una fórmula de la forma

$$\phi(\mbox{\bf u})\land \chi_i(\mbox{\bf x})$$

donde $\phi$ es positiva y $\chi$ define un orden, tiene una solución en N si y sólo si

$$\begin{eqnarray*}\forall p&\in& \mbox{\rm Primos}\cap \{i\vert i\leq \mathop{\rm... ...\mbox{\bf x})\mbox{\rm posee una soluci\'on mod }p^{k(\phi,p)}. \end{eqnarray*}$$

8. Teorema: Existe un algoritmo para decidir la veracidad de una fórmula

$$\exists \mbox{\bf x}\in N^n:\phi(\mbox{\bf x}).$$

9. Corolario: DSP está en la clase NP.

10. Proposición: DSP es completo-NP Veamos que el problema EDC de Ecuación Diofantina Cuadrática se reduce a DSP. Dada una instancia

$$\Phi(a,b,c)\equiv\exists x,y\in Z:a x^2+by-c=0,$$

tenemos las siguientes relaciones

$$\begin{eqnarray*}\Phi(a,b,c) &\Leftrightarrow& \exists x\in Z: b\vert(-a x^2 + c) \\ & \Rightarrow& \exists z\in N: b\vert(-a z + c) \end{eqnarray*}$$

Consideremos entonces la instancia de DSP

$$T(\Phi)\equiv \exists z\in N: b\vert(-a z + c).$$

Si $T(\Phi)$ se resuelve, se prueba cada una de las posibles soluciones z, las cuáles forman un conjunto finito en la región determinada por el Teorema en la observación anterior y se ve si alguna es un cuadrado, en cuyo caso $\Phi$ posee efectivamente una solución.
Siguiente: Algunos otros problemas Un nivel arriba: Problemas en teoría de Anterior: Enteros algebraicos