Los teoremas de la jerarquía son herramientas fundamentales. Un buen número de ellos se recopiló en una pregunta anterior (consulte ¿Qué jerarquías y / o teoremas de jerarquía conoce? ). Algunas separaciones de clase de complejidad se derivan directamente de los teoremas de jerarquía. Ejemplos de tales separaciones bien conocidas: , , , .
Sin embargo, no todas las separaciones se derivan de un teorema de jerarquía. Un ejemplo muy sencillo es . Aunque no sabemos si alguno de ellos contiene el otro, siguen siendo diferentes, porque está cerrado con respecto a las transformaciones polinómicas, mientras que no lo está.
¿Cuáles son algunas separaciones de clase de complejidad más profundas, incondicionales y no relativizadas para clases uniformes que no se siguen directamente de algún teorema de jerarquía?
fuente
Respuestas:
Me encantaría que me mostraran mal, pero no creo que actualmente haya límites inferiores uniformes que no estén basados en uno de los teoremas de la jerarquía. Nuestra comprensión actual de cómo aprovechar la uniformidad es realmente bastante limitada en ese sentido.
Por otro lado, hay muchos límites inferiores uniformes que no se siguen directamente de los teoremas de jerarquía, pero usan un teorema de jerarquía en combinación con otros trucos, técnicas y resultados inteligentes, por ejemplo:
fuente
¿Es la separación de Smolensky algo que has estado buscando?A C0 0⊊ T C0 0
fuente
Otro ejemplo no trivial proviene del área de la complejidad promedio de los casos. Rainer Schuler demuestra propiedades interesantes de la clase que él llama , ver [1].PP−comp
es la clase de lenguajes que se aceptan en tiempo polinómico con unpromedio μ paracadadistribución detiempo polinómico computable (P-computable) μ . Naturalmente, P ⊆ P P - c o m p se cumple, ya que la existencia de un algoritmo determinista de polytime implica que sigue siendo eficiente en promedio, sin importar cuál sea la distribución de entrada. Sin embargo, la condición de ejecución en tiempo polinómico promedio paracadadistribución de entrada computable P parece lo suficientemente fuerte como para sospechar P P -PP−comp μ μ P⊆PP−comp .PP−comp=P
Sorprendentemente, Schuler demuestra que existe un lenguaje , que es Turing completo para E , es decir, E ⊆ P P P - c o m pL∈PP−comp mi
Esto implica la separación incondicional P P - c o m p ≠ P . Si bien este último también utiliza el hecho E ≠ P , que se deriva del Teorema de la Jerarquía del Tiempo, la parte novedosa (*) se basa en diferentes herramientas: más allá de la diagonalización, emplea la medida limitada por los recursos y la complejidad de Kolmogorov.
Referencia:
[1] R. Schuler, "El cierre de la tabla de la verdad y el cierre de Turing del tiempo polinómico promedio tienen diferentes medidas en CAD", CCC 1996, pdf
fuente