Considere o problema da estrutura de dados com possíveis actualizações provenientes de um conjunto $\mathcal D$, consultas provenientes de um conjunto $\mathcal Q$ e actualizações de casos dinâmicos provenientes de um conjunto $\mathcal U$. O estado da evolução actual para os limites inferiores da estrutura de dados é $t = \tilde\Omega(\log |\mathcal Q|)$ para problemas de estrutura de dados estáticos e $\max(t_{\mathrm q},t_{\mathrm u}) = \tilde\Omega((\log n)^2)$, onde $n = \max(|\mathcal Q|,|\mathcal U|,\log |\mathcal D|)$ para problemas dinâmicos.
Adaptámos a estrutura de prova natural de Razborov e Rudich à definição de estruturas de dados estáticas e dinâmicas no modelo de sonda celular, de uma forma que sugere fortemente que este estado de evolução dificilmente será melhorado em algum momento. Uma abordagem semelhante foi recentemente adotada por Korten, Pitassi e Impagliazzo (FOCS 2025), que analisaram os limites das estruturas de dados estáticas num regime de parâmetros diferente.
A nossa contribuição é:
Definimos noções análogas às funções pseudo-aleatórias (FPA). A estas primitivas chamamos FPAs locais, no contexto de estruturas de dados estáticas, e FPAs locais e localmente atualizadas (FLLA), no contexto de estruturas de dados dinâmicas.
Formulamos então conjeturas criptográficas, nomeadamente que FPAs locais válidas e FPAs FLLA válidas existem precisamente no limite em que já não somos capazes de provar FPAs estáticas, respetivamente, para limites inferiores de estruturas de dados. Se estas conjeturas forem verdadeiras, segue-se que o estado da evolução atual em limites inferiores de estruturas de dados não pode ser melhorado por uma prova natural.
Mostramos que (quase) todas as provas de limites inferiores de estruturas de dados conhecidas são provas naturais, através de uma análise de todos os limites inferiores da literatura (que conhecemos). (A única exceção são as demonstrações baseadas em teoremas de levantamento.)
Daqui resulta que, se a nossa conjetura criptográfica for verdadeira, então todas as técnicas de prova com limite inferior conhecidas (salvo as duas exceções) são incapazes de melhorar o estado da evolução. (Também apresentamos obstáculos às duas exceções.)
Além disso, fornecemos construções candidatas concretas para as nossas duas primitivas pseudo-aleatórias. Conjeturamos que as nossas construções são seguras para parâmetros logo acima dos limites inferiores do estado da evolução.
Mostrámos também que, sejam elas seguras ou não, as nossas PRF candidatas satisfazem, pelo menos, as propriedades naturais que aparecem em todas (exceto numa) as provas conhecidas.
Portanto, se alguém estiver interessado em melhorar o estado da evolução em limites de estruturas de dados estáticas ou dinâmicas, deve encontrar um método não natural para provar tais limites inferiores (nenhum método deste tipo existe atualmente), ou pode começar por tentar quebrar as nossas PRF candidatas.
Apresentação por: Bruno Loff (Faculdade de Ciências da Universidade de Lisboa e LASIGE)