Complexité de l'espace moyen

11

J'essaie de trouver des problèmes dont la complexité de l'espace moyen des cas a été analysée.

Plus précisément, je suis intéressé de savoir s'il y a des problèmes avec une borne inférieure de complexité d'espace prouvée qui est super-linéaire, et surtout s'il y en a avec une analyse de cas moyen (par exemple, la borne tient même si l'algorithme est autorisé se tromper un petit pourcentage de fois, etc.)

Merci d'avance

cc.complexity-theory reference-request space-bounded average-case-complexity user4359
la source
2
Si vous pouvez être plus précis, je pense que vous aurez plus de chances d'obtenir des réponses à votre question. Par «complexité d'espace dans le cas moyen» d'un problème, voulez-vous dire la moyenne de l'espace minimum requis pour résoudre chacun des ensembles d'instances d'un problème? Je ne suis pas sûr que ce soit bien défini, même si ce n'est pas quelque chose auquel j'ai pensé en détail. Si vous voulez dire quelque chose de plus simple, comme la complexité moyenne de l'espace d'un algorithme particulier lors de la résolution d'un problème, je pense que votre question pourrait ne pas obtenir beaucoup de réponses car il y a tellement de possibilités. (continue dans le commentaire suivant)
jbapple
(suite de ci-dessus) En particulier, si c'est ce que vous voulez dire, votre question pourrait être un peu trop générale pour TCS SE: cstheory.stackexchange.com/faq Peut-être, peut-être pas. Le premier exemple qui me vient à l'esprit est ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , mais de nombreuses structures de données randomisées ont des analyses d'espace.
jbapple
3
@jbapple: Je ne peux pas suivre votre critique. J'ai pensé qu'il était clair d'après la question que le demandeur cherchait des travaux sur la contrepartie de la complexité spatiale de la complexité du temps moyen de Levin, et le pense toujours même après avoir lu vos commentaires. Je ne peux pas répondre à la question non pas parce que la question n'est pas claire, mais parce que je ne connais pas bien le sujet et que je ne connais pas un tel travail.
Tsuyoshi Ito
@Tsuyoshi Ito: Vous avez raison.
jbapple
interpréter "l'analyse de cas moyenne" comme "l'algorithme peut se tromper plusieurs fois" donne l'impression que l'analyse est aléatoire.
Suresh Venkat

Réponses:

7

Je m'intéresse à ce sujet mais je ne le connais pas. À la recherche de "Théorie de la complexité moyenne des cas", j'ai trouvé une thèse écrite par Tomoyuki Yamakami:

Théorie moyenne de la complexité de calcul des cas , Tomoyuki Yamakami, 1997.

La section 3.5.1 semble pertinente, une notion d'espace-analogique similaire à la complexité moyenne-temps est définie. J'espère qu'avec une lecture plus approfondie, nous trouverons quelques problèmes qui ont été analysés :)

Aussi dans le journal

Sur la théorie de la complexité moyenne des cas , Shai Ben-David, Benny Chor, Oded Goldreich et Michael Luby, 1989.

La complexité moyenne de l'espace journal est définie à la section 7.

Hsien-Chih Chang 張顯 之
la source