Argumento de relleno

Teorema. Si P  = NP , entonces EXP = NEXP .   

Prueba. Por definición, basta con demostrarlo .${\displaystyle {\mathsf {EXP}}\subseteq {\mathsf {NEXP}}}$${\displaystyle {\mathsf {NEXP}}\subseteq {\mathsf {EXP}}}$

Sea L un lenguaje en NEXP , de modo que existe una máquina de Turing no determinista M que verifica en tiempo no determinista , para algún número natural constante c . Ahora definamos el lenguaje con relleno.${\displaystyle x\in L}$${\displaystyle 2^{|x|^{c}}}$

${\displaystyle L'=\{x1^{2^{|x|^{c}}}\mid x\in L\},}$

donde '1' es un símbolo que no aparece en L.

${\displaystyle L'}$está en NP : Dada una entrada , primero verifica que tenga la forma y recházala si no la tiene. Si tiene la forma correcta, verifica usando M , que toma un tiempo no determinista . ${\displaystyle x'}$${\displaystyle x'=x1^{2^{|x|^{c}}}}$${\displaystyle x\in L}$${\displaystyle 2^{|x|^{c}}={\mathsf {poly}}(|x'|)}$

Bajo la suposición P  =  NP, está en P , por lo que hay una máquina determinista DM que decide en tiempo polinomial. ${\displaystyle L'}$${\displaystyle L'}$

Entonces podemos decidir L en tiempo exponencial determinista. Dado el input , escriba y use DM para decidir si . Esto lleva tiempo . ${\displaystyle x}$${\displaystyle x'=x1^{2^{|x|^{c}}}}$${\displaystyle x'\in L'}$${\displaystyle {\mathsf {poly}}(|x|+2^{|x|^{c}})={\mathsf {EXP}}(|x|)}$

Otro teorema demostrado por el argumento del relleno es

Teorema de Ladner . Sientonces existe un problema computacional que es NP-intermedio: enpero no NP-completo. ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$${\displaystyle {\mathsf {NP}}\setminus {\mathsf {P}}}$

Demostración. Supongamos que . Sea SAT el lenguaje de fórmulas satisfacibles. Es NP-completo. Ahora, dada cualquier función tal que sea computable en tiempo , podemos definir el lenguaje con relleno Afirmación 1: SAT* es NP. Esto se demuestra con este algoritmo ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$${\displaystyle H:\mathbb {N} \to \mathbb {N} }$${\displaystyle H(n)}$${\displaystyle {\mathsf {poly}}(n)}$$${\displaystyle {\mathsf {SAT}}^{*}:=\{\phi 1^{|\phi |^{H(|\phi |)}}:\phi \in {\mathsf {SAT}}\}}$$

• Dada una fórmula , si no se ajusta al formato de SAT*, devuelva Falso.${\displaystyle \phi }$
• De lo contrario, elimine el relleno para obtener una fórmula más corta y compruebe si el relleno tiene la longitud especificada . Si no la tiene, devuelva Falso.${\displaystyle \phi '}$${\displaystyle H(|\phi '|)}$
• De lo contrario, compruebe si se trata de un tiempo no determinista .${\displaystyle \phi '\in {\mathsf {SAT}}}$${\displaystyle {\mathsf {poly}}(|\phi '|)\leq {\mathsf {poly}}(|\phi |)}$

Afirmación 2: Si está acotada, entonces SAT* es NP-completo. Dado que está acotada, el relleno toma tiempo polinomial, reduciendo SAT a SAT*. ${\displaystyle H}$${\displaystyle H}$

Afirmación 3: Si , entonces SAT* no es NP-completo. ${\displaystyle H\to \infty }$

Supongamos lo contrario, entonces existe un algoritmo que reduce el problema SAT a SAT* en tiempo . Entonces, podemos decidir SAT en tiempo polinomial de la siguiente manera: ${\displaystyle T}$${\displaystyle n^{c}}$

