É realmente possível provar limites mais baixos?

Dado qualquer problema computacional, a tarefa de encontrar limites mais baixos para esse cálculo é realmente possível? Suponho que tudo se resume a como um único passo computacional é definido e qual modelo usamos para a prova, mas, dado que, realmente provamos um limite inferior ao geral? O que quero dizer é que podemos provar algo como "o problema $X$ não pode ser resolvido mais rápido que o tempo $t(X)$ " em vez de "o problema $X$ pode ser resolvido em um tempo $t(X)$ ou mais rápido"?

Tentei encontrar informações especificamente sobre os limites inferiores e as provas deles, mas não consigo encontrar nenhum interesse, alguma recomendação sobre livros / documentos / sites sobre o assunto?

Podemos provar absolutamente essas coisas.

Muitos problemas têm limites inferiores triviais, como encontrar o mínimo de um conjunto de números (que não são classificados / estruturados de forma alguma) leva pelo menos Ω ( n ) tempo. A prova disso é simples: um algoritmo hipotético que é executado em o ( n ) tempo não pode examinar todos os números na entrada. Portanto, se rodássemos o algoritmo em alguma entrada, poderíamos observar que ele nunca examinou um elemento específico da entrada. Alterando esse elemento ao mínimo, podemos fazer com que o algoritmo falhe.$n$$\Omega(n)$$o(n)$

Um limite inferior menos trivial é o limite inferior de para classificação no modelo baseado em comparação. A prova disso segue as seguintes linhas: dada uma entrada de n números, existem n ! saídas possíveis (a entrada pode ser qualquer permutação da lista classificada, portanto, a saída também pode ser qualquer permutação da entrada). Se estamos limitados a fazer apenas comparações, nosso algoritmo (em média) precisa executar pelo menos o log 2 ( $\Omega(n \log n)$$n$$n!$comparações de ! ) = Ω ( n log n ) para poder fornecer$\log_2(n!)=\Omega(n \log n)$saídas diferentes.$n!$

Limites inferiores podem ser ainda mais fortes. Existem vários problemas (principalmente o -Hard problemas) para o qual existe um limite inferior exponencial. Os problemas desta classe incluem o cálculo de estratégias ideais para jogos como xadrez (generalizado), damas e jogar. A prova disso é através doTeorema da Hierarquia de Tempo, que declara (sujeito a algumas restrições em f ):$EXPTIME$$f$

Dada uma função , existe um problema computacional que pode ser resolvido no tempo O ( f ( n ) $f$$O(f(n))$ mas não pode ser resolvido no tempo .$o(\frac{f(n)}{\log n})$

Então, basicamente, se você consegue pensar em uma função , existe um problema que requer muito tempo para ser resolvido.$f$

Finalmente, outra via de não necessariamente provar um limite de tempo mais baixo, mas algo ainda mais forte está mostrando a indecidibilidade de um problema (por exemplo, parada, pós-correspondência).

Sim é possivel. O exemplo clássico é o fato de que qualquer algoritmo de classificação baseado em comparação requer $\Omega(n\log n)$ para classificar uma lista de comprimento .$n$

No entanto, limites inferiores parecem ser muito mais difíceis de provar do que limites superiores. Para provar que existe um algoritmo de classificação que requer comparações , você só precisa exibir esse algoritmo (classificação por mesclagem - voila !). Mas para um limite inferior, você precisa mostrar de alguma forma que nenhum algoritmo em uma classe específica pode resolver seu problema. A dificuldade de fazer isso é ilustrada pelo fato de sabermos apenas que L ⊆ N L ⊆ P ⊆ N P ⊆ P $O(n\log n)$ mesmo sabendo que pelo menos uma dessas inclusões é estrita ( L ⊂ P S P A C E pelo teorema da hierarquia espacial) e a maioria das pessoas pensa quetodassãoestritas.

Por outro lado, Ryan Williams tem um bom artigo (e conversas, que ouvi algumas vezes) chamado Algoritmos para circuitos e Circuitos para algoritmos , nos quais ele argumenta que encontrar limites mais baixos e encontrar algoritmos não são fundamentalmente todos. tão diferente. Por exemplo, ele cita a prova da indecidibilidade do problema de parada como um exemplo de um algoritmo (a máquina de Turing universal) sendo usado exatamente para provar um limite inferior (indecidibilidade).

$n$

No entanto, há um ponto na pergunta que exige mais observações sobre o limite inferior (ou os limites de complexidade em geral).

Na verdade, a escolha do que é uma única etapa computacional é irrelevante, desde que as etapas computacionais possam ser consideradas como tendo um limite superior constante (e limite inferior). O resultado da complexidade será o mesmo, pois é definido até uma constante. Tomar 3 comparações como operações unitárias, ou apenas uma única, não faz diferença.

O mesmo se aplica ao tamanho dos dados que servem de referência para avaliar o custo da computação. Tomar um único inteiro ou dois inteiros como unidade de tamanho não faz diferença.

No entanto, as duas opções devem estar relacionadas.

$n$$\log n$$O(\log n)$

Se uma operação pode ser considerada com custo unitário está fortemente relacionada a quais dados podem ser considerados com tamanho unitário. E isso depende do nível de abstração que você escolher para o seu modelo de computação.