Hola.
Se quiere que la verificación se haga en tiempo polinómico del tamaño de la instancia s.
Se quiere que la verificación se haga en tiempo polinómico del tamaño de la instancia s.
El verificador B corre en tiempo polinómico del tamaño de su entrada. Si el tamaño de t, que es parte de la entrada de B, no fuera polinómico en el tamaño de s entonces el tiempo de ejecución de B podría no ser polinómico en el tamaño de s.
Como ejemplo tomemos Independent Set. Una instancia es un grafo G y un entero k. Un algoritmo que pruebe cada uno de los subconjuntos de k vértices podría, no solo verificar, sino resolver el problema porque permitiría decidir si el parámetro es una instancia SÍ o si es una instancia NO. Pero obviamente este algoritmo no es aceptable porque su tiempo de ejecución es exponencial (hay una cantidad exponencial de subconjuntos de tamaño k).
Si no se pusiera la restricción de que el tamaño de t sea polinómico en el tamaño de s, entonces al algoritmo verificador B se le podría pasar como parámetro t el conjunto de todos los subconjuntos de k vértices. Entonces B, con tiempo de ejecución polinómico en el tamaño de su entrada, podría verificar si la instancia es SÍ probando con cada uno de los subconjuntos. Pero este sería, como el anterior, un algoritmo que no solo verifica sino que resuelve el problema en tiempo exponencial del tamaño de la instancia s. Y esto no es aceptable.
Como ejemplo tomemos Independent Set. Una instancia es un grafo G y un entero k. Un algoritmo que pruebe cada uno de los subconjuntos de k vértices podría, no solo verificar, sino resolver el problema porque permitiría decidir si el parámetro es una instancia SÍ o si es una instancia NO. Pero obviamente este algoritmo no es aceptable porque su tiempo de ejecución es exponencial (hay una cantidad exponencial de subconjuntos de tamaño k).
Si no se pusiera la restricción de que el tamaño de t sea polinómico en el tamaño de s, entonces al algoritmo verificador B se le podría pasar como parámetro t el conjunto de todos los subconjuntos de k vértices. Entonces B, con tiempo de ejecución polinómico en el tamaño de su entrada, podría verificar si la instancia es SÍ probando con cada uno de los subconjuntos. Pero este sería, como el anterior, un algoritmo que no solo verifica sino que resuelve el problema en tiempo exponencial del tamaño de la instancia s. Y esto no es aceptable.
¿Explica esto la duda?
Saludos,