En la teoría de la complejidad computacional , el argumento de relleno es una herramienta para probar condicionalmente que si algunas clases de complejidad son iguales, otras clases más grandes también son iguales.
Ejemplo
La prueba de que P = NP implica EXP = NEXP usa "relleno". por definición, basta con mostrar .
Sea L un idioma en NEXP. Dado que L está en NEXP, hay una máquina de Turing no determinista M que decide L en el tiempopara alguna constante c . Dejar
donde 1 es un símbolo que no ocurre en L . Primero mostramos queestá en NP, entonces usaremos la máquina del tiempo polinomial determinista dada por P = NP para demostrar que L está en EXP.
se puede decidir en tiempo polinomial no determinista de la siguiente manera. Entrada dada, verifica que tenga la forma y rechazar si no es así. Si tiene la forma correcta, simule M (x) . La simulación toma medidas no deterministas tiempo, que es polinomio en el tamaño de la entrada, . Entonces,está en NP. Suponiendo que P = NP, también hay una máquina determinista DM que decideen tiempo polinomial. Entonces podemos decidir L en tiempo exponencial determinista de la siguiente manera. Entrada dada, simular . Esto solo toma un tiempo exponencial en el tamaño de la entrada,.
La que se llama el "relleno" de la lengua L . Este tipo de argumento también se usa a veces para clases de complejidad espacial, clases alternas y clases alternas acotadas.
Referencias
- Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge , p. 57, ISBN 978-0-521-42426-4