En este mini vídeo vamos a ver un ejemplo del programa del PCP y del
PCP-M. Nosotros ya sabemos la indecibilidad de estos problemas, pero vamos
a ver un ejemplo concreto, vamos a estudiar esta indecibilidad. Tenemos
aquí un ejemplo en el cual nos dan tres fichas de dominó, tres puzzles.
En la primera ficha de dominó tenemos un 1 arriba y tres 1 abajo. En la
segunda ficha de dominó tenemos arriba 1, 0, 1, 1, 1 y abajo 1, 0. Y en la
tercera ficha de dominó tenemos arriba 1, 0 y abajo 0. Se trata en el
programa del PCP de encontrar una ordenación de estas fichas de dominó,
de estos puzzles. Nosotros podemos encontrar... repetición de estas fichas
o no un conjunto de índices de tal manera que la lista que quede aquí
arriba y la lista que queda aquí abajo sea la misma ya sabéis de otros
mini vídeos que en la primera ficha si se elige que sea el primer índice,
la primera ficha estamos trabajando con el PCP-N modificado y si dejamos
libertad a la primera ficha es el programa PCP bueno pues vamos a hacer en
este ejemplo os animo también a que ya que habéis visto el mini vídeo de
teoría del PCP y PCP-M y podéis intentar estudiar en concreto este
ejemplo nosotros lo vamos a resolver Para ello vamos a resolver primero el
PCPM, entonces empezamos escribiendo la primera ficha de dominó que tenía
un 1 arriba y tres 1 abajo y vamos a poner y imaginar la segunda ficha de
dominó. La segunda ficha de dominó a continuación que estaba dada por 1,
0, 1, 1, 1 y abajo por 1, 0. Se trataría de ver, ahora lo ponemos ya
juntos, 1, 1, abajo 1, 3, 1, copiaríamos arriba el 1, 0, 1, 1, 1 y abajo
en la parte 1, 0 de la segunda ficha de dominó e intentamos ver si esta
lista de arriba está en correspondencia con la lista de abajo. Ya vemos
que aquí en la tercera columna hay un 0 y un 1, no están en
correspondencia, por lo tanto la primera y la segunda no sería en
principio buen camino para resolver este PCPM. Bueno, pues vamos a probar
con otra posibilidad. Volvemos otra vez a poner la primera ficha de
dominó, la de 1 y abajo 3, 1 y vamos a coger la tercera ficha de dominó
que tiene un 1, 0 arriba y un 0 abajo. Bueno, lo vamos poniendo aquí ya,
escribimos el 1, 0 a continuación del primer 1 y abajo en la primera fila
a continuación de los tres 1 ponemos el 0 y vemos que aquí de nuevo en la
tercera columna no está en correspondencia la lista de arriba con la
cadena de arriba con la cadena de abajo. Por tanto tampoco vamos por buen
camino cogiendo la primera ficha y la tercera ficha. Gracias. Bien, pues
ahora la única posibilidad es volver a repetir la primera ficha. No pasa
nada porque en el PCPM o en el PCP se repitan los índices. En este caso
estaríamos cogiendo en la primera ficha de dominó y después la primera
ficha de dominó. Vamos a ver si vamos bien. La primera ficha de dominó
tiene un 1 arriba y 3 unos abajo. Pues esto lo hemos puesto aquí, un 1 y 3
unos. Y la segunda ficha de dominó volvemos a repetir otra vez un 1 arriba
y otra vez 3 unos abajo. Vemos que están en correspondencia la primera
columna y la segunda columna. Por lo tanto, vamos por buen camino. Vamos a
ver ahora si podemos poner, por ejemplo, la segunda ficha de dominó. Si
intentamos poner la segunda ficha de dominó dada por 1 0 1 1 1, ponemos 1
0 1 1 1 y abajo tenía un 1 y un 0, pues vemos que en la cuarta columna de
aquí ya no está en correspondencia la primera cadena de arriba con la
cadena de abajo. Por lo tanto, la solución primera ficha de dominó,
primera ficha de dominó, segunda ficha de dominó, no es buena. Bien, pues
vamos a intentar ahora con la solución que teníamos en el momento de la
primera ficha y coger después la primera ficha otra vez. Vamos a ver si
podemos coger ahora la tercera ficha dada por 1 0 arriba y 0 abajo. Y si la
ponemos aquí, 1 0 y el 0, pues vemos que en la cuarta columna no vuelve a
estar en correspondencia. Por lo tanto, esta no es una buena solución.
Bien, pues la única opción que nos queda es volver a coger la ficha 1,
coger la ficha 1, y volver otra vez a coger la ficha 1. Si procedemos así,
pues tenemos un 1 arriba, 3 1s abajo de la primera ficha, un 1 arriba, 3 1s
abajo de la primera ficha, un 1 arriba, 3 1s de la primera ficha abajo, y
vemos que de momento todo está en correspondencia. Lo que ocurre es que la
cadena de abajo va creciendo ilimitadamente y la cadena de arriba se va
quedando cada vez más corta. Es un razonamiento que se puede seguir y
siempre, nunca podremos utilizar la ficha 2, nunca podremos utilizar la
ficha 3, siempre estamos obligados a repetir la ficha 1. Por lo tanto, en
este caso, en este ejemplo, podemos decir que existe solución negativa
para este problema de PCP modificado, PCPM. Bien, vamos a estudiar ahora la
indecibilidad del PCP. El PCP ya hemos visto que puede empezar por
cualquier ficha, por la primera, por la segunda, por la tercera. Hemos
visto que por la primera, que era el caso del PCPM, no llegamos a ninguna
solución. Por lo tanto, vamos a empezar ahora con la segunda ficha para
ver si el PCP, en este caso, es decidible o no lo es. La primera ficha de
dominio tenía 1 0 1 1 1 arriba y 1 0 abajo. Vamos ahora a pegarle,
veíamos antes que podemos repetir la ficha de dominio, no hay ningún
problema. Vamos a pegarle ahora la segunda ficha otra vez. Tendríamos 1 0
1 1 1 arriba y 1 0 abajo. Y vemos que en la columna cuarto no hay
correspondencia. No hay correspondencia. Segunda y segunda, pues no es
válida. Y vamos a ver qué ocurre si cogemos la segunda ficha y la tercera
ficha, que está dada por 1 0 arriba y 1 0 abajo. Ponemos aquí 1 0 y 0 y
vemos ahora que la tercera columna no entra en correspondencia. Por lo
tanto, tampoco es una solución. Y ya entonces lo único que nos queda es
intentar con la primera. Si nosotros cogemos la segunda ficha de dominó y
después la primera ficha de dominó, pues tenemos por un lado la segunda
ficha de dominó tenía arriba 1, 0 y 3, 1, abajo tenía 1, 0. Si cogemos
la primera ficha de dominó le pegaríamos 1, 1 arriba y 3, 1 abajo y vemos
que de momento todas las columnas entran en correspondencia. Por lo tanto
esta es una de momento vamos bien. Bueno, pues vamos a intentar ahora coger
por ejemplo la segunda ficha de dominó. La segunda ficha sería 1, 0, 1,
1, 1, abajo 1, 0 y vemos ahora que la columna número 7 pues no entra en
correspondencia por lo tanto este camino pues no va bien. Y vamos a ver
qué pasa si estábamos con un momento la solución 2, 1 y vamos a pegarle
no ahora la 2 sino la 3 que viene dada por 1, 0 arriba y 0 abajo. 1, 0 y 0
y vemos que en esta columna, en la columna número 6 pues no entra en
correspondencia lo cual por lo tanto es una mala solución. Y ya la única
cosa que nos queda probar a ver si tenemos suerte es con la primera.
Primero la segunda ficha de dominó, luego con la primera ficha de dominó,
luego con la primera a ver si así vamos bien. La segunda ficha de dominó
era 1, 0, 3, 1 arriba, 1, 0 abajo. Hemos pegado la primera ficha de dominó
que tiene un 1 arriba y 3, 1 abajo. Y la primera ficha de dominó y 3, 1
abajo y vemos que de momento todo está en correspondencia arriba y abajo.
Si ahora observamos aquí poniendo ahora la tercera ficha de dominó 1, 0 y
abajo le tocaría el 0 vemos que todo entra en correspondencia. La primera
cadena de arriba con la cadena de abajo. Y entonces tendríamos que... Si
la solución segunda ficha de dominó, primera ficha de dominó, primera y
tercera sería una solución positiva. Existe solución positiva para este
problema de PC-PCP. Bien, ahora intentar parar el minivídeo en casa a ver
qué habéis aprendido de este problema y yo voy a seguir. Bueno, pues
hemos aprendido una cosa y es que para este ejemplo el PCPM tiene solución
negativa. tiene solución negativa el PCP modificado y que tiene una
solución positiva el PCP Esto a lo mejor podría parecer, pero esto es una
contradicción porque nosotros hemos visto en los mini-minios que tanto el
PCP como el PCPM son indecidibles. Bueno, pero eso significa que no existe
un algoritmo que valga para todos los ejemplos, para todas las instancias.
Pero puede ocurrir para algunos ejemplos en concreto donde podamos decir si
existe solución negativa o si existe solución positiva, como ha pasado en
este ejemplo. Bien, pues ahora intentar inventaros un ejemplo distinto, a
ver si sois capaces de saber la indecibilidad o no del PCP y en otros mini
vídeos veremos más ejemplos.