Явное разделение между конструктивностью во времени и конструктивностью в пространстве?

Покажите функцию которая конструируется в пространстве, но не является временной. $f(n)$

Связана ли эта проблема с возможным разделением между классами сложности DTIME (f (n)) и SPACE (f (n))?

cc.complexity-theory space-bounded separation Тян Лю
источник

en.wikipedia.org/wiki/Constructible_function Насколько я знаю, этот вопрос не связан с TIME (f (n)) и SPACE (f (n)), но обратите внимание, что эти два класса, как известно , различны. Ищите статьи «О времени и пространстве», «О времени и пространстве II», «О времени и пространстве III»

Райан Уильямс,

Быстрое наблюдение: я думаю, что проблема эквивалентна вопросу о том, могут ли DTIME (f (n)) ∩TALLY и SPACE (f (n)) ∩TALLY различаться для некоторой пространственно-конструктивной функции f (n), где TALLY класс языков, которые являются подмножествами 1 ^ *.

Цуёси Ито

К сожалению, они не могут быть эквивалентными. Вот доказательство одного направления. Если существует язык L = {1 ^ n | n∈S} ∈ TALLY∩ (ПРОБЕЛ (f (n)) ∖ DTIME (f (n))) для некоторой конструктивно-пространственной функции f (n), тогда и f (n), и f (n) + χ_S (n ) (где χ_S (n) - характеристическая функция S) конструируемые в пространстве, но не оба они конструируемые во времени, и, следовательно, по крайней мере одна из них является конструируемой в пространстве, но не конструируемой во времени функцией.

Цуёси Ито

Благодаря Райану, по вашему комментарию я знаю, что TIME (f (n)) содержится в SPACE (f (n) / log f (n)) Хопкрофта и др., А последний правильно содержится в SPACE (f (n) )) по теореме о пространственной иерархии.

Тян Лю

Благодаря Tsuyoshi, очень умным идеям, если и f (n), и f (n) + χ_S (n) являются конструируемыми по времени, то мы можем решить, будет ли n∈S в самое большее f (n) +1 время, таким образом, L ∈TALLY ∩ DTIME (f (n)), противоречие. но можно ли назвать ваши конструкции "экспликтом"? какой из них не конструируемый во времени, f (n) или f (n) + χ_S (n)? под «явным», если я имею в виду, что мы можем определить значение f (n) для всех n, то ваша конструкция является явной.

Тянь Лю

Ответы:

Функция является конструируемой по времени, если существует машина Тьюринга которая на входе вычисляет функцию за время . $T \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto T(|x|)$ $O(T(n))$

Функция конструируема в пространстве, если существует машина Тьюринга которая на входе вычисляет функцию в пространстве . $S \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto S(|x|)$ $O(S(n))$

Некоторые тексты требуют, чтобы конструктивные функции времени / пространства были неубывающими. Некоторые тексты требуют, чтобы конструктивные функции времени удовлетворяли , а конструктивные функции пространства удовлетворяют . Некоторые тексты не используют обозначение в определении. $T(n)\ge n$ $S(n)\ge \log n$ $O(\cdot)$

В любом случае, легко показать, что каждая «обычная» функция , удовлетворяющая и конструируема в пространстве, но не конструктивна во времени. $f$ $f(n)\ge \log n$ $f(n) = o(n)$

Проблема конструктивности не связана напрямую с возможным разделением между классами сложности DTIME (f (n)) и SPACE (f (n)). Однако утверждение теорем о временной и пространственной иерархии включает в себя конструктивность. Например:

Теорема о временной иерархии. Если , - функции, построенные во времени, удовлетворяющие , то является собственным подмножеством . $f$ $g$ $f(n)\log f(n) = o(g(n))$ $\mathbf{DTIME}(f(n))$ $\mathbf{DTIME}(g(n))$

Обратитесь к книге Ароры и Барака или к Пападимитриу за дополнительной информацией. (Последний использует термин «правильная функция сложности» для обозначения того, что является одновременно конструируемым как во времени, так и в пространстве.)

М.С. Дусти
источник

Спасибо. Я предпочитаю определение, что функция является конструируемой во времени / пространстве, если есть машина Тьюринга, которая работает точно с шагами / квадратами ленты. Конечно, по теорем линейного ускорения времени / пространства это эквивалентно вашим определениям из учебника.

Тянь Лю

Sadeq, ваши определения терминов «конструируемый во времени» и «конструируемый в пространстве» дословно идентичны. Вы говорите, что это просто два разных названия для одной и той же концепции? Если нет, возможно, вам следует исправить свои определения.

Иц

Это просто опечатка.

Цуёси Ито

Извини Иц. Я исправил опечатку.

MS Dousti

является конструируемым в пространстве, но не конструируемым во времени. Причина в том, что вы можете отобразить в двоичное представление в пространстве но не во времени . $f(n)=\log n$ $1^n$ $O(\log n)$ $O(\log n)$

Мухаммед Аль-Туркистани
источник

Спасибо за комментарий и ответ. Но можете ли вы показать функцию f (n), которая по крайней мере линейна, то есть f (n)> = n, для разделения? Кажется, что функция времени может быть не меньше n по очевидной причине: необходимо прочитать все входные биты, в противном случае аргумент противника может показать, что функция вычислена неправильно.

Тян Лю

@Tian,

- конструируемая в пространстве, но не конструируемая во времени функция.

f (n) = n

$f(n)= n$

Мухаммед Аль-Туркистани

Еще раз спасибо, но вы предполагаете, что считывающая головка на входной ленте изначально расположена слева от первого бита ввода? в этом случае, чтобы обнаружить последний бит ввода, головка должна двигаться вправо n + 1 раз, пока не встретится первый пробел после ввода. Тогда

конструируемо по времени. Поэтому, пожалуйста, дайте "нетривальное" разделение с помощью функции f (n)> = n + 1?

f (n) = n + 1

$f(n)=n+1$

Тянь Лю

$EXP-TIME=EXP-SPACE$ $EXP-SPACE-COMPLETE$ $L\in EXP-SPACE$ $L\subseteq\{0,1\}^*$ $k\in\mathbb{N}$ $L$ $M$ $2^{n^k}$

е (N) знак равно {\begin{cases} 8 N + 2 & если (первый ⌊ \sqrt[К]{⌊ журнал N ⌋ + 1} ⌋ биты б я N (N)) \in L \\ 8 N + 1 & еще \end{cases}

$f(n)=\left\{\begin{array}{ll} 8n+2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\ 8n+1 & \mbox{else} \end{array} \right.$

$2n$ $f$ $f$ $L$

Этот ответ использует ту же идею.

Дэвид Г
источник