Durchschnittliche Raumkomplexität

11

Ich versuche, Probleme zu finden, deren durchschnittliche Raumkomplexität analysiert wurde.

Insbesondere interessiert mich, ob es Probleme mit einer nachgewiesenen Untergrenze der Raumkomplexität gibt, die superlinear ist, und insbesondere, wenn es Probleme mit einer Durchschnittsfallanalyse gibt (z. B. gilt die Grenze, selbst wenn der Algorithmus zulässig ist sich für einen kleinen Prozentsatz irren usw.)

Danke im Voraus

cc.complexity-theory reference-request space-bounded average-case-complexity user4359
quelle
2
Wenn Sie genauer sein könnten, werden Sie wahrscheinlich eher Antworten auf Ihre Frage erhalten. Meinen Sie mit "durchschnittliche Fallraumkomplexität" eines Problems den Durchschnitt des minimalen Speicherplatzes, der erforderlich ist, um jede Instanz eines Problems zu lösen? Ich bin mir nicht sicher, ob das gut definiert ist, obwohl ich nicht sehr detailliert darüber nachgedacht habe. Wenn Sie etwas Einfacheres meinen, wie die durchschnittliche räumliche Komplexität eines bestimmten Algorithmus bei der Lösung eines Problems, dann wird Ihre Frage möglicherweise nicht viele Antworten erhalten, da es nur so viele Möglichkeiten gibt. (Fortsetzung im nächsten Kommentar)
jbapple
(Fortsetzung von oben) Insbesondere wenn Sie das meinen, ist Ihre Frage für TCS SE möglicherweise etwas zu allgemein: cstheory.stackexchange.com/faq Vielleicht, vielleicht auch nicht. Das erste Beispiel, das mir in den Sinn kommt , ist ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , aber viele randomisierte Datenstrukturen haben Raumanalysen.
jbapple
3
@jbapple: Ich kann deiner Kritik nicht folgen. Ich dachte, dass es aus der Frage klar war, dass der Fragesteller nach Arbeiten zum Gegenstück zur räumlichen Komplexität von Levins durchschnittlicher zeitlicher Komplexität sucht, und denke dies auch nach dem Lesen Ihrer Kommentare. Ich kann die Frage nicht beantworten, nicht weil die Frage unklar ist, sondern weil ich das Thema nicht gut kenne und keine solche Arbeit kenne.
Tsuyoshi Ito
@ Tsuyoshi Ito: Du hast recht.
jbapple
Wenn man "durchschnittliche Fallanalyse" als "der Algorithmus darf einige Male fehlerhaft sein" interpretiert, klingt dies wie eine randomisierte Analyse.
Suresh Venkat

Antworten:

7

Ich interessiere mich für dieses Thema, bin aber mit ihm nicht vertraut. Auf der Suche nach "Average Case Complexity Theory" fand ich eine These von Tomoyuki Yamakami:

Average Case Computational Complexity Theory , Tomoyuki Yamakami, 1997.

Abschnitt 3.5.1 scheint relevant zu sein, es wird ein raumanaloger Begriff definiert, der der durchschnittlichen zeitlichen Komplexität ähnelt. Hoffentlich finden wir bei einer tieferen Lektüre einige Probleme, die analysiert wurden :)

Auch in der Zeitung

Zur Theorie der durchschnittlichen Fallkomplexität , Shai Ben-David, Benny Chor, Oded Goldreich und Michael Luby, 1989.

Die durchschnittliche Komplexität des Protokollbereichs ist in Abschnitt 7 definiert.

Hsien-Chih Chang 張顯 之
quelle