Je veux encoder une simple machine de Turing dans les règles d'un jeu de cartes. Je voudrais en faire une machine de Turing universelle afin de prouver l'exhaustivité de Turing. Jusqu'à présent, j'ai créé un état de jeu qui code pour la machine de Turing à 2 états et 3 symboles d'Alex Smith ....
J'ai pensé partager cette question car elle pourrait être intéressante pour d'autres utilisateurs ici. Supposons qu'une fonction qui est dans une classe uniforme (comme ) se trouve également dans une petite classe non uniforme (comme , c'est-à-dire non uniforme ), cela implique-t-il que la fonction...
Décider si une formule booléenne quantifiée telle que ∀ x1∃ x2∀ x3⋯ ∃ xnφ ( x1, x2, … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), évalue toujours à true est un problème classique PSPACE-complete. Cela peut être considéré...
Je suis plutôt confus par la littérature sur l'optimisation continue et la littérature TCS sur les types de programmes mathématiques (MP) (continus) qui peuvent être résolus efficacement et ceux qui ne le peuvent pas. La communauté de l'optimisation continue semble affirmer que tous les programmes...
J'étais (et je suis toujours) vraiment intéressé par la réponse à cette question, car il s'agit d'une variation intéressante sur la complexité des jeux qui n'a pas été résolue, alors j'ai offert une prime. Je pensais que la question d'origine était très probablement trop difficile, alors j'ai posté...
Il y a des tonnes de problèmes NP-complets et des sources qui les collectent, par exemple, voir le livre de Garey et Johnson. Je serais également intéressé de voir une liste des problèmes NEXP-complete. Y en a-t-il un disponible? Comme je suppose qu'il n'y en a pas, j'ouvre cette question (est-ce...
La connectivité ST est le problème de déterminer s'il existe un chemin dirigé entre deux sommets distincts et t dans un graphe dirigé G ( V , E ) . La question de savoir si ce problème peut être résolu dans l'espace de journalisation est un problème ouvert de longue date. C'est ce qu'on appelle le...
Je sais que le problème de l'arrêt est indécidable en général, mais il y a certaines machines Turing qui s'arrêtent évidemment et d'autres qui ne le sont évidemment pas. De toutes les machines de turing possibles, quelle est la plus petite où personne n'a de preuve qu'elle s'arrête ou...
L'un des Saint Graal de la conception d'algorithmes est de trouver un algorithme fortement polynomial pour la programmation linéaire, c'est-à-dire un algorithme dont l'exécution est délimitée par un polynôme dans le nombre de variables et de contraintes et est indépendante de la taille de la...
Je suis nouveau dans le domaine CS et j'ai remarqué que dans la plupart des articles que j'ai lus, il n'y a pas de résultats empiriques (pas de code, juste des lemmes et des preuves). Pourquoi donc? Étant donné que l'informatique est une science, ne devrait-elle pas suivre la méthode...
J'ai lu des articles sur les types dépendants et les contrats de programmation. D'après la majorité de ce que j'ai lu, il semble que les contrats soient des contraintes vérifiées dynamiquement et que les types dépendants soient vérifiés statiquement. Certains documents m'ont fait penser qu'il était...
J'ai lu Nielson & Nielson " Semantics with Applications ", et j'aime vraiment le sujet. J'aimerais avoir un livre de plus sur la sémantique du langage de programmation - mais je ne peux vraiment en obtenir qu'un. J'ai jeté un œil au livre Turbak / Gifford , mais il est trop long; Je pensais que...
Dans ce billet d'invité de Josh Grochow sur le blog de complexité, il rend compte d'un récent atelier consacré au GCT qui s'est tenu à Princeton en juillet. Plusieurs des participants ont fait valoir que nous devrions utiliser GCT pour attaquer des problèmes plus faciles que vs N P afin de...
Existe-t-il un exemple intéressant d'algorithme randomisé pour un problème de recherche qui génère toujours la même réponse (correcte), indépendamment de son caractère aléatoire interne, mais qui exploite le caractère aléatoire de sorte que son temps d'exécution attendu soit meilleur que le temps...
Y a-t-il une borne inverse de Chernoff qui limite la probabilité de queue au moins autant. c'est-à-dire si X1,X2,…,XnX1,X2,…,XnX_1,X_2,\ldots,X_n sont des variables aléatoires binomiales indépendantes et μ=E[∑ni=1Xi]μ=E[∑i=1nXi]\mu=\mathbb{E}[\sum_{i=1}^n X_i] . Alors peut-on prouver...
Dans la préface de ses livres très influents Automates, Langages et Machines (Volumes A, B), Samuel Eilenberg a promis de façon alléchante les Volumes C et D traitant "d'une hiérarchie (appelée hiérarchie rationnelle) des phénomènes non rationnels ... utilisant des relations rationnelles comme un...
Les années 80 ont donné naissance aux modèles PRAM et BSP de calcul parallèle. Il semble que l'apogée des deux modèles remonte à la fin des années 80 et au début des années 90. Ces domaines sont-ils toujours actifs en termes de recherche d'algorithmes parallèles? Existe-t-il des modèles plus...
Je voudrais trouver un algorithme de temps polynomial qui détermine si la durée d'un ensemble donné de matrices contient une matrice de permutation. Si quelqu'un sait si ce problème est d'une classe de complexité différente, ce serait tout aussi utile. EDIT: J'ai étiqueté cette question avec la...
Il est bien connu qu'une marche aléatoire dans la grille bidimensionnelle retournera à l'origine avec la probabilité 1. Il est également connu que la même marche aléatoire en TROIS dimensions a une probabilité strictement inférieure à 1 de revenir à l'origine . Ma question est: Y a-t-il quelque...
Dans quelques questions récentes ( q1 q2 ), il y a eu une discussion entre "Théorie A" et "Théorie B", apparemment pour capturer le fossé entre l'étude de la logique et des langages de programmation et l'étude des algorithmes et de la complexité. Cette terminologie était nouvelle pour moi, et une...