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 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.
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.
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 tA(x) com a entrada x e o algoritmo B é executado em tempo tA(x)2 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 n2 em todas as entradas, exceto a palavra 1n, para a qual A leva um tempo de 2n. Então, é facilmente verificável que o tempo de execução esperado de A é polinomial mas que o tempo esperado de B é exponencial.
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: 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.
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 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,1t) : 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.
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.
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.
