Complexidade de caso médio

Em teoria de complexidade computacional, a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (tipicamente tempo) utilizado pelo algoritmo, numa média sobre todas as entradas possíveis. É frequentemente contrastada com a complexidade de pior caso que considera a complexidade máxima do algoritmo sobre todas as entradas possíveis.

Existem três motivações principais para estudar a complexidade de caso médio. Primeiramente, apesar de alguns problemas serem intratáveis no pior caso, as entradas que elicitam esse comportamento podem raramente ocorrer na prática, e portanto a complexidade de caso médio pode ser uma medida mais precisa da performance de um algoritmo. Segundo, a análise de complexidade de caso médio fornece ferramentas e técnicas para gerar instâncias difíceis de problemas que podem ser utilizadas em áreas como criptografia e probabilidade algorítmica. Terceiro, complexidade de caso médio permite diferenciar o algoritmo mais eficiente na prática entre algoritmos equivalentes em complexidade (por exemplo, quicksort).

A análise de caso médio requer uma noção de uma entrada "média" para um algoritmo, o que leva ao problema de conceber uma distribuição de probabilidade sobre as entradas. Alternativamente, um algoritmo probabilístico pode ser usado. A análise de tais algoritmos leva à noção relacionada de uma complexidade esperada.

História

A performance de caso médio de algoritmos tem sido estudada desde que noções modernas de eficiência computacional foram desenvolvidas nos anos 50. A maioria desse trabalho inicial focou em problemas para os quais algoritmos de tempo polinomial de pior caso já eram conhecidos. Em 1973, Donald Knuth publicou o volume 3 de The Art of Computer Programming que inspecionava de modo extenso a performance de caso médio de algoritmos para problemas solucionáveis em tempo polinomial de pior caso, tais como ordenação e descoberta da mediana.

Um algoritmo eficiente para problemas NP-completos é geralmente caracterizado como um que é executado em tempo polinomial para todas as entradas; isso é equivalente à exigir complexidade de pior caso eficiente. Porém, um algoritmo que é ineficiente em um número "pequeno" de entradas ainda pode ser eficiente para a "maioria" das entradas que ocorrem na prática. Portanto, é desejável estudar as propriedades destes algoritmos onde a complexidade de caso médio pode diferenciar da complexidade de pior caso e encontrar métodos para relacionar ambos.

As noções fundamentais de complexidade de caso médio foram desenvolvidas por Leonid Levin em 1986, quando ele publicou um artigo de uma página definindo a complexidade e completude do caso médio enquanto dava um exemplo de um problema completo para distNP, a analogia de caso médio para NP.

Complexidade de caso médio eficiente

A primeira tarefa é definir precisamente o que se quer dizer por um algoritmo eficiente "na média". Uma tentativa inicial pode definir um algoritmo eficiente de caso médio como um que é executado num tempo polinomial esperado sobre todas as entradas principais. Tal definição possui várias desvantagens: em particular, não é robusta à mudanças ao modelo computacional. Por exemplo, suponha que o algoritmo A é executado em tempo t_A(x) com a entrada x e o algoritmo B é executado em tempo t_A(x)² com a entrada x; isto é, B é quadraticamente mais lento que A. Intuitivamente, qualquer definição de eficiência de caso médio deve capturar a ideia de que A é eficiente na média se e somente se B é eficiente na média. No entanto, suponha que as entradas são extraídas aleatoriamente da distribuição uniforme de palavras de tamanho n, e que A é executado em tempo n² em todas as entradas, exceto a palavra 1ⁿ, para a qual A leva um tempo de 2ⁿ. Então, é facilmente verificável que o tempo de execução esperado de A é polinomial mas que o tempo esperado de B é exponencial.

Para criar uma definição mais robusta de eficiência de caso médio, faz sentido permitir um algoritmo A executar em tempo maior que polinomial em algumas entradas, mas a fração de entradas nas quais A requer tempo de execução cada vez maior vai se tornando cada vez menor. Essa intuição é capturada na seguinte fórmula para tempo de execução polinomial médio, que equilibra o trade-off polinomial entre tempo de execução e fração de entradas:

$\Pr _{x\in _{R}D_{n}}[t_{A}(x)\geq t]\leq {\frac {p(n)}{t^{\epsilon }}}$

para todo n, t, ε > 0 e p polinomial, onde t_A(x) denota o tempo de execução do algoritmo A na entrada x. Alternativamente, isto pode escrito como

$E_{x\in _{R}D_{n}}[{\frac {t_{A}(x)^{\epsilon }}{n}}]\leq C$

para alguma constante C, onde n = |x|. Em outras palavras, um algoritmo A tem uma boa complexidade de caso médio is, após ser executado por t_A(n) passos, A consegue resolver todas, exceto uma fração ${\frac {n^{c}}{(t_{A}(n))^{\epsilon }}}$ de entradas de tamanho n, para algum ε, c > 0.

