Рассмотрим такой язык , что:
и так что
Другими словами, самая быстрая машина вычисляет за время а наиболее экономичная машина вычисляет при использовании пространства .
Что можно сказать о пространственной эффективности М или временной эффективности М '? Или, точнее, если - это множество всех машин, которые вычисляют в то что мы можем сказать о самой машине в ? Как насчет того же самого для очевидной космической версии: .
В качестве альтернативы, можно ли использовать и для определения некоторых хороших пространственно-временных компромиссов? При каких условиях или, в более общем смысле, для некоторого пространственно-временного компромисса при каких условиях .g ( n ) T S ∈ o ( f ( n ) g ( n ) ) h ( T , S ) h ( T , S ) ∈ h ( o ( f ( n ) ) , o ( g ( n) ) ) )
источник
Ответы:
Прототипом f и g здесь, вероятно, будет поли-время и пространство полилога. Интересной проблемой здесь является связность (в ориентированных графах), которая может быть решена за полиномиальное время (с использованием линейного пространства) или в полилогическом пространстве (с использованием суперполиномиального времени). Это известная открытая проблема, может ли она быть решена в TIME-SPACE (poly, polylog), классе, известном как SC .
Т.е. твой вопрос - общеизвестная открытая проблема. Я не думаю, что здесь есть что-то нетривиальное.
источник
этот вопрос оказался на «похожих вопросах», когда я только что опубликовал этот другой вопрос /cstheory/9677/deterministic-time-space-separation-via-space-compression .
там я привожу результат Гопкрофта, Пола, Валиантса 1977 года (по-видимому, наиболее известный согласно rj lipton в его блоге), который, кажется, относится к вашему вопросу, т. е.DTIME(t(n))⊆DSPACE(t(n)/log(n))
источник