¿Hay problemas para los cuales dividir y conquistar / recursión es demostrablemente inútil?

Cuando intentamos construir un algoritmo para un nuevo problema, dividir y conquistar (usando la recursividad) es uno de los primeros enfoques que intentamos. Pero en algunos casos, este enfoque parece infructuoso ya que el problema se vuelve mucho más complicado a medida que crece su aporte.

Mi pregunta es: ¿hay problemas para los que podamos probar que un enfoque de divide y vencerás no puede ayudar a resolver? En las siguientes líneas trato de hacer esto más formal.

Supongamos que es un problema determinado cuya entrada tiene un tamaño (por ejemplo, un problema que acepta una entrada y una matriz de números). Supongamos que tenemos un algoritmo recursivo para resolver . El tiempo de ejecución recursivo de ese algoritmo se calcula suponiendo un oráculo que puede resolver por cada en tiempo constante. Por ejemplo: $P(n)$ $n$ $n$ $P(n)$ $P(k)$ $k<n$

El tiempo de ejecución recursivo de la búsqueda binaria es , ya que solo utiliza una comparación y dos llamadas recursivas. $O(1)$
El elemento máximo en una matriz se puede encontrar en el tiempo recursivo . $O(1)$
El tiempo de ejecución recursivo de tipo de fusión es , debido al paso de fusión. $O(n)$

El tiempo recursivo suele ser menor que el tiempo de ejecución real, lo que refleja el hecho de que el algoritmo recursivo es más simple que una solución directa y no recursiva para el mismo problema.

Ahora mi pregunta es:

¿Hay algún problema que pueda resolverse en el tiempo , pero que probablemente no tenga un algoritmo recursivo con tiempo de ejecución recursivo asintóticamente menor que ? $f(n)$ $f(n)$

Algunas variantes específicas de esta pregunta son:

¿Hay algún problema en que no tenga algoritmo con tiempo de ejecución recursivo ? (¿Tal vez clasificando?) $P$ $O(1)$
¿Hay algún problema con un algoritmo exponencial que no tiene un algoritmo con tiempo de ejecución recursivo polinómico?

EDITAR: al contrario de lo que supongo, la ordenación tiene un algoritmo con tiempo de ejecución recursivo $O(1)$ . Por lo tanto, todavía está abierto, si hay un problema en que no tiene algoritmo con tiempo de ejecución recursivo . $P$ $O(1)$

cc.complexity-theory recursion Erel Segal-Halevi
fuente

Tal vez probar un límite inferior de kernelization haría el truco en.wikipedia.org/wiki/Kernelization

Tyson Williams

El tamaño de salida es un límite inferior en el tiempo de ejecución. Por lo tanto, cualquier problema con el tamaño de salida que coincida con su complejidad tiene esta propiedad.

Chao Xu

@Chao Xu: ¿Por qué su argumento no se aplica al tamaño de entrada? Creo que el argumento depende del modelo de costo (y modelo computacional) que consideremos.

Tsuyoshi Ito

Esto es lo opuesto a lo que está buscando, pero dados esos oráculos, su modelo puede resolver la suma de subconjuntos, un problema conocido de NP-Completo, en tiempo lineal, suponiendo que P! = NP es mucho más poderoso que las funciones iterativas en este caso . La función simplemente verificaría si el conjunto actual se agrega a 0, luego, si no, se llama a sí mismo en los n subconjuntos de tamaño n-1. El tiempo de ejecución en sí es n! Sin embargo, lo que es peor que la fuerza bruta, por lo que no estoy realmente seguro de cuánto valor proporciona este modelo, pero sigue siendo una pregunta interesante.

Phylliida

Su edición reciente ("recursiva" -> "divide y vencerás") es un cambio bastante grande a la pregunta. Simplemente publicaría una pregunta por separado en su lugar. Probablemente podamos decir cosas sobre divide-and-conquer mirando, por ejemplo, las profundidades de los circuitos.

usul

Respuestas:

¿Hay algún problema con un algoritmo exponencial que no tiene un algoritmo con tiempo de ejecución recursivo polinómico?

Si. Tenga en cuenta que si un lenguaje de conteo tiene "algoritmo recursivo" con polinomio "tiempo de ejecución recursivo", entonces está en P. Hay un lenguaje de conteo en E ∖ P por un argumento de diagonalización estándar.

¿Hay algún problema que pueda resolverse en el tiempo , pero que probablemente no tenga un algoritmo recursivo con tiempo de ejecución recursivo ? $f(n)$ $o(f(n))$

Puede depender del modelo computacional, pero dudo que esto se conozca, dado que el teorema de la jerarquía de tiempo para las máquinas de Turing de dos cintas no es lo suficientemente poderoso como para distinguir, digamos, el tiempo O ( n ² ) y el tiempo o ( n ² ) incluso sin dar a este último el acceso de tiempo constante a las respuestas en instancias más pequeñas.

