Пространственно-временной компромисс и лучший алгоритм

14

Рассмотрим такой язык L , что:

LDTIME(O(f(n)))DSPACE(O(g(n)))

и так что

LDTIME(o(f(n)))DSPACE(o(g(n)))

Другими словами, самая быстрая машина вычисляет за время а наиболее экономичная машина вычисляет при использовании пространства .MLO(f(n))MLO(g(n))

Что можно сказать о пространственной эффективности М или временной эффективности М '? Или, точнее, если - это множество всех машин, которые вычисляют в то что мы можем сказать о самой машине в ? Как насчет того же самого для очевидной космической версии: .MTLO(f(n))MTMS

В качестве альтернативы, можно ли использовать и для определения некоторых хороших пространственно-временных компромиссов? При каких условиях или, в более общем смысле, для некоторого пространственно-временного компромисса при каких условиях .g ( n ) T S o ( f ( n ) g ( n ) ) h ( T , S ) h ( T , S ) h ( o ( f ( n ) ) , o ( g ( n) ) ) )f(n)g(n)TSo(f(n)g(n))h(T,S)h(T,S)h(o(f(n)),o(g(n)))

Артем Казнатчеев
источник
Вы спрашиваете о произвольном L или вас интересуют результаты такого рода, которые могут существовать для конкретных проблем?
Суреш Венкат
Я действительно заинтересован в обоих. Моя первоначальная мотивация была в основном из-за проблем достижимости (направленная и ненаправленная st-связность). Тем не менее, было бы интересно узнать, есть ли какие-либо общие ограничения или доступные методы.
Артем Казнатчеев
2
Итак, возьмите любой разрешимый язык . Этот язык дает функции F L , г L , так что L ВРЕМЯ [ F L ( п ) ] ПРОСТРАНСТВО [ г л ( п ) ] и L ВРЕМЯ [ О ( е L ( п ) ) ] ПРОСТРАНСТВО [ О ( г L ( n ) ) ]LfL,gLLВРЕМЯ[еL(N)]КОСМОС[граммL(N)]LTIME[o(fL(n))]SPACE[o(gL(n))], (Это правда, или есть «ускоренные» языки, которые нарушают это?)
Деррик Столи
В частности, есть примеры в диапазоне поиска проблем, которые допускают (Query, Space) формы (log n, poly (n)) или (сублинейный, линейный) или любую их интерполяцию
Суреш Венкат

Ответы:

14

Прототипом f и g здесь, вероятно, будет поли-время и пространство полилога. Интересной проблемой здесь является связность (в ориентированных графах), которая может быть решена за полиномиальное время (с использованием линейного пространства) или в полилогическом пространстве (с использованием суперполиномиального времени). Это известная открытая проблема, может ли она быть решена в TIME-SPACE (poly, polylog), классе, известном как SC .

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

Ноам
источник
Спасибо за ответ. Я подозревал, что это будет открытой проблемой, но надеялся, что некоторые конкретные результаты уже будут известны.
Неудачно
-4

этот вопрос оказался на «похожих вопросах», когда я только что опубликовал этот другой вопрос /cstheory/9677/deterministic-time-space-separation-via-space-compression .

там я привожу результат Гопкрофта, Пола, Валиантса 1977 года (по-видимому, наиболее известный согласно rj lipton в его блоге), который, кажется, относится к вашему вопросу, т. е. DTIME(t(n))DSPACE(t(n)/log(n))

ВЗН
источник
1
Я не понимаю, как это относится к пространственно-временным компромиссам ...
Артем Казнатчеев
понятие «пространственно-временного компромисса», похоже, не совсем определено. Мой ответ можно понять следующим образом: программа, которая находится в DTIME (t (n)), «естественно» в DSPACE (t (n)). результаты HPV1977 позволяют затем создать TM за счет некоторого увеличения состояний (и, может быть, лент?), так что вместо этого требуется пространство DSPACE (t (n) / log (n)). поэтому "компромисс"
vzn
1
Существует стандартное понимание компромиссов в CS, которое совсем не то, что вы описываете (то, что вы описываете, вовсе не компромисс, а просто стандартные отношения между DTIME и DSPACE). Кроме того, я подробно объясняю, чего я хочу в компромиссе между временем и пространством в своем вопросе, пожалуйста, внимательно прочитайте вопросы, прежде чем пытаться на них отвечать.
Артем Казнатчеев
Если ваше определение пространственно-временных компромиссов, приведенное выше в вашем вопросе, является стандартным, как вы говорите, определено ли оно в какой-либо литературе?
ВЗН
просматривая ваше определение, кажется интуитивно правдоподобным, что такие f (n), g (n) существуют для всех разрешимых языков, но не возникнет ли проблем, даже доказывающих, что такие f (n), g (n) обязательно существуют из-за теоремы ускорения Блума ....?
ВЗН