Siguiente: Máquinas-p Un nivel arriba: Máquinas probabilísticas Anterior: Máquinas probabilísticas

Máquinas del tipo 1

Una máquina de Turing probabilística del tipo 1, (mTp1), es una mTnd M modificada de manera que en su árbol de computaciones:

• cada arista tiene un peso numérico $p\in [0,1]$,
• en cada nodo la suma de los pesos de las aristas que emanan de él es 1,
• el conjunto de nodos terminales es la unión disjunta de nodos de aceptación y de nodos de rechazo,
  
  $$\mbox{\rm Terminales} = \mbox{\rm Aceptantes}\cup\mbox{\rm Rechazantes},$$
  
  
  y
• toda computación es terminal.

Las transiciones en una mTp1 se suponen independientes de sus precedentes, por lo que la probabilidad de una computación es el producto de las probabilidades de las transiciones que la componen. Alternativamente, en una mTp1 podemos considerar a su función de transición como una de la forma

$$\begin{eqnarray*}t:Q\times\Sigma\times [1,n]&\rightarrow& Q\times\Sigma\times \{\mbox{\rm Der,Izq}\} \\ (p,\sigma,r) &\mapsto& (q,\tau,m) \end{eqnarray*}$$

donde $r:Q\times\Sigma\times R\rightarrow [1,n]$ es una variable aleatoria tal que

$$\mbox{\rm Prob}\{r(p,\sigma,x)=i\}=\mbox{\rm Prob}\{\mbox{\rm pasar al estado $i$ al estar en $p$ y leer }\sigma\}.$$

Sea M una mTp1. Para cada cadena de entrada $\mbox{\bf x}$ sea

$$\rho_M(\mbox{\bf x})=\mbox{\rm Prob}\{M \mbox{\rm acepta a }\mbox{\bf x} \}.$$

El lenguaje reconocido por M es L si y sólo si

$$\begin{array}{rrcl} \bullet & \forall \mbox{\bf x}&:& \mbox{... ...n L \;\Rightarrow\; \rho_M(\mbox{\bf x})>\epsilon. \end{array}$$

Escribiremos L=L(M). Se tiene evidentemente que

• toda máquina de Turing determinística es una mTp1, en la que en todo instante sólo una transición asume una probabilidad 1, y
• toda mTp1 es una máquina de Turing no-determinística, de hecho las nociones de reconocimiento coinciden, sólo que en una mTp1 se sabe que una cadena reconocida posee al menos $100\cdot \epsilon\%$ computaciones aceptantes.

Consideraremos únicamente mTp1's tales que sus árboles de computación poseen alturas polinomiales en la longitud de sus entradas. Hacemos

$$R=\{L\vert\exists M\in \mbox{\rm mTp1}:L=L(M)\}.$$

Entonces

$$P\subset R \subset \mbox{\it NP}.$$

Siguiente: Máquinas-p Un nivel arriba: Máquinas probabilísticas Anterior: Máquinas probabilísticas