Límites inferiores de cálculo de una función de un conjunto

Teniendo un conjunto de elementos, digamos que quiero calcular una función que es sensible a todas las partes de la entrada, es decir, depende de un miembro muy de (es decir, es posible cambiar cualquier miembro de a algo de lo contrario, para obtener una nueva entrada, st valor de en y son diferentes). $A$ $n$ $f(A)$ $A$ $A$ $A'$ $f$ $A$ $A'$

Por ejemplo, podría ser la suma o el promedio. $f$

¿Hay algún resultado que demuestre que, en algunas condiciones, el tiempo necesario para que una máquina de Turing determinista calcule será ? $f$ $\Omega(n)$

complexity-theory Виталий Олегович
fuente

Tenga en cuenta que si

es una secuencia con acceso aleatorio, y el supuesto de sensibilidad se debilita, esto no siempre se cumple. Por ejemplo,

se puede calcular con dos consultas, aunque no sea una junta.

A

$A$

(i, x_{1}, \dots, x_{n}) \to x_{i}

$(i,x_1,\dots,x_n) \to x_i$

sdcvvc

@sdcvvc tu ejemplo me recuerda la enseñanza de idiomas C V[i]. ¿Cuál es la definición de junta ?

Виталий Олегович

Una

junta es una función booleana que depende solo de

argumentos, es decir, hay un conjunto

de tamaño

tal que para cualquier

, si

difieren solo en las posiciones fuera de

, entonces

. Abuse de este término para referirme a una función que no depende de todos los argumentos.

k

$k$

k

$k$

A \subset {1, 2, \dots, n}

$A\subset\{1,2,\dots,n\}$

k

$k$

x

$x$

y

$y$

x

$x$

y

$y$

A

$A$

f (x) = f (y)

$f(x)=f(y)$

sdcvvc

Si está tratando de encontrar soporte para su respuesta al problema de distancia promedio en math.se, desafortunadamente, esto no funcionará.

Aryabhata

@Aryabhata, la primera intención fue encontrar apoyo para mi respuesta a esta pregunta: math.stackexchange.com/questions/129969/… , pero lo único que dirá este resultado es que si hay

vértices en el gráfico, el algoritmo calcular la distancia promedio será

, lo cual es bastante obvio. He eliminado mi respuesta allí, porque como escribiste no probé nada.

n

$n$

Ω (n)

$\Omega(n)$

Виталий Олегович

Respuestas:

Debe especificar el modelo de cálculo y las propiedades de . En el siguiente argumento expondré los supuestos que necesito. Puede generalizarse un poco más, pero creo que debería ser suficiente para darle la idea. $f$

Suponga que la máquina nunca lee el valor de uno de los miembros de (un conjunto fijo, y se da como una lista). Suponga además que es una entrada tal que cambiar el valor de su ésimo miembro no cambia la respuesta de Suponga además que es sensible a todas las partes de la entrada, es decir, depende del mismo miembro de (es decir, es posible cambiar cualquier miembro de a otra cosa para obtener un nuevo valor de entrada st de en y son diferentes). $M$ $A$ $A$ $A$ $i$ $M$ $f$ $A$ $A$ $A'$ $f$ $A$ $A'$

Podemos usar un argumento adverso para mostrar que la máquina no puede calcular la respuesta correcta cambiando el valor de ese miembro de para obtener contrario, el valor de es diferente. El valor de en estos dos conjuntos es el mismo, por lo que uno de ellos debe ser falso y, por lo tanto, no puede calcular correctamente. $A$ $A'$ $f$ $M$ $M$ $f$

Por lo tanto, cualquier máquina que calcule necesitará leer toda la entrada que toma pasos de . $M$ $f$ $\Omega(n)$

(Por otro lado, suponga que tenemos una máquina de acceso aleatorio no determinista, y queremos calcular OR de los bits en la entrada. Podemos adivinar un bit de manera no determinista y verificar si es 1, si es 1, sacamos 1 . Esta máquina lee solamente un único bit de la entrada en pasos y respuestas correctamente el problema. Así que sin suposiciones sobre y el resultado no se mantiene.) $O(\lg n)$ $M$ $f$

Kaveh
fuente

Lo siento, olvidé escribir que mi modelo de cálculo era la máquina determinista de Turing.

Виталий Олегович

+1 para argumentos adversarios, que es una excelente manera de comenzar a comprender los límites inferiores.

Joe