¿Problemas no triviales solucionables en tiempo constante?

El tiempo constante es la complejidad absoluta al final del tiempo. Uno puede preguntarse: ¿hay algo no trivial que se pueda calcular en tiempo constante? Si nos atenemos al modelo de máquina de Turing, entonces no se puede hacer mucho, ya que la respuesta solo puede depender de un segmento inicial de longitud constante de la entrada, ya que las partes más lejanas de la entrada ni siquiera se pueden alcanzar en tiempo constante.

Por otro lado, si adoptamos el modelo de RAM de costo unitario algo más poderoso (y más realista), en el que las operaciones elementales en números $O(\log n)$ -bit se cuentan como pasos individuales, entonces podremos resolver problemas no triviales tareas, incluso en tiempo constante. Aquí hay un ejemplo:

Instancia: enteros $n, k, l, d$ , cada uno dado en formato binario por $O(\log n)$ bits.

Pregunta: ¿Existe un gráfico de $n$ -vértices, de modo que su conectividad de vértice sea $k$ , su conectividad de borde sea $l$ y su grado mínimo sea $d$ ?

Tenga en cuenta que, desde la definición, ni siquiera es obvio que el problema está en NP . La razón es que el testigo natural (el gráfico) puede necesitar una descripción larga de bits, mientras que la entrada es dada solo por $\Omega(n^2)$ bits. Por otro lado, el siguiente teorema (verTeoría del gráfico extremode B. Bollobas) viene al rescate. $O(\log n)$

Teorema: Sean enteros. Existe un gráfico de -vértices con conectividad de vértice , conectividad de borde y grado mínimo , si y solo si se cumple una de las siguientes condiciones: $n, k, l, d$ $n$ $k$ $l$ $d$

, $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$
$1\leq 2d+2-n\leq k\leq l = d< n-1$
$k=l=d=n-1.$

Dado que estas condiciones se pueden verificar en tiempo constante (en el modelo de RAM de costo unitario), el Teorema conduce a un algoritmo de tiempo constante en este modelo.

Pregunta: ¿Cuáles son algunos otros ejemplos no triviales de algoritmos de tiempo constante?

cc.complexity-theory ds.algorithms time-complexity Andras Farago
fuente

¿Verifica una prueba comprobable probabilísticamente cuenta?

David Eppstein

No piense que su ejemplo es

tiempo. Su entrada tiene una longitud

, en cuyo caso la palabra RAM típica solo permitiría operaciones de

-bit en un solo paso. (La alternativa es permitir que el tamaño de las palabras sea proporcional a la longitud de entrada, pero en ese caso se pueden nombrar muchos algoritmos de "tiempo constante" ...) Podría intentar agregar una cadena de longitud

después de esos números, pero luego I no veo cómo se verificaría la comprobación de ese formato en

O (1)

$O(1)$

m = O (\log n)

$m=O(\log n)$

O (\log m)

$O(\log m)$

\geq n

$\geq n$

O (1)

$O(1)$ tiempo: parece que tiene que verificar (mediante búsqueda binaria, por ejemplo) que la longitud total de la cadena es de hecho

, lo que requiere tiempo de

Ω (\log n)

$\Omega(\log n)$

\log n

$\log n$

Ryan Williams

Creo que la sugerencia de David Eppstein apunta a una dirección más interesante: considerando algoritmos aleatorios de tiempo O (1). Al menos en ese caso, puede esperar que se acceda a cada bit de entrada en al menos una posible ejecución del algoritmo.

Ryan Williams

Un ejemplo simple de algoritmos aleatorios de tiempo O (1) es la mediana aproximada (aproximada en el sentido de que dividirá la entrada aproximadamente 50-50). Simplemente elija 1000000 elementos de la entrada de manera uniforme al azar, calcule su mediana y envíela.

Jukka Suomela

Me gusta su pregunta, pero el inconveniente de su ejemplo es que se basa en un teorema matemático. Llevando esto al límite, podría decir: Instancia Enteros positivos

. Pregunta ¿Hay un número entero

tal que

(la respuesta es Verdadero o Falso). Bueno, de hecho hay un algoritmo de tiempo constante porque la respuesta siempre es Falsa, pero claramente este no es el tipo de ejemplos que desea.

x, y, z

$x, y, z$

n > 2

$n > 2$

x^{n} + y^{n} = z^{n}

$x^n + y^n = z^n$

J.-E.

Respuestas:

El documento Algoritmos de aproximación de tiempo constante a través de mejoras locales de Nguyen y Onak ofrece muchos ejemplos de esquemas aleatorios de aproximación de tiempo constante: Coincidencia máxima (el tiempo de ejecución depende solo del grado máximo del gráfico), Fijar cobertura, etc. Los autores presentar un método para diseñar tales algoritmos.

Lamina
fuente

Existen muchos ejemplos de juegos estudiados en la teoría de juegos combinatorios donde el estado de un juego puede describirse mediante un número constante de valores enteros. Para algunos de estos, una estrategia ganadora para el juego se puede calcular en tiempo constante. Pero también plantean preguntas sobre cuál es exactamente su modelo de cálculo.

Uno de los juegos combinatorios más simples y básicos es nim: uno tiene un número constante de montones de frijoles, y en un solo movimiento puedes eliminar cualquier número de frijoles de un montón, ya sea ganando o perdiendo (según las reglas que elijas) Si tomas el último frijol. La estrategia óptima se puede calcular en tiempo constante si permite operaciones booleanas xor bit a bit (es decir, el operador ^ en lenguajes de programación como C / C ++ / Java / etc.) ¿Es este un algoritmo de tiempo constante en su modelo?

Aquí hay uno donde se sabe que existe un algoritmo determinista exacto de tiempo constante (en un modelo de cómputo extendido posiblemente no realista que le permite probar la primalidad de un número en tiempo constante) pero no se sabe qué es ese algoritmo: dado un comienzo moverse en el juego de monedas de Sylver , determinar si es un movimiento ganador o perdedor. Se proporciona un diagrama de flujo para este problema en Berlecamp, Conway y Guy, Winning Ways , pero depende de un conjunto finito de contraejemplos para una caracterización general de los movimientos ganadores, y no se sabe cuál es ese conjunto (o incluso si es vacío).

Otro ejemplo interesante de la teoría de juegos combinatorios es el juego de Wythoff. Cada posición del juego puede describirse mediante un par de enteros (es decir, espacio constante, en su modelo de cálculo), los movimientos en el juego implican reducir uno de estos dos enteros a un valor menor, y la estrategia ganadora implica moverse a una posición donde La proporción entre estos dos enteros es lo más cercana posible a la proporción áurea. Pero en muchas posiciones de juego hay una opción: puedes reducir el mayor de los dos enteros hasta el punto donde es (casi) el entero más pequeño multiplicado por la proporción áurea, o el entero más pequeño dividido por la proporción áurea. Solo una de estas dos opciones será una jugada ganadora. Entonces, la estrategia óptima se puede definir en términos de un número constante de operaciones aritméticas, pero estas operaciones implican un número irracional, la proporción áurea. ¿Es ese un algoritmo de tiempo constante en su modelo? Talves esto' $n$ $\log n$

David Eppstein
fuente

Gracias, todos estos son ejemplos interesantes. También arrojan luz sobre el hecho de que el concepto de "tiempo constante" es menos claro de lo que originalmente pensé ...

Andras Farago

$|G|$ $G$ $p$ $m$ $m$ $|G|$ $G$ $p$ $m$ $G$ $|G|$ $m$ $m$ $m$

orgesleka
fuente