Compensación entre tiempo y complejidad de consulta

18

Trabajar directamente con la complejidad del tiempo o los límites inferiores del circuito es aterrador. Por lo tanto, desarrollamos herramientas como la complejidad de la consulta (o la complejidad del árbol de decisiones) para manejar los límites inferiores. Dado que cada consulta toma al menos un paso unitario, y los cálculos entre consultas se cuentan como gratuitos, la complejidad del tiempo es al menos tan alta como la complejidad de la consulta. Sin embargo, ¿podemos decir algo sobre las separaciones?

Tengo curiosidad sobre el trabajo en la literatura clásica o cuántica, pero proporciono ejemplos de QC ya que estoy más familiarizado.

Algunos algoritmos famosos, como la búsqueda de Grover y el período de búsqueda de Shor, la complejidad del tiempo está dentro de los factores polilogarítmicos de la complejidad de la consulta. Para otros, como el problema del subgrupo oculto, tenemos una complejidad de consulta polinómica , aunque no se conocen algoritmos de tiempo polinomiales.

Dado que existe una brecha potencial entre el tiempo y la complejidad de la consulta, no está claro que un algoritmo de complejidad de tiempo óptimo tenga que tener la misma complejidad de consulta que el algoritmo de complejidad de consulta óptima.

¿Hay ejemplos de compensaciones entre el tiempo y la complejidad de la consulta?

¿Existen problemas en los que el algoritmo de complejidad de tiempo más conocido tiene una complejidad de consulta diferente que el algoritmo de complejidad de consulta más conocido? En otras palabras, ¿podemos realizar más consultas para facilitar las operaciones entre consultas?

¿O hay un argumento que muestra que siempre hay una versión de un algoritmo de consulta asintóticamente óptimo que tiene una implementación con la mejor complejidad de tiempo asintóticamente?

cc.complexity-theory reference-request time-complexity query-complexity Artem Kaznatcheev
fuente

¿Quieres un problema natural o un problema artificial también está bien?

Robin Kothari

2

Se prefieren los problemas naturales, pero los problemas artificiales son mejores que ninguna respuesta.

Artem Kaznatcheev

9

Aquí hay un intento de crear una función artificial con la siguiente propiedad:

El problema se puede resolver con consultas , pero requiere tiempo . $O(\log n)$ $\exp(n)$
El problema puede ser resuelto con tiempo, sino que requiere consultas $O(n)$ $O(n)$

Deje que el tamaño de entrada sea . Deje que los primeros bits (llamemos a esta cadena x) codifiquen la entrada a un problema completo para EEXP. Los siguientes bits (llamemos a esta cadena y) tienen la propiedad de que todos son cero si y solo si x es una instancia NO del problema EEXP-complete. $n + \log n$ $\log n$ $n$

En palabras, los primeros bits codifican un problema difícil, y los siguientes bits le dan una pista sobre la solución del problema. Sin embargo, para encontrar la solución mirando la cadena de bits, realiza consultas . $\log n$ $n$ $n$ $\Omega(n)$

Por lo tanto, este problema se puede resolver ya sea leyendo solo los primeros bits y gastando tiempo exp (n) o leyendo bits y usando solo tiempo lineal. $\log n$ $n$

La misma función se aplica para la complejidad de la consulta cuántica ... inserte signos de raíz cuadrada donde sea necesario.

Robin Kothari
fuente

7

Una versión más extrema del ejemplo de Robin:

Deje que el tamaño de entrada sea , con los primeros bits (llame a esta cadena ) codificando una máquina Turing . Arregla alguna función . Deje que el último bit de la cadena sea si la máquina Turing detiene en menos de pasos. El problema es entonces determinar si detiene en menos de pasos y la paridad de es par. $n$ $n-1$ $x$ $T_x$ $f(n)$ $1$ $T_x$ $f(n)$ $T_x$ $f(n)$ $x$

Por lo tanto, al hacer consultas el problema se puede resolver en el tiempo , mientras que al hacer consultas, el problema se puede resolver en el tiempo . $n-1$ $O(f(n))$ $n$ $O(n)$

Joe Fitzsimons
fuente

