¿Cuánto ayudaría un oráculo SAT a acelerar los algoritmos de tiempo polinomiales?

El acceso a un oráculo proporcionaría una mayor aceleración súper polinomial para todo en (suponiendo que el conjunto no esté vacío). Sin embargo, está menos claro cuánto se beneficiaría de este acceso al oráculo. Por supuesto, la aceleración en no puede ser superpolinomial, pero aún puede ser polinomial. Por ejemplo, ¿podríamos encontrar un camino más corto más rápido con un oráculo que sin él? ¿Qué tal algunas tareas más sofisticadas, como la minimización de funciones submodulares o la programación lineal? ¿Se beneficiarían ellos (u otros problemas naturales en ) de un oráculo ?$SAT$${\bf NP}-{\bf P}$$\bf P$$\bf P$$SAT$$\bf P$$SAT$

En términos más generales, si podemos detectar algún problema en y usar un oráculo para ello, ¿cuál de los problemas en podría ver una aceleración?${\bf NP}-{\bf P}$$\bf P$

En realidad, la aceptación de las máquinas de Turing no deterministas en el tiempo es reducible en tiempo a SAT (la construcción es a través de una simulación inconsciente, ver Arora-Barak), por lo que generalmente cada vez que una máquina no determinista es apreciablemente más rápida que una determinista uno, veremos al menos algo de aceleración con un oráculo SAT.$t$$O(t \log t)$

Para ser más concretos, me viene a la mente la prueba de primalidad, ya que la mejor variante del algoritmo AKS parece probar la primalidad de un número de bits en el tiempo . Pero si vamos a la "vieja escuela", Pratt dio una TM no determinista para decidir la primalidad en el tiempo . La aceptación de esta máquina se puede reducir (determinísticamente) en tiempo a una instancia SAT.$n$$O(n^6 \; \text{polylog}\; n)$$O(n^3 \; \text{polylog}\; n)$$O(n^3 \; \text{polylog}\; n)$

El problema 3SUM puede ser otro ejemplo, ya que parece que uno puede adivinar una solución y verificarla en tiempo subcuadrático, y luego la aceptación de dicha máquina puede reducirse a SAT en tiempo subcuadrático.

En términos más generales, si podemos detectar algún problema en NP − P y usar un oráculo para ello, ¿cuál de los problemas en P podría ver una aceleración?

Esta pregunta se vuelve más directa en la representación y el tiempo requerido para reducir un problema a otro ...

La respuesta principal que tengo en mente es un oráculo de programación entera / lineal. La versión de decisión de ese problema es NP-complete. Hay una "reducción" trivial de la programación lineal porque es un caso especial. Pero un oráculo para la programación lineal solo (y mucho menos para ILP) acelera muchos problemas que pueden resolverse inmediatamente mediante programación lineal. Pueden reducirse en tiempo lineal reescribiendo el problema como un LP. Por ejemplo, caminos más cortos y otros problemas de flujo, coincidencias.

Pero no creo que ILP sea el único de ninguna manera, probablemente es más que la gente no ha pensado mucho, por ejemplo, reducir el camino más corto a TSP, etc.

En una nota relacionada (más de un comentario, publicando como respuesta por solicitud), si en lugar de un oráculo uno permite un oráculo , entonces podría usarse para encontrar circuitos mínimos para cualquier problema en (Esto sigue la misma idea que la prueba de Karp-Lipton). Esto daría un costo amortizado casi óptimo a cualquier problema; la razón por la que solo se amortiza es que si solo usa esto una vez, entonces el tamaño de la fórmula que anota es esencialmente el tiempo de ejecución de su algoritmo original de poli-tiempo, pero después de ese paso, entonces tiene un circuito óptimo para todos instancias de tamaño .Σ 2 S A T P Σ 2 S A T ≤ $SAT$$\Sigma_2 SAT$$\mathsf{P}$$\Sigma_2 SAT$$\leq n$