¿Qué se sabe sobre la complejidad de encontrar circuitos mínimos para SAT?

¿Qué se sabe sobre la complejidad de encontrar circuitos mínimos que computan SAT hasta una longitud $n$ ?

Más formalmente: ¿cuál es la complejidad de una función que, dado como entrada, genera un circuito mínimo tal que para cualquier fórmula φ con , ?$1^{n}$$C$$\varphi$$|\varphi| \leq n$$C(\varphi) = SAT(\varphi)$

(Estoy específicamente interesado en los límites inferiores).

El algoritmo determinista ingenuo (calcular SAT por fuerza bruta hasta la longitud , luego probar todos los circuitos en orden de tamaño hasta que encuentre uno que calcule correctamente la SAT hasta la longitud ) toma tiempo para calcular SAT, y luego un tiempo adicional de para encontrar un circuito mínimo, donde es el tamaño del circuito mínimo. $n$$n$$\leq 2^{O(n)}$$O(2^n 2^M)$$M$

¿Existe un algoritmo determinista que encuentre circuitos mínimos para SAT cuyo tiempo de ejecución es , donde es el tamaño del circuito mínimo? ¿O esto implica un colapso de complejidad?$o(2^n 2^M)$$M$

Aquí hay dos cosas que, aunque están relacionadas con mi pregunta, definitivamente no son lo que estoy preguntando (que es, creo, por qué me resultó un poco difícil de buscar):

• El problema circuito de minimización: dado un circuito de (o una función dada por su tabla de verdad, o varias otras variantes) encuentran un circuito mínimo calculando la misma función que . Incluso si la minimización del circuito fuera fácil, no implicaría necesariamente que la tarea anterior sea fácil, ya que incluso calcular la función que queremos minimizar (SAT hasta la longitud ) se considera difícil, mientras que en el problema de minimización del circuito la función querer minimizar es gratis (se da como entrada).f C ′ C $C$$f$$C'$$C$$n$

• $NP$ versus . Mi pregunta no es simplemente sobre qué tamaño tiene el circuito mínimo; Se trata de la complejidad de encontrar un circuito mínimo, independientemente de su tamaño. Obviamente, si podemos calcular circuitos mínimos en tiempo polinomial, entonces (y de hecho , ya que la familia de circuitos es -uniforme), pero lo contrario no tiene por qué ser cierto. De hecho, creo que Immerman y Mahaney fueron los primeros en construir un oráculo donde pero , es decir, tiene circuitos de tamaño polinómico pero no se pueden encontrar en el tiempo polinomial.$P/poly$$NP \subseteq P/poly$$NP \subseteq P$$P$P ≠ N P N $NP \subseteq P/poly$$P \neq NP$$NP$

Supongamos que uno no puede resolver SAT mucho más rápido de manera no uniforme que uniformemente. Es decir, hay un TM M resolviendo SAT en el tiempo T (n), y el circuito más pequeño para SAT tiene un tamaño T '(n) que no es mucho más pequeño que T (n) (digamos, : en particular, esto se cumple si el circuito más pequeño para resolver SAT tiene un tamaño de 2 Ω ( n ) que muy bien puede ser cierto).$T(n) = poly(T'(n))$$2^{\Omega(n)}$

Por lo tanto, podría obtener un circuito "casi" mínimo simplemente ejecutando una simulación canónica de M por un circuito, en el tiempo que es básicamente óptimo (tanto tiempo como le tome escribir la salida). Solo por esta razón, supongo que no habrá límite inferior para esta pregunta basada en cualquier suposición "agradable". Sin embargo, no sé cómo pasar de "casi mínimo" a realmente mínimo. Una forma de hacerlo será utilizar el hecho de que encontrar el circuito hasta el tamaño es una pregunta en la jerarquía polinómica,$S$$T(T(n))$$2^{o(M)}$ .$T(n)=2^{n^{o(1)}}$