Пространство средней сложности

11

Я пытаюсь найти проблемы, сложность которых в среднем случае была проанализирована.

Более конкретно, мне интересно знать, есть ли какие-либо проблемы с доказанной нижней границей сложности пространства, которая является суперлинейной, и особенно, если есть какие-либо проблемы с анализом среднего случая (например, оценка выполняется, даже если алгоритм разрешен ошибаться в течение небольшого процента раз и т. д.)

заранее спасибо

cc.complexity-theory reference-request space-bounded average-case-complexity user4359
источник
2
Если вы могли бы быть более конкретным, я думаю, что у вас будет больше шансов получить ответы на свой вопрос. Под «сложностью пространства в среднем случае» вы подразумеваете среднее минимального пространства, необходимого для решения каждого из наборов какой-либо задачи? Я не уверен, что это четко определено, хотя я не очень подробно об этом думал. Если вы имеете в виду что-то более простое, например, среднюю сложность конкретного алгоритма при решении задачи, то я думаю, что ваш вопрос может не получить много ответов, потому что возможностей так много. (продолжение в следующем комментарии)
jbapple
(продолжение сверху) В частности, если вы это имеете в виду, ваш вопрос может быть слишком общим для TCS SE: cstheory.stackexchange.com/faq Может быть, а может и нет. Первый пример, который появляется в моей голове, - это ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , но многие рандомизированные структуры данных имеют пространственный анализ.
Jbapple
3
@jbapple: я не могу следовать вашей критике. Я подумал, что из вопроса ясно, что спрашивающий ищет работы на уровне сложности пространства, аналогичном сложности времени Левина в среднем случае, и все еще думаю, что даже после прочтения ваших комментариев. Я не могу ответить на вопрос не потому, что вопрос неясен, а потому, что я плохо знаю предмет и не знаю ни одной такой работы.
Цуёси Ито
@ Tsuyoshi Ito: Ты прав.
jbapple
Интерпретация «анализа среднего случая» как «алгоритму разрешено несколько раз ошибиться» делает его похожим на рандомизированный анализ.
Суреш Венкат

Ответы:

7

Я заинтересован, но не знаком с этой темой. В поисках «Теории средней сложности случая» я нашел тезис, написанный Томоюки Ямаками:

Вычислительная сложность среднего случая , Томоюки Ямаками, 1997.

Раздел 3.5.1 представляется актуальным, определяется пространственно-аналоговое понятие, аналогичное сложности среднего времени. Надеюсь, с более глубоким чтением мы найдем некоторые проблемы, которые были проанализированы :)

Также в газете

К теории средней сложности случая , Шай Бен-Давид, Бенни Чор, Одед Голдрайх и Майкл Луби, 1989.

Средняя сложность лог-пространства определяется в разделе 7.

Сянь-Чжи Чан 張顯 之
источник