• Dada una fórmula , si no se ajusta al formato de SAT*, devuelva Falso.${\displaystyle \phi }$${\displaystyle T(\phi )}$
• De lo contrario, por límite superior de tiempo de ejecución, .${\displaystyle |\phi _{1}|^{H(|\phi _{1}|)}+|\phi _{1}|=|\phi _{1}1^{|\phi _{1}|^{H(|\phi _{1}|)}}|=|T(\phi )|\leq |\phi |^{c}}$
• Repetimos este proceso, obteniendo cada vez una fórmula más corta hasta que o bien ${\displaystyle \phi _{1},\phi _{2},\dots }$
  • Si se encuentra una fórmula que no se ajusta al formato de SAT*, devolvemos Falso.
  • o bien obtener una fórmula con una longitud determinada para alguna constante , en cuyo caso simplemente enumeramos por fuerza bruta todas las posibles asignaciones de valores de verdad para . Si es satisfacible, entonces devolvemos Verdadero, de lo contrario devolvemos Falso.${\displaystyle \phi _{k}}$${\displaystyle |\phi _ {k}|\leq C}$${\displaystyle C}$${\displaystyle O(2^{C})}$${\displaystyle \phi _{k}}$${\displaystyle \phi _{k}}$

Siempre que se elija lo suficientemente grande como para que para todo , podemos hacer que cada iteración reduzca la longitud: Por lo tanto, esto requiere iteraciones, y por lo tanto todo el algoritmo se ejecuta en tiempo . La idea es similar a la kernelización . ${\displaystyle C}$${\displaystyle H(m)>2c}$${\displaystyle m>C}$$${\displaystyle |\phi _{1}|^{2}\leq |\phi |,|\phi _{2}|^{2}\leq |\phi _{1}|,\dots ,|\phi _{k}|^{2^{k}}\leq |\phi |}$$${\displaystyle k=O(\ln \ln |\phi |)}$${\displaystyle {\mathsf {poly}}(|\phi |)}$

Paso 4: Construir un , de tal manera que sea computable en tiempo polinomial, , y SAT* no sea P. ${\displaystyle H}$${\displaystyle H}$${\displaystyle H\to \infty }$

Definimos de la siguiente manera: y para valores mayores de , es el entero positivo más pequeño tal que ${\displaystyle H}$${\displaystyle H(0)=0,H(1)=1}$${\displaystyle n}$${\displaystyle H(n)}$${\displaystyle i}$

• ${\displaystyle i\leq f(n)}$.
• Para cualquier longitud , la máquina de Turing decide correctamente con tiempo de ejecución .${\displaystyle \phi }$${\displaystyle |\phi |<g(n)}$${\displaystyle M_{i}}$${\displaystyle \phi \in {\mathsf {SAT}}^{*}}$${\displaystyle \leq i|\phi |^{i}}$

• Si no existe tal máquina de Turing, entonces simplemente establezca .${\displaystyle H(n)=f(n)}$

donde hay dos funciones diseñadas para que sea computable en tiempo .${\displaystyle f(n)=g(n)=\lceil \ln \ln n\rceil }$${\displaystyle H(n)}$${\displaystyle {\mathsf {poly}}(n)}$

Afirmación: está bien definida y es computable en .${\displaystyle H(n)}$${\displaystyle {\mathsf {poly}}(n)}$

Esto se demuestra por inducción sobre . Los casos base simplemente se memorizan. Para el paso de inducción, se prueban todas las máquinas de Turing en todas las fórmulas posibles de longitud , para pasos. También necesitamos probar si , que tarda hasta tiempo comprobando todas las filas de su tabla de verdad . El tiempo total empleado está acotado superiormente por Ahora, si SAT* está en P, entonces sea una máquina que decide SAT* en tiempo . Para suficientemente grande tal que , la construcción permite considerar en la construcción de . Esto muestra que, para todo suficientemente grande , tenemos , y por lo tanto, según la afirmación 2, SAT* es NP-completo, pero entonces tenemos un problema NP-completo que está en P, lo que contradice la suposición de que .${\displaystyle n}$${\displaystyle f(n)}$${\displaystyle 2^{g(n)}}$${\displaystyle \phi }$${\displaystyle |\phi |\leq g(n)}$${\displaystyle i|\phi |^{i}\leq f(n)g(n)^{f(n)}}$${\displaystyle \phi \in {\mathsf {SAT}}^{*}}$${\displaystyle 2^{g(n)}}$$${\displaystyle f(n)2^{g(n)}f(n)g(n)^{f(n)}+2^{g(n)}2^{g(n)}\leq {\mathsf {poly}}(n)}$$${\displaystyle M_{m}}$${\displaystyle Cn^{C'}}$${\displaystyle n}$${\displaystyle f(n)>\max(C,C',m)}$${\displaystyle M_{m}}$${\displaystyle H(n)}$${\displaystyle n}$${\displaystyle H(n)=m}$${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$

Por lo tanto, SAT* no pertenece a P. Esto implica que se vería obligado a crecer hacia el infinito. Según la afirmación 3, SAT* no es NP-completo.${\displaystyle H(n)}$