Complexidade de caso médio - Average-case complexity

Na teoria da complexidade computacional , a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (normalmente tempo) usado pelo algoritmo, calculada a média de todas as entradas possíveis. É frequentemente contrastado com a complexidade do 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. Em primeiro lugar, embora alguns problemas possam ser intratáveis ​​no pior caso, as entradas que geram esse comportamento raramente ocorrem na prática, de modo que a complexidade do caso médio pode ser uma medida mais precisa do desempenho de um algoritmo. Em segundo lugar, 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 desregulamentação . Terceiro, a complexidade de caso médio permite discriminar o algoritmo mais eficiente na prática entre algoritmos de complexidade de melhor caso equivalente (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 aleatório pode ser usado. A análise de tais algoritmos leva à noção relacionada de uma complexidade esperada .

História e antecedentes

O desempenho de caso médio de algoritmos tem sido estudado desde que as noções modernas de eficiência computacional foram desenvolvidas na década de 1950. Muito 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 da Art of Computer Programming, que examina extensivamente o desempenho de caso médio de algoritmos para problemas solucionáveis ​​em tempo polinomial de pior caso, como classificação e localização de mediana.

Um algoritmo eficiente para problemas NP-completos é geralmente caracterizado como aquele que roda em tempo polinomial para todas as entradas; isso é equivalente a exigir complexidade eficiente do pior caso. No entanto, um algoritmo que é ineficiente em um "pequeno" número de entradas pode ainda ser eficiente para "a maioria" das entradas que ocorrem na prática. Assim, é desejável estudar as propriedades desses algoritmos onde a complexidade de caso médio pode diferir da complexidade de pior caso e encontrar métodos para relacionar as duas.

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 complexidade e completude de caso médio, dando um exemplo de um problema completo para distNP, o análogo de caso médio de NP .

Definições

Complexidade eficiente de caso médio

A primeira tarefa é definir com precisão o que se entende por um algoritmo que é eficiente "na média". Uma tentativa inicial pode definir um algoritmo de caso médio eficiente como aquele que é executado no tempo polinomial esperado sobre todas as entradas possíveis. Essa definição tem várias deficiências; em particular, não é robusto a mudanças no modelo computacional. Por exemplo, suponha que o algoritmo A execute no tempo t _A (x) na entrada x e o algoritmo B execute no tempo t _A (x) ² na 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 em média se e somente se B é eficiente em média. Suponha, entretanto, que as entradas são extraídas aleatoriamente da distribuição uniforme de strings com comprimento , e que A roda no tempo n ² em todas as entradas, exceto na string 1 ⁿ para a qual A leva tempo 2 ⁿ . Então, pode ser facilmente verificado se o tempo de execução esperado de A é polinomial, mas o tempo de execução esperado de B é exponencial. ${\ displaystyle n}$

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

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

para todo n, t, ε> 0 e polinômio p, onde t _A (x) denota o tempo de execução do algoritmo A na entrada x. Alternativamente, isso pode ser escrito como

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

para alguma constante C, onde n = | x |. Em outras palavras, um algoritmo A tem uma boa complexidade de caso médio se, após a execução de t _A (n) etapas, A puder resolver tudo, exceto uma fração de entradas de comprimento n, para algum ε, c> 0. ${\ displaystyle {\ frac {n ^ {c}} {(t_ {A} (n)) ^ {\ epsilon}}}}$

Problema de distribuição

A próxima etapa é definir a entrada "média" para um problema específico. Isso é obtido associando as entradas de cada problema a uma distribuição de probabilidade particular. Ou seja, um problema de "caso médio" consiste em uma linguagem L e uma distribuição de probabilidade D associada 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 (computável P): são distribuições para as quais é possível calcular a densidade cumulativa de qualquer entrada x fornecida. Mais formalmente, dada uma distribuição de probabilidade μ e uma string x ∈ {0, 1} ⁿ , é possível calcular o valor em tempo polinomial. Isso implica que Pr [x] também é computável em tempo polinomial.${\ displaystyle \ mu (x) = \ sum \ limits _ {y \ in \ {0,1 \} ^ {n}: y \ leq x} \ Pr [y]}$
2. Distribuições amostráveis ​​em tempo polinomial (amostrável P): são distribuições a partir das quais é possível extrair amostras aleatórias em tempo polinomial.

Essas duas formulações, embora semelhantes, 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 e distNP

Um problema de distribuição (L, D) está na classe de complexidade AvgP se houver um algoritmo de caso médio eficiente para L, conforme definido acima. A classe AvgP é ocasionalmente chamada de distP na literatura.

Um problema de distribuição (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 é amostrável por P, (L, D) pertence a sampNP.

Juntos, AvgP e distNP definem os análogos de caso médio de P e NP, respectivamente.

Reduções entre problemas de distribuição

Sejam (L, D) e (L ', D') dois problemas de distribuição. (L, D) caso médio se reduz a (L ', D') (escrito (L, D) ≤ _AvgP (L ', D')) se houver uma função f que para cada n, na entrada x pode ser calculado no tempo polinomial em n e

1. (Correção) x ∈ L se e somente se f (x) ∈ L '
2. (Dominação) Existem polinômios p e m tais que, para cada n e y, ${\ displaystyle \ 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 noção de que se o problema (L, D) é difícil em média, então (L ', D') também é difícil em média. Intuitivamente, uma redução deve fornecer uma maneira de resolver uma instância x do problema L calculando f (x) e alimentando a saída para o algoritmo que resolve L '. Sem a condição de dominação, isso pode não ser possível, pois o algoritmo que resolve L em tempo polinomial em média pode levar tempo superpolinomial em um pequeno número de entradas, mas f pode mapear essas entradas em um conjunto muito maior de D 'para que o algoritmo A 'não é mais executado em tempo polinomial, em média. A condição de dominação permite apenas que tais strings ocorram polinomialmente com a freqüência em D '.

Problemas distNP-completo

O análogo de caso médio para NP-completude é distNP-completude. Um problema de distribuição (L ', D') é distNP-completo se (L ', D') está em distNP e para cada (L, D) em distNP, (L, D) é o caso médio redutível a (L ' , D ').

Um exemplo de um problema distNP-completo é o problema de parada limitada, BH, definido como segue:

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

Em seu artigo original, Levin mostrou um exemplo de um problema de tiling de distribuição que é NP-completo de caso médio. Uma pesquisa de problemas distNP-complete conhecidos está disponível online.

Uma área de pesquisa ativa envolve a descoberta de novos problemas distNP-completos. No entanto, encontrar tais problemas pode ser complicado devido a um resultado de Gurevich que mostra que qualquer problema de distribuição com uma distribuição plana não pode ser distNP-complete a menos que EXP = NEXP . (Uma distribuição plana μ é aquela para a qual existe um ε> 0 tal que para qualquer x, μ (x) ≤ 2 ^{- | x | ε} .) Um resultado de Livne mostra que todos os problemas NP-completos naturais têm DistNP-completo versões. No entanto, o objetivo de encontrar um problema distributivo natural que seja DistNP-completo ainda não foi alcançado.

Formulários

Algoritmos de classificação

Como mencionado acima, muitos trabalhos iniciais relacionados à complexidade de caso médio focaram em problemas para os quais algoritmos de tempo polinomial já existiam, como classificação. Por exemplo, muitos algoritmos de classificação que utilizam aleatoriedade, como Quicksort , têm um tempo de execução de pior caso de O (n ² ), mas um tempo de execução de caso médio de O (nlog (n)), onde n é o comprimento de a entrada a ser classificada.

Criptografia

Para a maioria dos problemas, a análise de complexidade de caso médio é realizada 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 do pior caso é irrelevante; em vez disso, queremos uma garantia de que a complexidade de caso médio de cada algoritmo que "quebra" o esquema criptográfico é ineficiente.

Assim, todos os esquemas criptográficos seguros dependem da existência de funções unilaterais . Embora a existência de funções unilaterais ainda seja um problema em aberto, muitas funções unilaterais candidatas são baseadas em problemas difíceis, como fatoração de inteiros ou cálculo do log discreto . Observe que não é desejável que a função candidata seja NP-completa, pois isso apenas garantiria que provavelmente não há algoritmo eficiente para resolver o problema no pior caso; o que realmente queremos é uma garantia de que nenhum algoritmo eficiente pode resolver o problema sobre entradas aleatórias (ou seja, o caso médio). Na verdade, tanto a fatoração de inteiros quanto os problemas de log discreto estão em NP ∩ coNP e, portanto, não se acredita que sejam NP-completos. O fato de que toda a criptografia é baseada na existência de problemas intratáveis ​​de caso médio em NP é uma das principais motivações para estudar a complexidade de caso médio.

Outros resultados

Em 1990, Impagliazzo e Levin mostraram que se existe um algoritmo de caso médio eficiente para um problema distNP-completo sob a distribuição uniforme, então existe um algoritmo de caso médio para cada problema em NP sob qualquer distribuição amostrável em tempo polinomial. Aplicar essa teoria a problemas distributivos naturais permanece uma questão pendente pendente.

Em 1992, Ben-David et al. mostraram que se todas as linguagens em distNP têm algoritmos de decisão bons na média, eles também têm algoritmos de pesquisa bons na média. Além disso, eles mostram que essa conclusão é válida sob uma suposição mais fraca: se cada linguagem em NP é fácil em média para algoritmos de decisão com relação à distribuição uniforme, então também é fácil em média para algoritmos de pesquisa com relação à distribuição uniforme. Assim, as funções criptográficas unilaterais podem existir apenas se houver problemas distNP sobre a distribuição uniforme que são difíceis em média para 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 na média para um problema distNP-completo sob a distribuição uniforme implica a existência de pior caso algoritmos eficientes para todos os problemas em NP. Em 2003, Bogdanov e Trevisan generalizaram este resultado para reduções não adaptativas arbitrárias. Esses resultados mostram que é improvável que qualquer associação possa ser feita entre a complexidade do caso médio e a complexidade do pior caso por meio de reduções.

Veja também

• Análise probabilística de algoritmos
• Problemas NP-completos
• Complexidade de pior caso
• Análise amortizada
• Melhor, pior e médio caso

Referências

Leitura adicional

A literatura de complexidade média de caso inclui o seguinte trabalho:

• Franco, John (1986), "On the probabilistic performance of algoritms 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, JS (agosto de 1987), Análise de caso médio de algoritmos e estruturas de dados , Tech. Relatório, Institut National de Recherche en Informatique et en Automatique, BP 105-78153 Le Chesnay Cedex França.
• Gurevich, Yuri ; Shelah, Saharon (1987), "Expected computation time for Hamiltonian path problem ", SIAM Journal on Computing , 16 (3): 486–502, CiteSeerX  10.1.1.359.8982 , doi : 10.1137 / 0216034.
• Ben-David, Shai; Chor, Benny; Goldreich, Oded ; Luby, Michael (1989), "Sobre a teoria da complexidade média dos casos", Proc. 21º Simpósio Anual de Teoria da Computação , 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 , hdl : 2027.42 / 29307. Veja também o rascunho de 1989 .
• Selman, B .; Mitchell, D .; Levesque, H. (1992), "Hard and easy distributions of SAT problems", Proc. 10ª Conferência Nacional de Inteligência Artificial , pp. 459-465.
• Schuler, Rainer; Yamakami, Tomoyuki (1992), "Structural average case complex", 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 complex", Proc. 10º Simpósio Anual de Aspectos Teóricos da Ciência da Computação , pp. 650-661.
• Venkatesan, R .; Rajagopalan, S. (1992), "Average case intractability of matrix and Diophantine problems", Proc. 24º Simpósio Anual de Teoria da Computação , Association for Computing Machinery , pp. 632-642.
• Cox, Jim; Ericson, Lars; Mishra, Bud (1995), The average case complex of multilevel syllogistic (PDF) , Technical Report TR1995-711, New York University Computer Science Department.
• Impagliazzo, Russell (17 de abril de 1995), Uma visão pessoal da complexidade de caso médio , Universidade da Califórnia, San Diego.
• Paul E. Black, "Θ" , no Dicionário de Algoritmos e Estruturas de Dados [online] Paul E. Black, ed., Instituto Nacional de Padrões e Tecnologia dos EUA. 17 de dezembro de 2004. Recuperado em 20/09.
• Christos Papadimitriou (1994). Complexidade computacional. Addison-Wesley.