Probablemente haya querido decir que el último bit sea tal que la paridad de x sea incluso si la máquina de Turing se detiene a tiempo (de lo contrario, la pregunta solo requiere una consulta;)). Esto es bueno y puede modificarse para dar cualquier tipo de separación que queramos entre tiempo y consulta. Considere cualquier función y , luego deje que los primeros bits de sean una descripción de una máquina de torneado. Supongamos que la otra de bits es tal que la paridad de es incluso si detiene en menos de pasos. Luego tenemos una versus consultas a costa de

g (n) = ω (1)

$g(n) = \omega(1)$

g (n) < n

$g(n) < n$

g (n)

$g(n)$

x

$x$

n - g (n)

$n - g(n)$

x

$x$

x

$x$

T_{x}

$T_x$

f (n) > n

$f(n) > n$

g (n)

$g(n)$

n

$n$

Θ (f (n))

$\Theta(f(n))$ versus en el tiempo.

n

$n$

Artem Kaznatcheev

Haga caso omiso de la primera oración de mi comentario anterior.

Artem Kaznatcheev

7

Me gusta la respuesta de Robin Kothari y la modificación de Joe Fitzsimons. En una extensión obvia de sus respuestas, pueden lograr cualquier relación de separación (excepto constante frente a no constante) entre la complejidad de consulta cada vez más pequeña y la complejidad de tiempo cada vez más grande. Sin embargo, no hay una manera obvia de hacer que sus funciones no sean parciales. Quiero señalar un problema natural en el que tenemos una separación y mostrar que las grandes separaciones son más difíciles para las funciones totales.

Un problema natural

Ben Reichardt señaló por correo electrónico el problema de evaluación de fórmulas. La complejidad de la consulta cuántica para evaluar una fórmula general AND-OR de lectura única en variables es . Sin embargo, el algoritmo de consulta no es eficiente en el tiempo. Aquí , se muestra que el algoritmo más rápido conocido hace consultas y se ejecuta a tiempo poliligáríticamente peor. Por lo tanto, tenemos un problema total natural donde hay una separación conocida. Aunque no hay pruebas de que esta separación tenga que existir. $n$ $\Theta(\sqrt{n})$ $O(\sqrt{n})$ $O(\sqrt{n}\log{n})$

¿Las funciones totales son más difíciles de separar?

Para mí, parece que es más difícil encontrar funciones totales con separaciones comprobables. Para mostrar que el caso de las funciones totales y parciales es diferente, proporcionaré un argumento sobre la separación más grande entre las complejidades de consulta de los algoritmos de consulta óptima y óptima de tiempo para una función total.

Usando el límite inferior [1] de Simon podemos ver que si una función depende de de sus variables, tendremos que consultar al menos de ellas. Por otro lado, lo máximo que consultaríamos es . Tenga en cuenta que no hay ninguna razón para consultar todas las variables, porque la salida es independiente de de ellas (llame a esos bits muertos) y para una función total no se revelará ninguna estructura secreta al mirar esos bits muertos. Por lo tanto, incluso el algoritmo con el tiempo más óptimo para una función total puede modificarse para usar en la mayoría de las consultas simplemente asumiendo que los bits muertos son todos . $m$ $\Omega{(\log m)}$ $m$ $n$ $n - m$ $m$ $0$

Por lo tanto, si escribimos , entonces para una función total, dado el algoritmo óptimo de consulta con complejidad , hay un algoritmo de tiempo óptimo con complejidad con y . En otras palabras, no podemos tener más que una separación exponencial en la complejidad de la consulta entre los algoritmos de consulta óptima y la hora óptima para funciones totales. No me sorprendería si estos límites realmente flojos pudieran mejorarse. $(\text{query complexity}\; , \; \text{time complexity})$ $(q_1(n),t_1(n))$ $(q_2(n),t_2(n))$ $q_2(n) \leq f(q_1(n))$ $f(n) = O(2^n)$

[1] HU Simon, "Un apretado Z (loglogn) enlazado en el tiempo para RAM paralelas para calcular funciones booleanas no degeneradas", en: Symp. sobre Fundamentos de la teoría de la computación, Lecture Notes in Computer Science, vol. 158, Springer, Berlín, 1983, págs. 439–444.

Artem Kaznatcheev
fuente

Compensación entre tiempo y complejidad de consulta

Respuestas:

Un problema natural

¿Las funciones totales son más difíciles de separar?