Complexidade do espaço médio

11

Estou tentando encontrar problemas cuja complexidade de espaço de caso médio foi analisada.

Mais especificamente, estou interessado em saber se existem problemas com um limite inferior da complexidade de espaço comprovado que é super-linear e, especialmente, se houver algum com uma análise de caso médio (por exemplo, o limite é válido mesmo que o algoritmo seja permitido errar uma pequena porcentagem de vezes etc.)

desde já, obrigado

cc.complexity-theory reference-request space-bounded average-case-complexity user4359
fonte
2
Se você puder ser mais específico, acho que você provavelmente obterá respostas para sua pergunta. Por "complexidade do espaço médio de caso" de um problema, você quer dizer a média do espaço mínimo necessário para resolver cada conjunto de instâncias de algum problema? Não tenho certeza de que esteja bem definido, embora não seja algo em que tenha pensado em grandes detalhes. Se você quer dizer algo mais simples, como a complexidade média do espaço de um algoritmo específico na solução de um problema, acho que sua pergunta pode não ter muitas respostas, porque existem muitas possibilidades. (continua na próxima comentário)
jbapple
(continuação de cima) Em particular, se é isso que você quer dizer, sua pergunta pode ser um pouco geral demais para o TCS SE: cstheory.stackexchange.com/faq Talvez, talvez não. O primeiro exemplo que aparece na minha cabeça é ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , mas muitas estruturas de dados aleatórias têm análises de espaço.
jbapple
3
@ jbapple: Eu não posso seguir suas críticas. Eu pensei que ficou claro a partir da pergunta que o solicitante está procurando trabalhos sobre a contrapartida da complexidade espacial da complexidade do tempo médio de caso de Levin, e ainda pensa assim mesmo depois de ler seus comentários. Não posso responder à pergunta não porque ela não esteja clara, mas porque não conheço bem o assunto e não conheço esse trabalho.
Tsuyoshi Ito 27/03
@ Tsuyoshi Ito: Você está certo.
jbapple
interpretar "análise de caso médio" como "o algoritmo pode errar algumas vezes" faz parecer uma análise aleatória.
Suresh Venkat

Respostas:

7

Estou interessado, mas não estou familiarizado com este tópico. Procurando por "teoria da complexidade média dos casos", encontrei uma tese escrita por Tomoyuki Yamakami:

Teoria Média da Complexidade Computacional de Casos , Tomoyuki Yamakami, 1997.

A Seção 3.5.1 parece relevante, é definida uma noção de espaço analógico semelhante à complexidade do tempo médio. Esperançosamente, com uma leitura mais profunda, encontraremos alguns problemas que foram analisados ​​:)

Também no jornal

Sobre a teoria da complexidade média dos casos , Shai Ben-David, Benny Chor, Oded Goldreich e Michael Luby, 1989.

A complexidade média do espaço de log é definida na Seção 7.

Hsien-Chih Chang 張顯 之
fonte