Siguiente: Problemas difíciles y completos Un nivel arriba: Clases de problemas Anterior: Clases de problemas

  
Reducibilidades

Recordemos algunas de las nociones introducidas en la sección 5.5.2. Ahí convinimos en que para dos conjuntos de números naturales, A,B no vacíos, $A\preceq_r B$ denota que $\chi_A\in\mbox{\it Rec}(\chi_B)$, $A\preceq_{m} B$ denota que existe una función computable f tal que A=f^-1(B) y, finalmente, $A\preceq_{m} B$ denota que existe una función computable e inyectiva f tal que A=f^-1(B). Las relaciones ``$\preceq_r$'', ``$\preceq_{m}$'' y ``$\preceq_{1}$'' son reducibilidades, es decir, son reflexivas y transitivas, y cada una es un refinamiento de la anterior. De manera más general, si ${\cal F}$ es una familia de funciones, escribiremos $A\preceq_{\cal F} B$ para denotar que existe una función $f\in{\cal F}$ tal que A=f<sup>-1</sup>(B). Obviamente, `` $\preceq_{\cal F}$'' es reducibilidad si, por ejemplo, la familia ${\cal F}$ contiene a la identidad y es cerrada bajo composición. Si ``$\preceq$'' es una reducibilidad, ésta induce a la relación ``$\equiv$'' definida como sigue:

$$A\equiv B \ \Leftrightarrow \ (A\preceq B)\&(B\preceq A).$$

Proposición 1.1   ``$\equiv$'' es una relación de equivalencia.

Sea ${\cal C}$ una clase de conjuntos y ``$\preceq$'' una reducibilidad.

Proposición 1.2   Sea A un conjunto completo en la clase ${\cal C}$ y sea $B\in{\cal C}$ tal que $A\preceq B$. Entonces B es completo en la clase ${\cal C}$.

Definamos $\mbox{\rm co-${\cal C}$ }=\{A\subset N\vert(N-A)\in {\cal C}\}.$ De manera inmediata, se tiene las siguientes proposiciones:

Proposición 1.3   Si $\mbox{\rm co-${\cal C}$ }$ fuera cerrado y hubiera un conjunto A completo para ${\cal C}$ que estuviera también en $\mbox{\rm co-${\cal C}$ }$ entonces se ha de tener ${\cal C}=\mbox{\rm co-${\cal C}$ }.$

En efecto, bajo las hipótesis hechas se prueba fácilmente que ${\cal C}\subset\mbox{\rm co-${\cal C}$ }$. De manera completamente simétrica se prueba la inclusión opuesta.

Proposición 1.4   Si $A\preceq_{m} B$ entonces $(N-A)\preceq_m (N-B)$. También: Si $A\preceq_{1} B$ entonces $(N-A)\preceq_1 (N-B)$.

En efecto, si $f:N\rightarrow N$ es tal que A=f^-1(B), evidentemente se tendrá también que (N-A)=f^-1(N-B).

Proposición 1.5   Si ${\cal C}$ fuera cerrada-m o cerrada-1 entonces también lo es $\mbox{\rm co-${\cal C}$ }$.

Esto es una consecuencia de la proposición anterior.

Proposición 1.6   Sea $\left\{f_n\right\}_n$ una enumeración de las funciones recursivas y sea $K=\{n\vert f_n(n)\downarrow\}.$ Entonces, K es completo-1 para la clase de conjuntos recursivamente enumerables.

En efecto, sea A recursivamente enumerable. Hemos de probar que para alguna función recursiva e inyectiva f₀ se tiene A=f₀^-1(K). Como A es recursivamente enumerable existe una función recursiva f_A cuyo dominio es precisamente A. Consideremos la función recursiva,

$$\begin{eqnarray*}g:N^2 &\rightarrow& N \\ (x,y) &\mapsto& g(x,y)=f_A(x) \end{eqnarray*}$$

Por el Teorema de Parametrización, existe una función recursiva f₀ tal que $\forall y: \ g(x,y)=f_{f_0(x)}(y).$ Observemos que las funciones de la forma $f_{f_0(x)},x\in N,$ son todas constantes. Por tanto el predicado $\Phi(x_1,x_2)\equiv \left(f_{f_0(x_1)}=f_{f_0(x_2)}\right)$ es recursivo. Así pues, se puede modificar fácilmente a f₀ de manera que sea inyectiva si acaso no lo fuera ya. Se cumplen además las equivalencias siguientes:

$$\begin{array}{rcrcr} x\in A &\Leftrightarrow& f_A(x)\downarr... ...arrow \\ &\Leftrightarrow& f_0(x)\in K \ \ & & \end{array}$$

Proposición 1.7   Si A es un conjunto completo-m para la clase de conjuntos recursivamente enumerables entonces su complemento A^c no puede ser recursivamente enumerable.

Se tiene que la clase de los conjuntos recursivamente enumerables es cerrada-m. Luego, si A^c fuera recursivamente enumerable entonces el complemento de todo recursivamente enumerable también sería recursivamente enumerable. Evidentemente, esta última propiedad no puede ser cierta.

Proposición 1.8   Dados, $A,B\subset N$ sea $A\oplus B=\{2x\vert x\in A\}\cup \{2x+1\vert x\in B\}.$ Entonces,

1.

$A,B\preceq_{m} A\oplus B$.

2.

$\forall C\subset N:\ A,B\preceq_{m} C\ \Rightarrow \ A\oplus B\preceq_{m} C.$

$A\oplus B$ es el conjunto que contiene la información de ambos A y B y nada más.
Siguiente: Problemas difíciles y completos Un nivel arriba: Clases de problemas Anterior: Clases de problemas