Complexidade computacional

Complexidade computacional

1. Instâncias

   • Ao considerar problemas computacionais, uma instância de problema é uma cadeia sobre um alfabeto. Normalmente, o alfabeto é considerado como sendo o alfabeto binário (ou seja, o conjunto {0,1}), e, assim, as cadeias são bitstrings.

2. Problemas de decisão como linguagens formais

   • Problemas de decisão são um dos objetos de estudo centrais na teoria da complexidade computacional. Um problema de decisão é um tipo especial de problema computacional cuja resposta é sim ou não, ou alternativamente 1 ou 0. Um problema de decisão pode ser visto como uma linguagem formal, onde os membros da linguagem são instâncias cuja resposta é sim, e os não membros da linguagem são aquelas instâncias cuja saída é não.

3. Problemas de função

   • Um problema de função é um problema computacional, onde uma única saída (de uma função total) é esperada para cada entrada, mas a saída é mais complexa do que a de um problema de decisão, isto é, não é apenas sim ou não. Exemplos notáveis incluem o problema do caixeiro viajante e o problema de fatoração de inteiros.

4. Medição do tamanho de uma instância

   • Para medir a dificuldade de resolver um problema computacional, pode-se desejar ver quanto tempo o melhor algoritmo necessita para resolver o problema. No entanto, o tempo de execução pode, em geral, depender da instância. Em particular, instâncias maiores exigirão mais tempo para resolver. Assim, o tempo necessário para resolver um problema (ou o espaço necessário, ou qualquer outra medida de complexidade) é calculado em função do tamanho da instância

5. Máquina de Turing

   • Muitos tipos de máquinas de Turing são usados para definir as classes de complexidade, tais como máquinas de Turing determinísticas, máquinas de Turing probabilísticas, máquinas de Turing não-determinísticas, máquinas de Turing quânticas, máquinas de Turing simétricas e máquinas de Turing alternadas. Todas elas são igualmente poderosas, em princípio, mas quando os recursos (tais como tempo e espaço) são limitados, algumas destas podem ser mais poderosas do que outras.
   • Uma máquina de Turing determinística é a máquina de Turing do tipo mais básico, que utiliza um conjunto fixo de regras para determinar suas ações futuras. Uma máquina de Turing probabilística é uma máquina de Turing determinística com um suprimento extra de bits aleatórios. A capacidade de tomar decisões probabilísticas muitas vezes ajuda algoritmos a resolverem problemas de forma mais eficiente

6. Medidas de complexidade

   • O melhor, o pior e o caso médio de complexidade referem-se a três maneiras diferentes de medir a complexidade de tempo (ou qualquer outra medida de complexidade) de entradas diferentes do mesmo tamanho. Uma vez que algumas entradas de tamanho n podem ser mais rápidas para resolver do que outras, definimos as seguintes complexidades:
   • Complexidade no melhor caso:
     • Esta é a complexidade de resolver o problema para a melhor entrada de tamanho n.
   • Por exemplo, considere o algoritmo de ordenação quicksort. Isso resolve o problema de ordenar uma lista de inteiros que é dada como entrada. O pior caso é quando a entrada já está ordenada ou está em ordem inversa, e o algoritmo leva tempo O(n2) para este caso. Se assumirmos que todas as permutações possíveis da lista de entrada são igualmente prováveis, o tempo médio necessário para a ordenação é O(n log n). O melhor caso ocorre quando cada pivô divide a lista pela metade, também precisando tempo O(n log n).

7. Limites superior e inferior da complexidade dos problemas

   • Para classificar o tempo de computação (ou recursos semelhantes, como o consumo de espaço), é necessário provar os limites superiores e inferiores sobre a quantidade mínima de tempo exigida pelo algoritmo mais eficiente para resolver um determinado problema. A complexidade de um algoritmo é geralmente entendida como a sua complexidade de pior caso, a menos que seja especificado o contrário. A análise de um determinado algoritmo cai sob o campo de análise de algoritmos. Para mostrar um limite superior T(n) sobre a complexidade de tempo de um problema, é necessário mostrar apenas que há um determinado algoritmo com tempo de funcionamento, no máximo, T(n)

8. Intratabilidade

   • Problemas que podem ser resolvidos na teoria (por exemplo, dado um tempo infinito), mas que na prática levam muito tempo para as suas soluções sejam úteis, são conhecidos como problemas intratáveis.[11] Na teoria da complexidade, os problemas que não apresentam soluções em tempo polinomial são considerados intratáveis por mais pequenas que sejam suas entradas. Na verdade, a tese de Cobham-Edmonds afirma que apenas os problemas que podem ser resolvidos em tempo polinomial podem ser computados de maneira factível por algum dispositivo computacional.

9. Complexidade contínua

   • A teoria da complexidade contínua pode se referir à teoria da complexidade dos problemas que envolvem funções contínuas que são aproximadas por discretizações, como estudado em análise numérica. Uma abordagem para a teoria da complexidade da análise numérica [12] é a complexidade baseada em informação (IBC).