Creo que un teorema de jerarquía de tamaño para la complejidad del circuito puede ser un gran avance en el área. ¿Es un enfoque interesante para la separación de clases? La motivación para la pregunta es que tenemos que decir hay alguna función que no puede calcularse mediante circuitos de...
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...
¿Qué tipo de teoremas de jerarquía existen para la profundidad del circuito? Declaraciones como g(n)∈o(f(n))g(n)∈o(f(n))g(n) \in o(f(n))f(n)∈nO(1)f(n)∈nO(1)f(n) \in n^{O(1)}SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))\mathsf{SizeDepth}(n^{O(1)}, g(n))...
Pregunta general ¿El teorema de la jerarquía espacial se generaliza a la computación no uniforme? Aquí hay algunas preguntas más específicas: ¿Es ?L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Para todas las funciones construibles en el espacio f(n)f(n)f(n) , ¿es...
Sabemos que . Del teorema de Savitch, , y, del Teorema de la jerarquía espacial, . Entonces, como no sabemos si , no sabemos si , o sabemos que ? ¿Alguien ha intentado demostrar que \ mathcal L ^ 2 \ subseteq \ mathcal P ? ¿Cuáles son los últimos resultados o esfuerzos de esta manera? He estado...
\newcommand{\cc}[1]{\mathsf{#1}} ¿Se un teorema en las siguientes líneas: Si es un poco más grande que , entonces ?f ( n ) N T I M E ( g ) ∩ c o N T I M E ( g ) ≠ N T I M E ( f ) ∩ c o N T I M E ( f )sol( n )g(n)g(n)F( n )f(n)f(n)N T I M E (g) ∩ c o N T I M E ( g) ≠ N T I M E ( f) ∩ c o N T I M E (...