Si est un graphique avec un degré maximum 3 et est un mineur de H , alors G est un mineur topologique de H .GGGHHHGGGHHH Wikipedia cite ce résultat de la "théorie des graphes" de Diestel. Il est répertorié comme Prop 1.7.4 dans la dernière version du livre. Le livre manque de preuve ou de citation....
En répondant à cette question sur cstheory , j'ai (officieusement) prouvé à la volée le théorème suivant: Théorème : Pour tout fixe, le probem du cycle hamiltonien reste NP-complet même s'il est limité à des graphes bipartites planaires non orientés de degré 3 maximum qui ne contiennent pas de...
Je recherche un document d'enquête sur les concepts importants dans le domaine des automates quantiques. J'ai trouvé Quantum Automata Theory - A Review by Hirvensalo, mais cela semble trop succinct pour saisir le sujet. Existe-t-il une enquête assez complète sur le thème des automates quantiques?...
Disons qu'un graphe a la propriété si ses sommets peuvent être ordonnés de telle sorte que le graphe induit par les sommets a pour tout . En d'autres termes, l'ajout du sommet suivant dans notre classement n'affecte pas la métrique de distance du graphique actuel.M v 1 , v 2 , … v n H i { v 1 , … ,...
Le SAT unique est le problème bien connu: étant donné une formule CNF , est-il vrai que F a exactement un modèle?FFFFFF Je m'intéresse au problème «Exactement -SAT»: étant donné une formule CNF F et un entier m > 1 , est-il vrai que F a exactement m modèles?mmmFFFm>1m>1m>1FFFmmm Les deux...
Quelle est la largeur d'arbre minimale d'un circuit sur pour calculer MAJ?{∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} Ici MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} sort 1 si au moins la moitié de ses entrées sont 111 . Je ne me soucie que de la taille du circuit (doit être polynomial) et...
Je recherche des références bibliographiques pour l'algorithme / problème suivant: je l'ai nommé "BiSelect" ou "t-ary Select" ou "Select in Union of Sorted Arrays", mais je suppose qu'il a été introduit auparavant sous un autre nom? Problème Considérez le problème suivant: Étant donné tableaux...
Nous connaissons donc tous la borne inférieure de l'arbre de de ⌈ log 2 n ! ⌉ sur le nombre le plus défavorable de comparaisons effectuées par un algorithme de tri comparatif (déterministe). Elle ne s'applique pas au tri par comparaison aléatoire (si nous mesurons les comparaisons attendues pour...
Je suis certain que je ne suis pas le premier à entretenir l'idée que je vais présenter. Cependant, il serait utile que je puisse trouver de la documentation liée à l'idée. L'idée est de construire une machine de Turing M avec la propriété que si P = NP alors M résoudra 3-SAT en temps polynomial....
Qui a été la première personne à démontrer qu'une langue est en NP si un certificat pour la langue peut être vérifié en temps polynomial? Avons-nous un document qui le prouve formellement? Quand la communauté TCS a-t-elle commencé à mettre l'accent sur le non-déterminisme en faveur de la...
Supposons que l'on ait un algorithme randomisé (BPP) UNEAA utilisant rrr bits de caractère aléatoire. Les moyens naturels d'amplifier sa probabilité de réussite à 1 - δ1−δ1-\delta , pour tout δ> 0δ>0\delta>0 choisi , sont Exécutions indépendantes + vote majoritaire: exécutez UNEAA...
J'espère que quelqu'un connaît une référence à cela, donc je n'ai pas à lire la littérature ... Considérons une séquence de nombres . Considérez la séquence comme intervalles . De toute évidence, la séquence d'origine est bitonique si un point quelconque de la ligne réelle est poignardé à 2...
Un MPA (automate multipebble) est un 2DFA (automate fini déterministe bidirectionnel) qui peut utiliser un nombre arbitraire de cailloux (en fait au plus cailloux sur une entrée donnée w - l'entrée est écrite sur la bande entre deux extrémités -marqueurs comme # w # ). Pendant le calcul, un MPA...
Je lis des sondages de Trevisan et Lovett sur les applications de la combinatoire additive en TCS. La majorité de ces applications relèvent de la complexité de calcul , par exemple, les limites inférieures. Je me demande si la combinatoire additive a également trouvé des applications dans la...
Si vous recevez une collection d'ordres partiels, le tri topologique vous indiquera s'il existe une extension de la collection à un ordre total (une extension dans ce cas est un ordre total cohérent avec chacun des ordres partiels). Je suis tombé sur une variation: Correction d' un ensemble . On...
Donc, une recherche rapide sur le Web m'a amené à croire que "APXHardness implique qu'aucun QPTAS n'existe pour un problème à moins que [une certaine classe de complexité] ne soit incluse dans une [autre classe de complexité]" et c'est bien connu aussi! Il semble que tout le monde le sait, sauf...
L'algorithme simplex est souvent traité soit dans l'arithmétique réelle, soit dans le monde discret avec des calculs exacts. Cependant, il semble être implémenté le plus souvent avec une arithmétique à virgule flottante. Cela conduit à se demander si l'algorithme simplex doit être considéré comme...
Compte tenu composite N∈NN∈NN\in\Bbb N tamis de champ numérique général est le meilleur algorithme de factorisation connu pour factorisation entier de NNN . Il s'agit d'un algorithme randomisé et nous obtenons une complexité attendue de
TC0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd L'entrée Zoo pour TC0TC0\mathsf{TC^0} ne mentionne que la séparation entre la profondeur 2 et 3. Existe-t-il également une référence standard pour le fait que la hiérarchie AC0dACd0\mathsf{AC^0_d} ne...
Je fais actuellement des recherches sur le langage formel impliquant des classes de langues au-dessus de Regular mais en dessous de Context Free. Je regarde des choses comme les machines à compteurs multiples inversées, les compteurs à pile unique, les LFC déterministes, etc. Je me demande si...