Problemas que probablemente requieren tiempo cuadrático

Estoy buscando ejemplos de problemas que tengan un límite inferior de $\Omega(|x|^2$ ) para la entrada $x$ .

El problema debe tener las siguientes propiedades:

$\Omega(n^2)$ Prueba de tiempo de ejecución de para cualquier algoritmo: la primera prioridad es tener un argumento de límite inferior tan simple como sea posible.
$O(n^2)$ algoritmo, si es posible, simple también.
Tamaño de salida de $O(n)$ (o menor). Obviamente, cualquier problema que requiera una salida alargada de $\Omega(n^2)$ requirió al menos un tiempo de ejecución similar, pero eso no es lo que estoy buscando. Tenga en cuenta que cualquier problema de decisión cabe aquí.
(si es posible) un problema "natural". Sin una definición formal, un problema que cualquier graduado de CS reconocería es preferible.

Recientemente me preguntaron sobre ese problema, pero no pude encontrar uno simple. El primer problema que se me ocurrió fue $3SUM$ , que se conjugó para ser un problema de tiempo de ejecución de $\Omega(n^2)$ . Esto no fue lo suficientemente simple y, además, la coyuntura recientemente demostró ser falsa : o.

El ir a un problema extremadamente poco natural, creo que el problema que se pone como una entrada de una MT determinista y la entrada $\langle M \rangle,x$ , y da salida a la posición de la cabeza de la cinta después de $(|M|+|x|)^2$ pasos cuando es corriendo en $x$ probablemente responde la pregunta.

Si es absolutamente necesario, aceptemos que estamos usando el modelo TM de una sola cinta, aunque prefiero los problemas cuyo tiempo de ejecución es independiente del modelo exacto (siempre que sea razonable).

Entonces, ¿podemos encontrar un problema simple (para probar), natural (bien conocido) cuyo tiempo de ejecución es ? $\Theta(n^2)$

Creo que "Dados los números naturales

, calcular

" califica. Además, tenga en cuenta esta pregunta .

x

$x$

y

$y$

x + y

$x+y$

Raphael

La única forma en que sabemos cómo probar los límites inferiores superlineales en máquinas Turing de múltiples cintas es a través de la diagonalización. Para las máquinas de Turing de una sola cinta, puede mejorar un poco el uso de secuencias cruzadas, pero no tan lejos como

menos que tal vez restrinja el espacio.

n^{2}

$n^2$

Yuval Filmus

Vea aquí para otra pregunta relacionada; La inversión de entrada parece ser un buen candidato.

Raphael

No creo que pueda hacerlo con un problema de decisión, porque el límite inferior mejor encontrado para NP es O (n).

Albert Hendriks

Gracias por tu comentario @AlbertHendriks. ¿Puede compartir una referencia a una fuente / encuesta que afirme que el límite inferior más conocido para cualquier problema en NP es

Ω (n)

$\Omega(n)$

Respuestas:

Encontrar un corte de pastel sin envidia requiere consultas . Sin embargo, esto no responde directamente a su pregunta, ya que el modelo computacional es diferente a una máquina de Turing. $\Omega(n^2)$

Por cierto, actualmente el algoritmo más rápido conocido para este problema requiere consultas, por lo que hay una gran brecha desde el límite inferior, probablemente una de las brechas más grandes en informática. $n^{n^{n^{n^{n^{n}}}}}$

Erel Segal-Halevi
fuente

Al igual que en el enlace proporcionado por Raphael, Peter muestra que la inversión de entrada requiere un tiempo $\Theta(n^2)$ en TMs de cinta única de vainilla. Para un problema de decisión, el lenguaje

L = {x 0^{| x |} x ∣ x \in {0, 1}^{*}}

$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$ también probablemente necesita

Θ (n^{2})

$\Theta(n^2)$ tiempo para calcular. Para ver esto, use el argumento de complejidad de comunicación de Peter, junto con un resultado clásico que

E Q_{n}

$EQ_n$ necesita

Θ (n)

$\Theta(n)$ bits de comunicación, que muestra la cuadrática límite inferior de

L

$L$ . El enfoque similar funciona para uno más natural

L = {x x ∣ x \in {0, 1}^{*}}

$L = \{xx \mid x \in \{0,1\}^\ast \}$ .

Por cierto, vale la pena mencionar que el "método de secuencia cruzada" mencionado por Yuval es (según mi mejor conocimiento) matemáticamente equivalente (o, tal vez, informante) al complejo de comunicación.

Por otro candidato que no responde directamente a su pregunta, Ryan Williams demostró que $\mathsf{SAT}$ no puede ser decidido en $O(n^{2 \cos(\pi/7)})$ tiempo y simultáneamente $n^{o(1)}$ espacio en RAM. Mientras que la constante $2 \cos(\pi/7) \approx 1.8$ parece bastante mágica, la idea inicial que surge de Fortnow es ingeniosa pero no tan complicada. Consulte la página 101 en el libro de texto de Barak y Arora para una exposición de la idea.

Lwins
fuente