Teorema de Ladner en TOC

El teorema de Ladner en TOC:
como probablemente sepa, independientemente de si P = NP es un problema significativo y desconcertante en el campo de la informática. En complejidad computacional, aquellos problemas que pertenecen a NP-problemas pero que no pueden pertenecer a P o NP-completos se conocen como problemas NP-intermedios .

Teniendo en cuenta los problemas NP-completos, es normal seguir pensando si tenemos una división entre P y NP-completos, para ser específicos si P o NP se componen solo de problemas NP-completos, en caso de que P ≠ NP . 

Incluso si piensa en P ≠ NP, es atractivo creer que NP = P ∪ NP-completo, que cada problema en NP puede abordarse en tiempo polinomial o es lo suficientemente expresivo como para codificar SAT. Todos estos problemas fueron resueltos por Ladner, su teorema prueba que existe una complejidad intermedia. 

Problemas NP-intermedios:
Una lengua L ∈ NP es NP-intermedia si y sólo si L∉ P y L∉ NP-completa.

Teorema de Ladner: 
Si P ≠ NP entonces hay una lengua L que es una lengua intermedia NP.
En otras palabras, si P ≠ NP es cierto, entonces NP Intermedio no está vacío, significa que NP contiene problemas que no están ni en P ni en NP-completo.

Demostración: 
usando diagonalización, 

supongamos una función especial H : N –> N tal que :

• O(m ³ ) tiempo requerido para procesar H(m) a partir de m.
• H(m) –> ∞ con m si SAT _H ∉ ​​P.
• H(m) ≤ C (C= constante) si SAT _H ∈ PAGS .
• Ahora, sea SAT _H = {Ψ ₀ 1 ^{m^ H(m)} : Ψ ∈ SAT y |Ψ| = metro}

Teniendo en cuenta P ≠ NP, H se caracteriza de modo que SAT _H   es NP-intermedio.

1. Sea SAT _H ∈ P. Entonces H(m) ≤ C.
Esto sugiere un algoritmo politemporal para SAT como sigue:

• primero ingrese ϕ y obtenga el valor de m = |ϕ|.
• Ahora genere una string ϕ 0 1 ^{m^ H(m)} a partir de H(m) calculados.
• Verifique si la cuerda ϕ 0 1 ^{m^ H(m)}   ∈ SAT _H. 

Resultado : por lo tanto, debería ser SAT _H ∉ ​​P , debido a que P ≠ NP.

2. Sea SAT _H ∈ NP-completo. Esto implica H(m)–>∞ con m.
Esto sugiere un algoritmo poli-tiempo para SAT de la siguiente manera:

• SAT ≤ _p SAT _H    y ϕ–> Ψ 0 1 ^k 
• primera entrada ϕ con m = |Ψ| , y obtenga el valor de f(ϕ) = Ψ 0 1 ^k .
• Verifique si k = m ^H(m) procesando H(m).
• Esto sugiere, n ^c = |f(ϕ)| ≥ k ≥ metro ^2c .

Por lo tanto, √n ≥ m También ϕ ∈ SAT si Ψ ∈ SAT.
Solo se necesitan pasos recursivos O (log log n).

Resultado: por lo tanto, SAT _H ∉ ​​NP-completo, como P ≠ NP. 

Construcción de H: 
Ahora, para la construcción de H, notamos que el valor de H(m) gobierna
la membresía en SAT _H de strings, aquí longitud de SAT _H de string ≥ m. 

• Por lo tanto definiremos H(m) cuya longitud es < m , según la string en SAT _H .
• Ahora, para la construcción, sabemos que H(m) es el k < log (log m) más pequeño tal que M _k  elige la participación de todas las longitudes hasta log m strings x en SAT _H dentro de k. |x|  tiempo ^k _.   Si no, entonces podemos decir H(m) = log (log m). 
• Ahora H(m) ≤ C si y solo si SAT _H ∈ P es verdadero.

Existe un poli-tiempo M que elige matrícula de cada x ∈ SAT _H dentro de c. |x| ^{tiempo c}  . Aquí M puede ser direccionado por muchas strings, hay α ≥ c tal que M = M*α elige la participación de cada x ∈ SAT _H dentro de α.|x| ^{tiempo α}  .
Por tanto, H(m) ≤ α para todo m que satisfaga α < log (log m). 

• Si SAT _H ∈ P entonces H(m) ≤ C (para infinitos m).
   H(m) = k para infinitos m cuando k ≤ C esta condición es verdadera. 

haga cualquier x ∈ {0,1}* ahora encuentre el M más grande tal que |x| ≤ log m y H(m) = k. Aquí x se decide por M _k en k. |x| ^k tiempo.
SAT _H está determinado por M _k , que es una máquina poli-tiempo. 

Propiedades de H: 
Las propiedades de H son las siguientes:

• O(m3) tiempo requerido para procesar H(m) a partir de m.
• H(m) –> ∞ con m si SAT _H ∉ ​​P.
• H(m) ≤ C (C= constante) si SAT _H ∈ PAGS .

Límites de diagonalización:
La diagonalización es una técnica utilizada para separar conjuntos. Aquí queremos separar dos conjuntos NP y P para el conjunto intermedio NP. El teorema de Kozen muestra que la diagonalización fuerte no relativiza.

 Si bien la pregunta P versus NP aún no está resuelta, hemos refinado nuestra atención sobre el tema. A pesar de que existe una prueba sólida en contra de la capacidad de la diagonalización para aislar P y NP, hemos demostrado que esto no importa para nuestra idea de diagonalización sólida. Además, la diagonalización sólida es la mejor manera de aislar estos P y NP, como ilustró Kozen en su teorema.

Ejemplos de problema NP-intermedio:

• Cálculo del logaritmo discreto.
• Problema de isomorfismo de grafos.
•  Factorizando el logaritmo discreto.
• Aproximación del vector más corto en una red.
• Problema de tamaño mínimo del circuito.