Brechas comprobables entre la complejidad del árbol de decisión y la complejidad "verdadera"

El título es un poco engañoso: pero espero que la pregunta no sea:

El nuevo resultado de Grønlund y Pettie que muestra que 3SUM solo tiene la complejidad del árbol de decisión me hizo preguntarme: $O(n^{3/2})$

¿Hay un ejemplo simple de un problema con una complejidad de árbol de decisión de pero que admite un límite inferior (en un modelo más detallado) de ? $O(f)$ $\omega(f)$

En otras palabras, ¿cómo debería el resultado en 3SUM cambiar nuestra visión de la posibilidad de obtener un límite superior significativamente menor que en la complejidad del problema? $n^2$

cc.complexity-theory machine-models decision-trees Suresh Venkat
fuente

Ω (n \log n)

$\Omega(n\log n)$

El modelo de árbol de decisión es un modelo teórico de información: una vez que haya aprendido suficiente información acerca de su entrada para que la respuesta se determine de manera única a partir de esta información, habrá terminado. No importa si determinar la respuesta a partir de esta información es indecidible. Entonces, por ejemplo, si la entrada es una cadena binaria de n bits que codifica una máquina Turing, y la pregunta es si esta TM se detiene, un árbol de decisión de profundidad n puede resolver trivialmente este problema ya que conoce todos los n bits, pero ningún algoritmo puede resolver este problema.

Robin Kothari

Tal vez debería haber dicho 'ejemplo de un problema simple' en su lugar :).

Suresh Venkat

Respuestas:

Meyer auf der Heide describió una familia no uniforme de árboles de decisión lineal para Subset Sum con profundidad . Un resultado similar puede derivarse de un algoritmo posterior de Meiser para la ubicación de puntos en arreglos de hiperplano. Por supuesto, el problema es NP-hard. $O(n^4\log n)$

Jeffε
fuente

Si quisiera ser REALMENTE PEDÁNTICO, señalaría que ser NP-hard no es un límite inferior firme. pero ese es un buen ejemplo del espíritu de lo que estoy buscando.

Suresh Venkat

Sí, pero no sabemos cómo demostrar límites inferiores firmes.

Jeffε

@ Jɛ ﬀ E ¿Quizás conoces una buena redacción o exposición de este resultado? El original me parece muy difícil de seguir, algunas definiciones no están claras para mí.

domotorp

Al menos las definiciones básicas se describen en mi artículo sobre problemas de degeneración lineal .

Jeffε

$O(n\log(\frac{m+n}{n}))$ $\Theta(n+m)$ $m=\omega(n)$

Seth Pettie
fuente

Déjame estar en desacuerdo un poco. En el modelo RAM, no necesariamente necesitamos leer toda la entrada. En el modelo de máquina de Turing, hay muchos problemas triviales que pueden resolverse más rápidamente con un árbol de decisiones (o en una máquina RAM). Vea también el comentario de Robin a la pregunta original.

domotorp