Problema distribucional

O próximo passo é definir a entrada "média" para um problema particular. Consegue-se isto ao associar as entradas de cada problema com uma distribuição de probabilidade particular. Isto significa que um problema de "caso médio" consiste de uma linguagem L e uma distribuição de probabilidade D, que forma o par (L, D). As duas classes mais comuns de distribuições permitidas são:

1. Distribuições computáveis em tempo polinomial (P-computável): estas são distribuições para as quais é possível computar a densidade acumulada de uma dada entrada qualquer x. Mais formalmente, dada uma distribuição probabilística μ e uma palavra x ∈ {0, 1}ⁿ é possível computar o valor $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ em tempo polinomial.
2. Distribuições amostráveis em tempo polinomial (P-amostrável): estas são distribuições das quais é possível extrair amostras aleatórias em tempo polinomial. Isso implica que Pr[x] também é computável em tempo polinomial.

Estas duas formulações, apesar de similares, não são equivalentes. Se uma distribuição é P-computável, também é P-amostrável, mas o inverso não é verdadeiro se P ≠ P^#P.

AvgP and distNP

Um problema distribucional (L, D) está na classe de complexidade AvgP se existir um algoritmo eficiente de caso médio para L, como definido acima. A classe AvgP é ocasionalmente chamada de distP na literatura.

Um problema distribucional (L, D) está na classe de complexidade distNP se L está em NP e D é P-computável. Quando L está em NP e D é P-amostrável, (L, D) pertence à sampNP.

Juntas, AvgP e distNP define as analogias de caso médio à P e NP, respectivamente.

Reduções entre problemas distribucionais

Sejam (L, D) e (L', D') dois problemas distribucionais. (L, D) se reduz por caso médio à (L', D') (escrito como (L, D) ≤_AvgP (L', D')) se existir uma função f tal que, para todo n e sobre uma entrada x, pode ser computada em tempo polinomial em n e

1. (Corretude) x ∈ L se e somente se f(x) ∈ à L'
2. (Dominação) Existem polinomiais p e m tais que, para todo n e y, $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

A condição de dominação reforça a ideia de que se o problema (L, D) é difícil na média, então (L', D') também é difícil na média. Intuitivamente, uma redução deve fornecer uma maneira de resolver uma instância x do problema L ao computar f(x) e alimentar a saída ao algoritmo que resolve L'. Sem a condição de dominação, isso pode não ser possível, já que o algoritmo que resolve L em tempo polinomial em média pode levar um tempo superpolinomial em um número pequeno de entradas, mas f pode mapear tais entradas a um conjunto muito maior de D' de modo que o algoritmo A' não consiga ser executado em tempo polinomial, em média. A condição de dominação permite apenas que tais palavras ocorram polinomialmente com tanta frequência quanto em D'.

Problemas distNP-completos

O análogo de caso médio à NP-completude é a distNP=completude. Um problema distribucional (L', D') é distNP-completo se (L', D') está em distNP e para todo (L, D) em distNP, (L, D) é redutível por caso médio à (L', D').

Um exemplo de um problema distNP-completo é o Problema da Parada Limitado, BH, definido como:

BH = {(M,x,1^t) : M é uma máquina de Turing não-determística que aceita x em ≤ t passos}

Em seu artigo original, Levin mostrou um exemplo de um problema de preenchimento de ladrilhos que é NP-completo em caso médio. Uma pesquisa de problemas distNP-completos está disponível online.

Uma área de pesquisa ativa envolve encontrar novos problemas distNP completos. Entretanto, encontrar tais problemas pode ser complicado devido a um resultado de Gurevich que mostra que qualquer problema distribucional com uma distribuição plana não pode ser distNP-completo a menos que EXP = NEXP.. (Uma distribuição plana μ é uma em que existe um ε > 0 tal que para qualquer x, μ(x) ≤ 2^-|x|ε.) Um resultado de Livne mostra que todos os problemas NP naturais possuem versões distNP-completos. Entretanto, o objetivo de achar um problema distribucional natural que é distNP-completo ainda não foi alcançado.

Aplicações

Algoritmos de ordenação

Como mencionado acima, grande parte dos trabalhos iniciais relacionados à complexidade de caso médio focou em problemas para os quais algoritmos de tempo polinomial já existiam, tais como ordenação. Por exemplo, muitos algoritmos de ordenação que utilizam aleatoriedade, como quicksort, tem um tempo de execução de pior caso de O(nlog(n)), onde n é o tamanho da entrada a ser ordenada.

Criptografia

Para a maioria dos problemas, a análise de complexidade de caso médio é empreendida para encontrar algoritmos eficientes para um problema que é considerado difícil no pior caso. Em aplicações criptográficas, entretanto, o oposto é verdadeiro: a complexidade de pior caso é irrelevante; ao invés disso, queremos uma garantia de que a complexidade de caso médio de todo algoritmo que "quebra" o esquema criptográfico é ineficiente.

