O Tempo Exponencial Simétrico Requer Tamanho de Circuito Quase Máximo: Simplificado, Verdadeiramente Uniforme

Em uma recente descoberta, Chen, Hirahara e Ren provam que S2E/1 ⊄SIZE2n/n ao fornecer um algoritmo FS2P de valor único para o Problema de Evitação de Intervalo (Avoid) que funciona para infinitamente muitos tamanhos de entrada n. Baseando-se em seu trabalho, apresentamos um algoritmo FS2P de valor único simples para Avoid que funciona para todos os tamanhos de entrada n. Como resultado, obtemos o limite inferior de circuito S2E ⊄i.o.-SIZE2n/n e muitos outros corolários: 1. Limite inferior de circuito quase em toda parte para Σ2E ∩ Π2E e ZPENP. 2. Construções FZPPNP pseudodeterminísticas para objetos combinatórios como: grafos de Ramsey, matrizes rígidas, geradores pseudorrandômicos, extratores de duas fontes, códigos lineares, tabelas da verdade difíceis e cadeias Kpoly-randômicas.