Comentarios aleatorios sobre sus preguntas en esta publicación:

No creo que estas preguntas estén relacionadas con la utilidad de los programas recursivos, a pesar de lo que sugieren el título de la publicación y su elección de terminología. Como BVMR escribió en una respuesta, las recursiones e iteraciones son equivalentes en cierto sentido. En cambio, creo que las preguntas tienen una conexión con la utilidad del enfoque de divide y vencerás.
En la teoría de la complejidad, una noción relacionada con su noción de "algoritmos recursivos" con su "tiempo de ejecución recursivo" se denomina "auto-reducciones de disminución de longitud" con su complejidad de tiempo.
Parte de sus preguntas (definitivamente la parte que se refiere a algoritmos de tiempo sublineal) depende de la elección del modelo computacional.

Tsuyoshi Ito
fuente

Con respecto a su primera respuesta: déjenme intentar expandirlo para ver si entiendo correctamente. Suponga que cierto lenguaje de conteo tiene un algoritmo con el "tiempo de ejecución recursivo" polinómico. Se puede construir un algoritmo polinómico para este lenguaje usando programación dinámica. La respuesta para

se puede encontrar en tiempo polinómico ya que no se requieren llamadas recursivas. La respuesta para

se puede encontrar en tiempo polinómico usando la respuesta para

. Luego responde para

se pueden encontrar en tiempo polinómico usando las respuestas para

n = 0

$n=0$

n = 1

$n=1$

n = 0

$n=0$

n = 2

$n=2$

n = 1

$n=1$

n = 0

$n=0$ , etc. ¿Es esto correcto?

Erel Segal-Halevi

Sí, aunque es mejor evitar nociones asintóticas como "tiempo polinómico" cuando se habla de un valor particular de n; por ejemplo, no tiene sentido decir "el algoritmo se ejecuta en tiempo polinómico cuando n = 0". Si un lenguaje de conteo tiene un "algoritmo recursivo" con polinomio "tiempo de ejecución recursivo" p (n), entonces podemos calcular la respuesta para n sin el oráculo calculando las respuestas para 0, 1, 2, ..., n, y esto toma tiempo

, que es polinomial en n.

O (\sum_{i = 0}^{n} p (i))

$O(\sum_{i=0}^n p(i))$

Tsuyoshi Ito

Gracias. Estoy de acuerdo con tu comentario sobre divide-and-conquer y edité la pregunta en consecuencia.

Erel Segal-Halevi

Cualquier pregunta que tenga respuesta recursiva tiene respuesta iterativa y viceversa.

Cualquier algoritmo recursivo puede reescribirse de forma iterativa y viceversa.

Por lo tanto, su pregunta no es válida.

BVMR
fuente

La complejidad de un algoritmo, como lo definí en la pregunta, generalmente no permanece igual cuando se convierte de iterativo a recursivo. Por ejemplo, un algoritmo iterativo con operaciones O (n) puede encontrar el máximo de n elementos, pero también puede encontrarlo un algoritmo recursivo con operaciones O (1) (una de las cuales es una llamada recursiva). Aunque finalmente el tiempo de ejecución de ambos algoritmos es el mismo, el algoritmo recursivo es más simple de programar porque tiene menos operaciones.

Erel Segal-Halevi

-2

No estoy seguro si entiendo correctamente su noción de "complejidad recursiva".

$f$

F (0 0, \vec{X}) = C (\vec{X}) F (norte + 1, \vec{X}) = sol (F (norte, \vec{X}), norte, \vec{X})

$f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x),n,\vec x)$

$c$ $g$ $\mathcal{O}(1)$ $\mathcal{O}(1)$

Si se cumplen todos mis supuestos, entonces el ejemplo que está buscando no puede ser primitivo recursivo.

DFF
fuente

por favor explique los votos a favor

DFF

P (k)

$P(k)$

k < n

$k<n$

g (f (n, x), n, x)

$g(f(n,x),n,x)$

f (n, x)

$f(n,x)$ que tiene tiempo de ejecución constante. No te rechacé, pero esta es una pregunta contestada hace un año y también malinterpretaste una definición dada.

chazisop

g

$g$

O (1)

$\mathcal{O}(1)$

f (n, x)

$f(n,x)$

O (1 \circ 1) = O (1)

$\mathcal{O}(1\circ 1)=\mathcal{O}(1)$

g

$g$

O (1)

$O(1)$

ahh, está bien ... ahora todo tiene sentido ... gracias por la aclaración ... Probablemente estaba confundido por el hecho de que la complejidad recursiva no se invoca de forma recursiva ^^ (que no es muy común en la definición de la OMI)

DFF