Portanto, todo esquema criptográfico seguro confiam na existência de funções de mão única. Apesar da existência de funções de mão única ainda é um problema em aberto, muitas candidatas à funções de mão única são baseadas em problemas NP-difíceis, tais como fatoração de inteiros ou computar o logaritmo discreto. Note que não é desejável a função candidata ser NP-completa já que isso iria apenas garantir que é improvável existir um algoritmo eficiente pata solucionar o problema no poir caso; o que na verdade queremos é uma garantia de que nenhum algoritmo eficiente possa resolver o problema sobre entradas aleatórias (ex. o caso médio). Na verdade, tanto a fatorização de inteiros quanto o logaritmo discreto estão em NP ∩ Co-NP, e portanto acredita-se que não são NP-completos. O fato de que toda a criptografia é predicada na existência de problemas de caso médio intratáveis em NP é uma das motivações principais para o estudo da complexidade de caso médio.

Outros resultados

Em 1990, Impagliazzo e Levin mostraram que se existe um algoritmo eficiente de caso médio para um problema distNP-completo sob a distribuição uniforme, então existe um algoritmo de caso médio para todo problema em NP sob qualquer distribuição amostrável em tempo polinomial. Aplicando esta teoria a problemas de distribuição naturais permanece sendo uma ótima questão em aberto.

Em 1992, Ben-David et-al. mostrou que se todas as linguagens em distNP possuem algoritmos de decisão que são bons em média, elas também possuem algoritmos de busca que são bons em média. Além disso, eles mostram que esta conclusão continua válida sob uma suposição mais fraca: se toda linguagem em NP é fácil em média para algoritmos de decisão em respeito à distribuição uniforme, então é também fácil em média para algoritmos de busca em respeito à distribuição uniforme. Portanto, funções criptográficas de mão única podem existir somente se existem problemas distNP sobre a distribuição uniforme que são difíceis em média para os algoritmos de decisão.

Em 1993, Feigenbaum e Fortnow mostraram que não é possível provar, sob reduções aleatórias não-adaptativas, que a existência de um algoritmo bom em média para um problema distNP-completo sob a distribuição uniforme implica na existência de algoritmos eficientes no pior caso para todos os problemas em NP. Em 2003, Bogdanov e Trevisan generalizaram este resultado para reduções não adaptativas arbitrárias. Estes esultados mostram que é improvável que qualquer associação pode ser feita entre complexidade de caso médio e complexidade de pior caso via reduções.

Ver também

• Análise de algoritmos
• Problemas NP-Completos
• Complexidade de pior caso

Leitura adicional

A literatura da complexidade de caso médio inclui os seguintes trabalhos:

• Franco, John (1986), «On the probabilistic performance of algorithms for the satisfiability problem», Information Processing Letters, 23 (2): 103–106, doi:10.1016/0020-0190(86)90051-7 .
• Levin, Leonid (1986), «Average case complete problems», SIAM Journal on Computing, 15 (1): 285–286, doi:10.1137/0215020 .
• Flajolet, Philippe; Vitter, J. S. (agosto 1987), Average-case analysis of algorithms and data structures, Tech. Report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France .
• Gurevich, Yuri; Shelah, Saharon (1987), «Expected computation time for Hamiltonian path problem», SIAM Journal on Computing, 16 (3): 486–502, doi:10.1137/0216034 .
• Ben-David, Shai; Chor, Benny; Goldreich, Oded; Luby, Michael (1989), «On the theory of average case complexity», Proc. 21st Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 204–216 .
• Gurevich, Yuri (1991), «Average case completeness», Journal of Computer and`System Sciences, 42 (3): 346–398, doi:10.1016/0022-0000(91)90007-R . See also 1989 draft.
• Selman, B.; Mitchell, D.; Levesque, H. (1992), «Hard and easy distributions of SAT problems», Proc. 10th National Conference on Artificial Intelligence, pp. 459–465 .
• Schuler, Rainer; Yamakami, Tomoyuki (1992), «Structural average case complexity», Proc. Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, 652, Springer-Verlag, pp. 128–139 .
• Reischuk, Rüdiger; Schindelhauer, Christian (1993), «Precise average case complexity», Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science, pp. 650–661 .
• Venkatesan, R.; Rajagopalan, S. (1992), «Average case intractability of matrix and Diophantine problems», Proc. 24th Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 632–642 .
• Cox, Jim; Ericson, Lars; Mishra, Bud (1995), The average case complexity of multilevel syllogistic (PDF), Technical Report TR1995-711, New York University Computer Science Department .
• Impagliazzo, Russell (17 de abril de 1995), A personal view of average-case complexity, University of California, San Diego .
• Paul E. Black, "Θ", in Dictionary of Algorithms and Data Structures[online]Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.Retrieved Feb. 20/09.
• Christos Papadimitriou (1994). Computational Complexity. Addison-Wesley.