Une séparation explicite entre constructibilité temporelle et constructibilité spatiale?

Montrer une fonction qui est constructible dans l'espace mais pas dans le temps. $f(n)$

Ce problème est-il lié à une éventuelle séparation entre les classes de complexité DTIME (f (n)) et SPACE (f (n))?

cc.complexity-theory space-bounded separation Tian Liu
la source

en.wikipedia.org/wiki/Constructible_function Pour autant que je sache, cette question n'est pas liée à TIME (f (n)) vs SPACE (f (n)), mais notez que ces deux classes sont connues pour être différentes. Recherchez les articles "On Time Versus Space", "On Time Versus Space II", "On Time Versus Space III"

Ryan Williams

Une observation rapide: je pense que le problème revient à demander si DTIME (f (n)) )TALLY et SPACE (f (n)) ∩TALLY peut être différent pour une fonction f (n) constructible dans l'espace, où TALLY est la classe de langues qui sont des sous-ensembles de 1 ^ *.

Tsuyoshi Ito

Oups, ils peuvent ne pas être équivalents. Voici une preuve d'une direction. S'il existe une langue L = {1 ^ n | n∈S} ∈ TALLY∩ (ESPACE (f (n)) ∖ DTIME (f (n))) pour une fonction de construction d'espace f (n), puis f (n) et f (n) + χ_S (n ) (où χ_S (n) est la fonction caractéristique de S) sont constructibles dans l'espace mais pas les deux sont constructibles dans le temps, et donc au moins l'un d'entre eux est une fonction constructible dans l'espace mais pas constructible dans le temps.

Tsuyoshi Ito

Merci à Ryan, par votre commentaire, je sais que TIME (f (n)) est contenu dans SPACE (f (n) / log f (n)) par Hopcroft et al, et que ce dernier est correctement contenu dans SPACE (f (n )) par le théorème de la hiérarchie spatiale.

Tian Liu

Grâce à Tsuyoshi, des idées très intelligentes, si f (n) et f (n) + χ_S (n) sont constructibles dans le temps, alors nous pouvons décider si n∈S dans au plus f (n) +1 fois, donc L ALLTALLY ∩ DTIME (f (n)), une contradiction. mais peut-on appeler vos constructions "explicites"? lequel n'est pas constructible dans le temps, f (n) ou f (n) + χ_S (n)? par "explicite" si je veux dire que nous pouvons décider de la valeur f (n) pour tout n, alors votre construction est explicite.

Tian Liu

Réponses:

Une fonction est constructible dans le temps s'il existe une machine de Turing qui, sur l'entrée , calcule la fonction dans le temps . $T \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto T(|x|)$ $O(T(n))$

Une fonction est constructible dans l'espace s'il existe une machine de Turing qui, sur l'entrée , calcule la fonction dans l'espace . $S \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto S(|x|)$ $O(S(n))$

Certains textes exigent que les fonctions constructibles temps / espace ne soient pas décroissantes. Certains textes nécessitent que les fonctions constructibles temporelles satisfassent , et les fonctions constructibles spatiales satisfassent . Certains textes n'utilisent pas la notation dans la définition. $T(n)\ge n$ $S(n)\ge \log n$ $O(\cdot)$

$f$ $f(n)\ge \log n$ $f(n) = o(n)$

Le problème de constructibilité n'est pas directement lié à une éventuelle séparation entre les classes de complexité DTIME (f (n)) et SPACE (f (n)). Cependant, l'énoncé des théorèmes de la hiérarchie du temps et de l'espace incorpore la constructibilité. Par exemple:

$f$ $g$ $f(n)\log f(n) = o(g(n))$ $\mathbf{DTIME}(f(n))$ $\mathbf{DTIME}(g(n))$

Voir le livre d'Arora & Barak ou celui de Papadimitriou pour plus d'informations. (Ce dernier utilise le terme «fonction de complexité appropriée» pour désigner celle qui est à la fois constructible dans le temps et dans l'espace.)

MS Dousti
la source

Merci. Je préfère la définition selon laquelle une fonction est constructible dans le temps / l'espace s'il existe une machine de Turing qui fonctionne exactement à ce pas / carrés de bande. Bien sûr, par les théorèmes d'accélération linéaire temps / espace, cela équivaut à vos définitions / manuels.

Tian Liu

Sadeq, vos définitions de «constructible dans le temps» et de «constructible dans l'espace» sont identiques mot à mot. Voulez-vous dire que ce ne sont que deux noms différents pour exactement le même concept? Sinon, vous devriez peut-être corriger vos définitions.

Yitz

Ce n'est qu'une faute de frappe.

Tsuyoshi Ito

Désolé Yitz. J'ai corrigé la faute de frappe.

MS Dousti

$f(n)=\log n$ $1^n$ $O(\log n)$ $O(\log n)$

Mohammad Al-Turkistany
la source

Merci au commentaire et à la réponse. Mais pouvez-vous montrer une fonction f (n) qui est au moins linéaire, c'est-à-dire f (n)> = n, pour la séparation? Il semble qu'une fonction constructible dans le temps ne puisse pas être inférieure à n pour une raison apparente: avoir à lire tous les bits d'entrée, sinon un argument adverse peut montrer que la fonction n'est pas correctement calculée.

Tian Liu

f (n) = n

$f(n)= n$

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}$

f (n) = {\begin{cases} 8 n + 2 & if (first ⌊ \sqrt[k]{⌊ \log n ⌋ + 1} ⌋ bits of b i n (n)) \in L \\ 8 n + 1 & else \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$

Cette réponse utilise la même idée.

David G
la source