Il est bien connu que les palindromes peuvent être reconnus en temps linéaire sur des machines de Turing à bandes, mais pas sur des machines de Turing à bande unique (auquel cas le temps nécessaire est quadratique). L'algorithme de temps linéaire utilise une copie de l'entrée et utilise donc...
Quelle est la complexité la plus connue pour calculer la distance d'édition exacte entre deux chaînes de même longueur en utilisant un espace de travail qui est sublinéaire dans la taille de l'entrée? Je suppose que l'entrée est stockée dans un format en lecture seule. Est-ce un problème déjà...
Il est facile de voir que tout problème décidable dans un espace de log déterministe ( ) s'exécute au plus en temps polynomial ( ). De nombreux algorithmes connus de l'espace de journalisation (par exemple: connectivité st non dirigée, isomorphisme de graphe planaire) s'exécutent dans où est...
Considérons un langage tel que:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) et pour que L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) En d'autres termes, la machine la...
Je m'intéresse à la première histoire des résultats publiés sur les compromis spatio-temporels à usage général. En particulier, je veux savoir qui a décrit en premier le type d'algorithme suivant pour évaluer un calcul ayant un graphique de flux de données arbitraire avec en degré O (1) en...
(déjà demandé sur le site principal , mais aussi ici pour une meilleure couverture, désolé) Depuis que je connaissais les structures de données succinctes, j'ai désespérément besoin d'une bonne vue d'ensemble des développements les plus récents dans ce domaine. J'ai googlé et lu beaucoup d'articles...
Le non-déterminisme peut-il accélérer le calcul déterministe? Si oui, combien? En accélérant le calcul déterministe par le non-déterminisme, j'entends les résultats de la forme: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Par exemple quelque chose comme...
Suite à la discussion sur les bornes inférieures pour 3SAT [ 1 ], je me demande quels sont les principaux résultats de borne inférieure formulés comme des compromis espace-temps. J'exclus des résultats tels que, disons, le théorème de Savitch; une bonne entrée se concentrerait sur un seul problème...
Si on nous donne deux chaînes de taille et , le calcul standard de la distance d'édition de Levenshtein se fait par un algorithme dynamique avec la complexité temporelle et la complexité spatiale . (Certaines améliorations peuvent être apportées en fonction de la distance de montage , mais nous ne...
Il y a eu quelques questions ( 1 , 2 , 3 ) sur l'achèvement transitif ici qui m'ont fait penser si quelque chose comme ça était possible: Supposons que nous obtenions un graphe orienté en entrée et que nous souhaitions répondre aux requêtes de type " ?", C'est-à-dire demander s'il existe une arête...
Il s'agit d'un suivi de l'accélération non déterministe du calcul déterministe . Est-il plausible que le non-déterminisme (ou plus généralement l'alternance) permette une accélération quadratique générale du calcul déterministe? Ou y a-t-il des conséquences invraisemblables connues pour quelque...