Je m'intéresse à la densité critique de 3-satisfiabilité (3-SAT) . On suppose qu'un tel α existe: si le nombre de clauses 3-SAT générées aléatoirement est ( α + ϵ ) n ou plus, elles sont presque sûrement insatisfaisantes. (Ici, ϵ est une petite constante et n est le nombre de variables.) Si le...
Certains chercheurs expérimentés en informatique théorique m'ont dit que travailler dans un emploi non lié à la recherche, même pendant quelques années, tuera votre carrière en tant que chercheur TCS. Cependant, je me méfie de l'affirmation selon laquelle le chemin qui mène d'un chercheur du SDC à...
Nous définissons un langage d'arbre régulier comme dans le livre TATA : c'est l'ensemble d'arbres accepté par un automate d'arbre fini non déterministe (chapitre 1) ou, de manière équivalente, l'ensemble d'arbres généré par une grammaire d'arbre régulière (chapitre 2). Les deux formalismes ont des...
Les autres éditeurs avisés de Wikipédia ont refusé ma demande de déplacer l'article de Wikipédia sur l' algorithme Rabin – Karp vers ce que je pense qu'il devrait être appelé, l'algorithme Karp – Rabin, au motif que le nom Rabin – Karp est utilisé plus souvent ( faux, si l'on se fie aux chiffres de...
Certains problèmes NP-durs qui sont exponentiels sur les graphes généraux sont sous-exponentiels sur les graphes planaires car la largeur de l'arborescence est au maximum de et ils sont exponentiels dans la largeur de l'arborescence.4.9|V(G)|−−−−−−√4.9|V(G)|4.9 \sqrt{|V(G)|} Fondamentalement, je...
RP est la classe de problèmes décidables par une machine de Turing non déterministe qui se termine en temps polynomial, mais qui est également autorisée en erreur unilatérale. P est la classe habituelle de problèmes décidables par une machine de Turing déterministe qui se termine en temps...
L'intersection de deux DFA (minimes) avec n états peut être calculée en utilisant O (n 2 ) temps et espace. Ceci est optimal en général, car le DFA résultant (minimal) peut avoir n 2 états. Cependant, si le DFA minimal résultant a z états, où z = O (n), peut-il être calculé dans l'espace n 2-eps ,...
Y a-t-il des références couvrant
Le rang de signe d'une matrice A avec + 1, -1 entrées est le plus petit rang (sur les réels) d'une matrice B qui a le même motif de signe que A (c'est-à-dire pour tous ). Cette notion est importante dans la complexité de la communication et la théorie de l'apprentissage.UNEje jBje j>...
Il est bien connu que toute preuve résolvant la question P vs NP doit surmonter la relativisation , les preuves naturelles et les barrières d' algèbre . Le diagramme suivant partitionne "l'espace de preuve" en différentes régions. Par exemple, correspond à l'ensemble des preuves qui relativisent et...
Considérez cette question comme résolue. Je ne choisirai pas la meilleure réponse car elles ont toutes contribué à ma compréhension du sujet. Je ne sais pas quel avantage nous avons en définissant formellement la sémantique de la logique des prédicats. Mais je vois la valeur d'avoir un calcul de...
Considérez le problème suivant: étant donné une formule CNF et une affectation qui satisfait cette formule, y a-t-il une autre affectation satisfaisante pour cette formule? Quelle est la complexité de ce problème? (C'est sûrement en NP, mais est-il aussi difficile en NP?) Que se passe-t-il si vous...
La complexité du problème suivant a-t-elle été étudiée? Entrée : un graphe cubique (ou régulier) , une borne supérieure naturelleG = ( V , E ) t333G = ( V, E)G=(V,E)G=(V,E)ttt Question : existe-t-il une partition de en parties de taille telle que la somme des ordres des sous-graphes correspondants...
J'ai récemment enseigné aux expanseurs et introduit la notion de graphes Ramanujan. Michael Forbes a demandé pourquoi on les appelait ainsi, et j'ai dû admettre que je ne sais pas. N'importe
1) Quelle est, le cas échéant, la relation entre le typage statique et les grammaires formelles? 2) En particulier, serait-il possible pour un automate borné linéaire de vérifier si, disons, un programme C ++ ou SML était bien typé? Un automate de pile imbriqué? 3) Existe-t-il un moyen naturel...
Hé les gars, je comprends que l'astuce de remplissage nous permet de traduire les classes de complexité vers le haut - par exemple . Le remplissage fonctionne en "gonflant" l'entrée, en exécutant la conversion (disons de à ), ce qui donne un algorithme "magique" que vous pouvez exécuter sur...
Toutes mes excuses pour avoir posé une question qui doit sûrement figurer dans de nombreuses références standard. Je suis curieux de savoir exactement la question dans le titre, en particulier je pense aux circuits booléens, sans limite de profondeur. J'ai mis "le plus petit" entre guillemets pour...
À la lumière des résultats récents d'Arora, Barak et Steurer, Algorithmes sous-exponentiels pour les jeux uniques et les problèmes connexes , je suis intéressé par les problèmes de graphes qui ont des algorithmes de temps sous-exponentiels mais qui ne sont pas résolus polynomialement. Un exemple...
Habituellement, on construit un graphe et pose ensuite des questions sur la décomposition des valeurs propres de la matrice d'adjacence (ou d'un parent proche comme le laplacien ) (également appelée spectre d'un graphe ). Mais qu'en est-il du problème inverse? Étant donné valeurs propres, peut-on...
Je lisais ça . Ça dit ... Vous ne vous retrouverez pas aussi affamé de financement comme Pure Mathematics. (Vous vous retrouverez toujours affamé de financement.) ... Pourquoi les mathématiciens purs ont-ils besoin de financement? (Oups sa question de flux mathématique) Pourquoi une personne...