Complexidade computacional – Wikipédia  a enciclopédia livre
10 pág.

Complexidade computacional – Wikipédia a enciclopédia livre


DisciplinaAlgoritmos14.809 materiais172.680 seguidores
Pré-visualização6 páginas
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(n ) 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).
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).
No entanto, provar limites inferiores é muito mais difícil, uma vez que limites inferiores fazem uma declaração sobre todos os possíveis
algoritmos que resolvem um determinado problema. A frase "todos os algoritmos possíveis" inclui não apenas os algoritmos conhecidos hoje,
mas qualquer algoritmo que possa ser descoberto no futuro. Para mostrar um limite inferior de T(n) para um problema requer mostrar que
nenhum algoritmo pode ter complexidade de tempo menor do que T(n).
Limites superiores e inferiores são geralmente indicados usando a notação O-grande, que desconsidera fatores constantes e termos menores.
Isso faz com que os limites independam dos detalhes específicos do modelo computacional utilizado. Por exemplo, T(n) = 7n + 15n + 40,
em notação O-grande seria escrito da seguinte forma T(n) = O(n ).
Classes de complexidade
Definição de classes de complexidade
Uma classe de complexidade é um conjunto de problemas de complexidade relacionados. As classes mais simples de complexidade são
definidas pelos seguintes fatores:
O tipo de problema computacional: Os problemas mais comumente utilizados são problemas de decisão. No entanto, classes de
complexidade podem ser definidas com base em problemas de função, problemas de contagem, problemas de otimização, problemas
de promessa, etc.
O modelo de computação: O modelo mais comum de computação é a máquina de Turing determinística, mas muitas classes de
complexidade são baseadas em máquinas de Turing não-determinísticas, circuitos Booleanos, máquinas de Turing quânticas, circuitos
monótonos, etc.
O recurso (ou recursos) que está sendo limitado e os limites: Essas duas propriedades são geralmente declaradas em conjunto, tais
como "tempo polinomial", "espaço logarítmico", "profundidade constante", etc.
2
2
2
Uma representação da relação entre as classes de
complexidade
É claro, algumas classes de complexidade têm definições complexas que não se encaixam nesse quadro. Assim, uma classe de complexidade
típica tem uma definição como a seguinte:
O conjunto de problemas de decisão solúveis por uma máquina de Turing determinística dentro do tempo f(n). (Esta classe de
complexidade é conhecida como DTIME(f(n))).
Mas limitar o tempo de computação acima por alguma função concreta f(n) muitas vezes produz classes de complexidade que dependem do
modelo da máquina escolhida. Por exemplo, a linguagem {xx | x é uma sequência binária qualquer} pode ser resolvida em tempo linear em
uma máquina de Turing multi-fitas, mas necessariamente exige tempo quadrático no modelo de máquinas de Turing single-fita. Se permitirmos
variações no tempo polinomial em execução, a tese de Cobham-Edmonds afirma que "as complexidades do tempo em quaisquer dois
modelos razoáveis e gerais de computação são polinomialmente relacionados" (Goldreich 2008, Chapter 1.2). Isto forma a base para a
classe de complexidade P, que é o conjunto de problemas de decisão solúveis por uma máquina de Turing determinística dentro do tempo
polinomial. O conjunto correspondente de problemas de função é FP.
Importantes classes de complexidade
Muitas classes de complexidade importantes podem ser definidas por limitando o
tempo ou espaço usado pelo algoritmo. Algumas importantes classes de
complexidade de problemas de decisão definidas desta maneira são as seguintes:
Classe de
complexidade
Modelo de computação
Limitação de
recursos
DTIME(f(n)) Máquina de Turing Determinística Tempo f(n)
P Máquina de Turing Determinística Tempo poly(n)
EXPTIME Máquina de Turing Determinística Tempo 2
NTIME(f(n))
Máquina de Turing Não-
Determinística
Tempo f(n)
NP
Máquina de Turing Não-
Determinística
Time poly(n)
NEXPTIME
Máquina de Turing Não-
Determinística
Tempo 2
DSPACE(f(n)) Máquina de Turing Determinística Espaço f(n)
L Máquina de Turing Determinística Espaço O(log n)
PSPACE Máquina de Turing Determinística Espaço poly(n)
EXPSPACE Máquina de Turing Determinística Espaço 2
NSPACE(f(n))
Máquina de Turing Não-
Determinística
Espaço f(n)
NL
Máquina de Turing Não-
Determinística
Espaço O(log n)
NPSPACE
Máquina de Turing Não-
Determinística
Espaço poly(n)
NEXPSPACE
Máquina de Turing Não-
Determinística
Espaço 2
Acontece que PSPACE = NPSPACE e EXPSPACE = NEXPSPACE pelo teorema de Savitch.
Outras classes de complexidade importantes incluem BPP, ZPP e RP, que são definidas usando máquinas de Turing probabilística; AC e
NC, que são definidas usando circuitos booleanos e BQP e QMA, que são definidas usando máquinas de Turing quânticas. #P é uma
importante classe complexidade de problemas de contagem (que não são problemas de decisão). Classes como IP e AM são definidas
usando sistemas de prova interativa. ALL é a classe de todos os problemas de decisão.
Teoremas de hierarquia
Para as classes de complexidade definidas desta forma, é desejável provar que relaxar os requisitos em função (digamos) do tempo de
computação realmente define um conjunto maior de problemas. Em particular, embora DTIME(n) esteja contido em DTIME(n ), seria
interessante saber se a inclusão é estrita. Para requisitos de tempo e de espaço, a resposta a tais perguntas é dada pelo teorema de
hierarquia para a complexidade de tempo e pelo teorema de hierarquia para a complexidade de espaço, respectivamente. Eles são
chamados teoremas de hierarquia porque induzem uma hierarquia adequada sobre as classes definidas, restringindo os respectivos recursos.
poly(n)
poly(n)
poly(n)
poly(n)
2
Diagrama de classes de complexidade
assumindo que P \u2260 NP. A existência de
problemas em NP fora tanto de P quanto
de NP-completo, neste caso, foi
estabelecida por Ladner.
Assim, existem pares de classes de complexidade tal que uma está propriamente contida na outra. Depois de ter deduzido assim as relações
de pertinência estrita de conjuntos, podemos continuar a fazer declarações quantitativas sobre quanto mais tempo adicional ou espaço é
necessário para aumentar o número de problemas que podem ser resolvidos.
Mais precisamente, o teorema de hierarquia de tempo afirma que:
.
O teorema de hierarquia de espaço afirma que:
.
Os teoremas de hierarquia de tempo e de espaço formam a base para a maioria dos resultados de separação de classes de complexidade.
Por exemplo, o teorema da hierarquia de tempo nos diz que P está estritamente contida em EXPTIME, e o teorema hierarquia do espaço
nos diz que L está estritamente contida em PSPACE.
Redução
Muitas classes de complexidade são definidas usando o conceito de redução. Uma redução é uma transformação de um problema em outro
problema. Ela captura a noção informal de um problema que seja pelo menos tão difícil quanto outro problema. Por exemplo, se um
problema X pode ser resolvido usando um algoritmo para Y, X não é mais difícil do que Y, e dizemos que X se reduz a Y. Existem muitos
tipos diferentes