Złożoność przestrzeni dla średnich przypadków

11

Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana.

Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją jakieś z analizą średnich przypadków (np. Granica jest zachowana, nawet jeśli algorytm jest dozwolony błądzić przez niewielki procent razy itp.)

Z góry dziękuję

cc.complexity-theory reference-request space-bounded average-case-complexity użytkownik4359
źródło
2
Jeśli możesz być bardziej szczegółowy, myślę, że będziesz bardziej skłonny uzyskać odpowiedzi na swoje pytanie. Czy przez „złożoność problemu w średniej wielkości przypadków” masz na myśli średnią minimalnej przestrzeni wymaganej do rozwiązania każdego z zestawów wystąpień jakiegoś problemu? Nie jestem pewien, czy to dobrze zdefiniowane, chociaż nie jest to coś, o czym myślałem bardzo szczegółowo. Jeśli masz na myśli coś prostszego, na przykład średnią złożoność przestrzeni danego algorytmu podczas rozwiązywania problemu, myślę, że twoje pytanie może nie uzyskać wielu odpowiedzi, ponieważ jest tak wiele możliwości. (ciąg dalszy w następnym komentarzu)
jbapple
(ciąg dalszy od góry) W szczególności, jeśli to masz na myśli, twoje pytanie może być nieco zbyt ogólne dla TCS SE: cstheory.stackexchange.com/faq Może, a może nie. Pierwszy przykład, który pojawia się w mojej głowie, to ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , ale wiele randomizowanych struktur danych zawiera analizy przestrzeni.
jbapple
3
@jbapple: Nie mogę podążać za twoją krytyką. Pomyślałem, że z pytania wynika jasno, że pytający szuka prac nad odpowiednikiem złożoności przestrzeni w średniej złożoności Levina w średnim przypadku, i nadal tak myślę, nawet po przeczytaniu twoich komentarzy. Nie mogę odpowiedzieć na pytanie nie dlatego, że pytanie jest niejasne, ale dlatego, że nie znam dobrze tematu i nie znam żadnej takiej pracy.
Tsuyoshi Ito
@Tsuyoshi Ito: Masz rację.
jbapple 28.03.11
interpretacja „analizy średnich przypadków” jako „algorytmu może kilka razy popełnić błąd” sprawia, że ​​brzmi to jak analiza losowa.
Suresh Venkat

Odpowiedzi:

7

Jestem zainteresowany tym tematem, ale go nie znam. Szukając „teorii średniej złożoności przypadków”, znalazłem pracę napisaną przez Tomoyuki Yamakami:

Teoria złożoności obliczeniowej średnich przypadków , Tomoyuki Yamakami, 1997.

Sekcja 3.5.1 wydaje się istotna, zdefiniowano pojęcie przestrzenno-analogiczne podobne do złożoności średniego czasu. Mam nadzieję, że przy głębszym czytaniu znajdziemy kilka problemów, które zostały przeanalizowane :)

Również w gazecie

O teorii średniej złożoności przypadków Shai Ben-David, Benny Chor, Oded Goldreich i Michael Luby, 1989.

Średnia złożoność przestrzeni logowej jest zdefiniowana w rozdziale 7.

Hsien-Chih Chang 張顯 之
źródło