Me gustaría verificar el estado del límite inferior del espacio para resolver el problema de conectividad en la transmisión en pases. El se indicó en la literatura, pero parece ser por un problema ligeramente diferente. ¿Me he perdido algo? Detalles abajo. Ω ( n / p )
Dado un gráfico de vértices en una secuencia (los bordes se presentan uno por uno de manera continua), queremos verificar si está conectado. ¿Cuál es el espacio mínimo que necesita un algoritmo para resolver este problema cuando se le permite leer la secuencia de pases?n G p
Feigenbaum y col . mostró el espacio para algoritmos de una pasada para una clase de problemas que incluye este problema (consulte la Sección 5.1) y afirmó que Henzinger et al probaron el límite inferior del espacio para la conectividad . . Sin embargo, el único límite inferior para el problema de la "conectividad" es en realidad para los " - conectividad" problema: dado vértices y , queremos comprobar si y estamos en la misma componente conexa (Teorema 6). La prueba de esto no se puede usar para el problema de conectividad, ya que puede haber muchos vértices incidentes sin borde.Ω ( n / p ) s t s t s t
Entonces, mi pregunta es, para la versión específica de conectividad que dije, ¿hay algún límite inferior conocido para la secuencia -pass?
Un límite inferior mejor cuandop=1 es bits, donde . (El término se puede hacer arbitrariamente cerca de para suficientemente grande , y asintóticamente es .)nlogn−n(loglogn+3/2) log=log2 3/2 1 n logloge−loge≈0.91
También se puede aplicar una reducción directa de un juego de comunicación de conectividad gráfica para obtener un límite inferior menos explícito . Sin embargo, dado que el factor constante implícito se relaciona con el número de bloques garantizados por el Lema de regularidad de Szemerédi , parece ser tan pequeño que resulta inútil para las aplicaciones.Ω(nlogn)
Entonces, un límite inferior más preciso para el caso -pass es . No estoy convencido de que este sea el límite inferior verdadero, ya que lograr ese límite parece poco probable : la verdadera dependencia de parece ser más débil que una proporción inversa. Sin embargo, el límite debe ser al menos , mejorando .p 1p(nlogn−n(loglogn+3/2)) p Ω(n/p)Ω(1pnlogn) Ω(n/p)
fuente