Reduções de pior caso para média de caso

Existem problemas cuja complexidade média de casos é a mesma de pior complexidade? Quais são as propriedades subjacentes a esses problemas que tornam possível reduzir o pior caso para o caso médio?

Esse tipo de problema tem sido objeto de bastante estudo. Você pode encontrar referências pesquisando a auto-redutibilidade aleatória no Google, e o artigo da Wikipedia é um bom lugar para começar a ler. Ainda existem muitas perguntas abertas associadas.

A entrada da Wikipedia à qual Peter se referiu menciona alguns exemplos importantes de problemas que apresentam reduções médias de casos piores, como a permanente. Problema vetorial mais curto (assim como problemas relacionados com treliça) é outro exemplo importante, veja o artigo de Ajtai e o que veio depois (trabalhos de Regev, Micciancio, Peikert, ...).

Uma das únicas observações gerais que temos sobre problemas com redução do pior para o caso médio é a seguinte (iniciada com o trabalho de Feigenbaum e Fortnow ): (pelo menos para reduções não adaptativas), é provável que esses problemas não sejam complete para classes que (provavelmente) não estão fechadas sob complemento (por exemplo, é provável que não sejam NP-complete).

$NP \cap coNP$