Problemas para reducir y probar un límite inferior

¿Cuáles son los problemas estándar que podemos reducir para probar los límites inferiores de ? $\Omega(n\log n)$

Por supuesto, otros problemas de estado además de la clasificación y la distinción de elementos.

cc.complexity-theory lower-bounds Vinayak Pathak
fuente

¿En qué modelo computacional?

MCH

Buen punto. Me refería al modelo basado en la comparación.

Vinayak Pathak

Respuestas:

$\Omega(n\log n)$

$n$
$n$
$n$
$n$
Inclusión de conjuntos: dados dos conjuntos de números reales, ¿uno es un subconjunto del otro?
$[n]$

Los primeros tres son los más utilizados en geometría computacional.

Jeffε
fuente

aparte irrelevante: los primeros tres son también los problemas canónicos difíciles para los límites inferiores del algoritmo de flujo basado en la complejidad de la comunicación.

Suresh Venkat

@SureshVenkat: he visto que se utiliza la disjunción y la igualdad de conjunto para probar los límites inferiores en la transmisión. ¿Tiene un ejemplo para la distinción de elementos?

Vinayak Pathak

Al menos un lugar que vi fue en el análisis de algoritmos bajo el modelo W-stream. En general, la disfunción eréctil está estrechamente relacionada con la desunión de vector de bits (o conjunto)

Suresh Venkat