Je présentais une conférence sur le tri des crêpes et j'ai mentionné que: Le tri par inversions est NP-difficile « signé » le tri par inversions est en P . Ce qui m'a fait réfléchir. Il y a un sens dans lequel le tri "signé" est "dirigé" - vous pouvez voir le signe comme une direction (et en fait,...
L'une des bonnes choses d'avoir évolué dans un univers à trois dimensions spatiales est que nous avons développé des compétences en résolution de problèmes concernant les objets dans l'espace. Ainsi, par exemple, nous pouvons considérer un triplet de nombres comme un point en 3-d et donc le calcul...
Existe-t-il des exemples de jouets qui fournissent des informations «essentielles» sur la compréhension des trois obstacles connus au problème P= NPP=NPP = NP - la relativisation, les preuves naturelles et
Remarque: il s'agit du puzzle sudoku 9x9 standard. La solution ne doit prendre en charge que des énigmes juridiques résolues . Ainsi, une solution n'a pas besoin de prendre en charge les cellules vides et peut s'appuyer sur les propriétés d'un puzzle sudoku résolu. Je me posais la question, mais je...
Si nous nous en remettons au livre (ou à toute autre version de la spécification du langage si vous préférez), quelle puissance de calcul une implémentation C peut-elle avoir? Notez que «implémentation C» a une signification technique: il s'agit d'une instanciation particulière de la spécification...
NC-Log-space-uniform est contenu dans un espace polylogue déterministe (parfois écrit PolyL). Le RNC à espace de log uniforme est-il également dans cette classe? La version standard randomisée de PolyL devrait être en PolyL, mais je ne vois pas que RNC (uniforme) est en randomL-PolyL. La difficulté...
Fixe un entier nnn et un alphabet Σ = { 0 , 1 }Σ={0,1}\Sigma=\{0,1\} . Définissez D FA ( n )DFA(n)DFA(n) comme la collection de tous les automates à états finis sur nnn états avec l'état de départ 1. Nous considérons tous les DFA (pas seulement ceux connectés, minimaux ou non dégénérés); ainsi |...
Il existe plusieurs algorithmes qui décident en temps polynomial si un graphique peut être dessiné dans le plan ou non, même beaucoup avec un temps d'exécution linéaire. Cependant, je n'ai pas trouvé d'algorithme très simple que l'on pourrait expliquer facilement et rapidement en classe et qui...
Je m'intéresse aux raisons pour lesquelles les nombres naturels sont si appréciés par les auteurs de livres sur la théorie des langages de programmation et la théorie des types (par exemple J. Mitchell, Foundations for Programming Languages et B. Pierce, Types and Programming Languages). La...
Soit la classe A tous les graphes de taille qui ont un cycle hamiltonien. Il est facile de produire un graphe aléatoire à partir de cette classe - prenez n nœuds isolés, ajoutez un cycle hamiltonien aléatoire, puis ajoutez des bords au hasard.nnnnnn Soit la classe B tous les graphes de taille qui...
Tout d'abord, je m'excuse d'avance pour toute stupidité. Je ne suis en aucun cas un expert en théorie de la complexité (loin de là! Je suis un étudiant de premier cycle qui suit mon premier cours de théorie de la complexité) Voici ma question. Le théorème de Savitch indique maintenant que...
Je m'intéresse de plus en plus à la théorie des graphes spectraux, que je trouve fascinante, et j'ai commencé à rassembler quelques documents que je n'ai pas encore lus plus attentivement que ce que j'ai jusqu'à présent. Cependant, je suis curieux d'une déclaration apparue dans plusieurs sources...
La question sur la théorie " Qu'est-ce que NP est limité aux témoins de taille linéaire? " Demande à propos de la classe NP limitée aux témoins de taille linéaire O ( n )O(n)O(n) , mais Existe-t-il des problèmes naturels NP-complets dans lesquels (oui) les instances de taille nécessitent des...
En parallèle, j'écris un langage en utilisant Python. J'ai commencé par utiliser un clone flex / bison appelé Ply, mais je me heurte aux limites de la puissance de ce que je peux exprimer avec ce style de grammaire, et je ne suis pas intéressé à pirater ma langue en raison d'un décalage d'impédance...
J'étudie récemment Haskell et les langages de programmation. Quelqu'un pourrait-il recommander des livres sur la théorie des
Dans cet article de wikipedia sur l'exhaustivité de Turing, il déclare que: Le calcul lambda non typé est Turing complet, mais de nombreux calculs lambda typés, y compris le système F, ne le sont pas. La valeur des systèmes dactylographiés est basée sur leur capacité à représenter la plupart des...
Supposons que j'ai un poset "S" et un prédicat monotone "P" sur S. Je veux trouver un ou tous les éléments maximaux de S satisfaisant P. EDIT : Je suis intéressé à minimiser le nombre d' évaluations de P . Quels algorithmes existent pour ce problème et quelles propriétés et opérations...
La complexité du préfixe de Kolmogorov (c'est-à-dire que est la taille du programme d'auto-délimitation minimal qui génère ) a plusieurs fonctionnalités intéressantes:xK( x )K(x)K(x)Xxx Cela correspond à une intuition de donner aux chaînes avec des motifs ou une structure une complexité inférieure...
Dans son livre, Boolean Function Complexity, Stasys Jukna mentionne (page 564) que Kolmogorov croyait que chaque langue en P avait des circuits de taille linéaire. Aucune référence n'est mentionnée et je n'ai rien trouvé en ligne. Quelqu'un en sait-il plus
Dans de nombreux domaines, il existe des techniques canoniques que tous ceux qui travaillent dans le domaine devraient maîtriser. Par exemple, pour les réductions d'espace de journalisation, le "truc de bit" pour la composition consiste à ne pas construire la sortie complète de la fonction...