Nous savons que des colorants bord de un graphe sont des colorants sommets d'un graphe spécial, à savoir du graphique de la ligne de .GGG GL(G)L(G)L(G)GGG Existe-t-il un opérateur de graphe tel que les colorations des sommets d'un graphe sont des colorations de bord du graphe ? Je m'intéresse à un...
On sait que l'on peut calculer exactement le déterminant d'une matrice dans l' espace determinstic . Quelles seraient les implications de complexité d'approximer le déterminant d'une matrice réelle, de norme au plus ( ) dans l'espace logarithmique randomisé, jusqu'à un 1 / \ text {poly }...
Un nouvel article est sorti revendiquant un algorithme quasi-polynomial pour le logarithme discret. http://arxiv.org/abs/1306.4244 Si elle est correcte, cela signifie-t-il que nous n'avons plus de séparation exponentielle en complexité d'un algorithme classique et de sa version quantique pour le...
Je me demande s'il y a des articles ou des recherches traitant des automates visiblement pushdown, mais permettant aux mots, plutôt qu'aux lettres simples, d'être poussés sur la pile. Alternativement, une construction qui a permis de symboles d'être poussé sur ϵϵ\epsilon -Transitions pourrait...
Tout graphique planaire , respectivement, externe satisfait | E ′ | ≤ 3 | V ′ | - 6 , respectivement, | E ′ | ≤ 2 | V ′ | - 3 , pour chaque sous-graphe G ′ = ( V ′ , E ′ ) de GG=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6|E′|≤2|V′|−3|E′|≤2|V′|−3|E'|\le...
Dans l'article An Efficient Algorithm for Graph Isomorphism de Corneil et Gotlieb, 1970, une conjecture a été énoncée sur laquelle l'algorithme énoncé s'est appuyé pour résoudre l'IG en temps polynomial. À savoir: que les graphiques représentatifs présentent la partition d'automorphisme du...
Cette question est probablement à la frontière entre le sujet et hors sujet, mais j'ai vu des questions similaires ici, donc je vais la poser. J'implémente un solveur Unique -SAT, dont l'entrée est une formule -CNF ayant au plus affectation satisfaisante. Pour tester son comportement pratique, j'ai...
On m'a proposé d'enseigner un nouveau programme de lycée TCS, qui nécessite la construction d'un curriculum. J'aimerais beaucoup entendre des opinions et des suggestions à ce sujet. Premièrement, quelqu'un connaît-il des écoles secondaires où un programme TCS a été enseigné avec succès (ou sans...
Il n'y a que très peu d'informations que je peux trouver sur le problème NP-complet de la résolution de l'équation diophantienne linéaire en nombres entiers non négatifs. C'est - à - dire, est - il une solution non négatif à l'équation a 1 x 1 + a 2 x 2 + . . . + a n x n = b , où toutes les...
Gowers a récemment souligné un problème, qu'il appelle «la détermination discrète de Borel», dont la solution est liée à la vérification des limites inférieures du circuit. Pouvez-vous fournir un résumé de l'approche adaptée à un public de théoriciens de la complexité? Que faudrait-il pour que...
Les automates finis sans ambiguïté (UFA) sont un type spécial d'automates finis non déterministes (NFA). Un NFA est appelé sans ambiguïté si chaque mot a au plus un chemin d'acceptation.w∈Σ∗w∈Σ∗w\in \Sigma^* Cela signifie .DFA⊂UFA⊂NFADFA⊂UFA⊂NFADFA\subset UFA\subset NFA Résultats d'automate...
Je recherche des problèmes connus pour être des PNJ pour les graphes dirigés mais qui ont un algorithme polynomial pour les graphes non orientés. J'ai vu la question concernant l'inverse des problèmes «dirigés» qui sont plus faciles que leur variante «non dirigée» , mais je recherche la dureté du...
Quand nous regardons le livre, Homotopy Type Theory - nous voyons les sujets suivants: Homotopy type theory 2.1 Types are higher groupoids 2.2 Functions are functors 2.3 Type families are fibrations 2.4 Homotopies and equivalences 2.5 The higher groupoid structure of type formers 2.6 Cartesian...
Les théorèmes de la hiérarchie sont des outils fondamentaux. Un bon nombre d'entre eux ont été rassemblés dans une question précédente (voir Quelles hiérarchies et / ou théorèmes de hiérarchie connaissez-vous? ). Certaines séparations de classes de complexité découlent directement des théorèmes de...
Un couvercle de bord est un sous-ensemble de bords d'un graphique de sorte que chaque sommet du graphique est adjacent à au moins un bord du couvercle. Les deux articles suivants indiquent que le comptage des couvertures de bord est # P-complet: Un FPTAS simple pour compter les couvertures de bord...
NP est-il dans DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log n})
Je suis intéressé s'il existe de bons articles ou enquêtes expositifs auxquels je peux me référer lorsque j'écris sur les opérateurs de classes de complexité : des opérateurs qui transforment les classes de complexité en faisant des choses telles que leur ajouter des quantificateurs. Exemples...
J'essaie de comprendre la complexité des fonctions exprimables via les portes de seuil et cela m'a conduit à . En particulier, je suis intéressé par ce que l'on sait actuellement sur l'apprentissage dans , car je ne suis pas un expert dans le domaine.T C0TC0\mathsf{TC}^0T C0TC0\mathsf{TC}^0 Ce que...
Toutes mes excuses si c'est une question trop large pour ce forum, mais je m'intéresse aux tactiques et astuces spécifiques que les chercheurs (dans TCS) utilisent pour rédiger l'introduction d'un document de recherche.
J'enseigne un cours sur les structures de données et couvrirai les arbres splay au début de la semaine prochaine. J'ai lu à plusieurs reprises l'article sur les arbres splay et je connais l'analyse et l'intuition derrière la structure des données. Cependant, je n'arrive pas à trouver une solide...