Existe algum problema não trivial na teoria dos algoritmos seriais com um limite inferior polinomial não trivial de

Na teoria dos algoritmos distribuídos, existem problemas com limites inferiores, como $\Omega(n^2)$, que são "grandes" (ou seja, maiores que $\Omega(n\log n)$) e não trivial. Gostaria de saber se existem problemas com limites semelhantes na teoria do algoritmo serial, quero dizer de ordem muito maior que$\Omega(n\log n)$.

Com trivial, quero dizer "obtido apenas considerando que devemos ler toda a entrada" e da mesma forma.

Existem tais problemas pelo teorema da hierarquia do tempo. Basta pegar qualquer problema que esteja completo para uma classe de grande complexidade. Por exemplo, considere um problema completo para$\mathsf{ExpTime}$. Esse problema será$\Omega(n^c)$ para todos $c\in\mathbb{N}$.

No entanto, observe também que, para problemas em $\mathsf{NP}$, não há limites inferiores de tempo forte no modelo de fita múltipla e a existência de algoritmos de tempo lineares para SAT é consistente com o estado atual do conhecimento. (No modelo TM de fita única, não é difícil mostrar que muitos problemas, como os palíndromos, exigem$\Omega(n^2)$ tempo, mas esses limites inferiores dependem essencialmente dos detalhes do modelo TM de fita única.)

Alguns problemas simples que têm limites mais baixos que o tamanho de suas entradas são algoritmos com tamanhos de saída maiores que seus tamanhos de entrada.

Alguns exemplos:

• O problema de listar todas as soluções para 3-SAT, ou similarmente, o problema de listar todos os ciclos hamiltonianos . Esses problemas têm um número exponencial de soluções no pior caso. Assim, eles têm um limite inferior de$\Omega (c^n),c>1$. Curiosamente, no entanto, o próprio problema 3-SAT não possui um conhecimento super-linear (maior que$\Omega (n)$) limites! Isso significa que não sabemos se é mais difícil do que linear!
• Você pode até criar novos algoritmos como este: "preenchendo um gráfico", isto é, dado $G = V,E$, Onde $E=\varnothing$e $n=|V|$, o algoritmo emitirá um gráfico $G' = V,E'$, Onde $E'=\left\{u,v|u\neq v\space\wedge\space u,v\in V \right\}$.

Além disso, você poderá compor um problema que tenha $\Omega (n^2)$de tamanho médio, com um problema que leva $\Omega (n^2)$ como entrada e saídas $\Omega (n)$ ou mesmo $\Omega (1)$de tamanho médio (por exemplo, algo que conta o número de saídas) para obter um problema que leva $\Omega(n)$de tamanho normal e saídas $\Omega (n)$de tamanho médio e, no entanto, possui um tempo de execução maior que $\Omega (n)$. No entanto, pode ser muito difícil provar (que não há atalho para obter a resposta em menos tempo).

Outra maneira pela qual alguns problemas têm limites inferiores é restringir o modelo de computação.

Embora o limite inferior do tipo de comparação não exceda $\Omega (n\log n)$, Acho que vale a pena discutir. A classificação por comparação também é um problema com um limite inferior maior que o tamanho da entrada, mas o limite inferior não excede$\Omega (n\log n)$, e em . No entanto, enquanto eu pesquisava isso, encontrei a seguinte pergunta no excesso de matemática: limites super-lineares de complexidade de tempo super-lineares para qualquer problema natural no NP . Outros exemplos listados na resposta estão bem abaixo$\Omega (n\log n)$. Penso que o essencial é que, se você restringir o modelo de computação, poderá obter limites mais baixos para problemas para os quais, de outra forma, não os temos. E se você não restringir o modelo de computação, é muito difícil provar limites mais baixos em problemas.