En este mini vídeo vamos a ver un ejemplo de PCP que se llama PCPT, PCP
tonto, en inglés se llama el Chili PCP, veremos por qué se llama así.
Bueno, el PCP tonto o el PCPT está caracterizado, es un PCP donde todas
las fichas de dominó, todas las fichas de dominó que nosotros tengamos,
todos los puzzles, todos los puzzles tienen la misma, esta barra de aquí
indica longitud, la longitud de arriba y la longitud de abajo, para todas
las fichas de dominó es la misma, es decir, nosotros tenemos aquí en la
primera ficha de dominó omegas 1 y x1, pues estos omegas 1 y x1 podrán
ser distintos entre sí, pero la longitud de omegas 1 y la longitud de x1
es la misma, y así para todas las fichas de dominó. Bueno, nosotros ya
sabemos que el PCP es indecidible, no existe un algoritmo general para
resolver todos los casos, todas las instancias, pero vamos a ver que en
este caso, vamos a estudiarlo, vamos a estudiar en este caso el PCPT, a ver
si podemos estudiar la indecibilidad, o sea que si queréis ahora, para el
mini vídeo, encártalo. Vamos a ir a casa e intentar responder a esa
pregunta, ¿puedo estudiar la indecibilidad o la indecibilidad de este
problema? Nosotros lo vamos a resolver. Bueno, pues es tan sencillo como lo
siguiente, hay que distinguir casos, si hay algún jota, si hay alguna
ficha de dominó, de tal manera que no solamente la longitud de arriba y la
de abajo sea la mía, eso es el PCP tonto, sino que la cadena de arriba,
omega jota, sea igual a la cadena de abajo, x jota, pues en este caso tiene
solución positiva el PCP tonto, existe solución positiva, ¿por qué?
Pues porque el índice que nos vale es coger la ficha dominó. La ficha
dominó y la i sub jota. La i sub jota, esta secuencia de dominó, es la
que tiene solución positiva. No hace falta coger más fichas de dominó,
si ya con una ficha de dominó la parte de arriba es igual a la parte de
abajo, ya entra en correspondencia. ¿Y qué pasa en el caso contrario? En
este otro caso no hay, que no hay un jota tal que la parte de arriba sea
igual a la parte de abajo, pues sencillamente existe solución negativa
para el PCP tonto, para el PCP tonto, porque no hay ninguna ficha de
dominó. Si nosotros vamos poniendo ficha de dominó y aquí la parte de
arriba es distinta a la parte de abajo, para todas las fichas no hay
manera. Precisamente porque la longitud es la misma de arriba que de abajo,
a la hora de poner las fichas de dominó nunca vamos a poder entrar en
correspondencia con la parte de arriba y la parte de abajo. Por lo tanto
existe solución negativa para el PCP tonto. Bueno, pues intentar ahora
parar el mini vídeo y a ver qué hemos aprendido del ceiling, del ceiling
PCP. Nosotros vamos a seguir, pero nosotros intentar parar el mini vídeo.
Bueno, pues lo que hemos aprendido es que hay un tipo de problema en PCP
tonto que está caracterizado por aquellas... Las fichas de dominó donde
las omegas sub i son iguales a los x sub i. No son iguales, sino la
longitud, esta barra de aquí indica la longitud de las x sub i. Todas las
fichas de dominó desde igual a 1 hasta acá son de igual longitud y hemos
demostrado que ese problema del PCP tonto es decidible. En concreto hemos
distinguido dos casos. El primer caso donde hemos visto que existía
solución positiva. Recordad que era el caso donde al menos había ficha de
dominó donde la parte de arriba era exactamente igual a la parte de abajo.
Y el caso 2, donde ninguna parte de arriba era igual a la parte de abajo.
Eso unido con el hecho de que las longitudes de los dominós tenían que
ser iguales nos lleva a caer su solución negativa. Pero esto no entra en
contradicción con el hecho de que el PCP sea indecibible. Puede haber
casos, este es uno de ellos, donde cogemos todos los fichas de dominó
donde el cardinal de arriba sea igual al cardinal de abajo, PCP tonto, y
hemos demostrado la decidibilidad. En unos casos positiva y en otros casos
negativa.