Le problème du "deuxième " est le problème de décider de l'existence d'une autre solution différente d'une solution donnée par exemple.XXX Pour certains problèmes -complets, la deuxième version de la solution est N P -complete (décidant de l'existence d'une autre solution pour le problème...
Impagliazzo, Paturi et Calabro, Impagliazzo, Paturi ont introduit l'hypothèse de temps exponentiel (ETH) et l'hypothèse de temps fortement exponentiel (SETH). En gros, SETH dit qu'il n'y a pas d'algorithme qui résout SAT dans le temps . 1,99n1.99n1.99^n Je me demandais ce que cela signifierait pour...
Existe-t-il un 2DFA avec états (où n est non trivial, disons au moins 4) qui nécessite au moins 2 n états pour simuler en utilisant n'importe quel DFA?nnnnnn2n2n2^n Un DFA bidirectionnel (2DFA) est un automate à états finis déterministe qui est autorisé à se déplacer d'avant en arrière sur sa...
Je suis à la recherche d'une classe de complexité qui se rapporte à APX comme BPP se rapporte à P. J'ai déjà posé la même question ici , mais peut-être TCS serait un endroit plus fructueux pour les réponses. La raison de la question est que dans les problèmes pratiques, il faut souvent trouver des...
Connaissez-vous des problèmes qui sont durs W [1] même pour les graphes de degrés bornés? La dimension métrique est difficile sur les graphiques avec un degré au plus 3, mais elle est W [2] -hard. Red-Blue Nonblocker était auparavant W [1] -hard sur les graphiques de degrés bornés, mais il y avait...
Existe-t-il un moyen documenté de calculer les nœuds? (circonférences incrustées dans un espace euclidien tridimensionnel). Je veux dire, un type de données pour les représenter, et un algorithme pour déterminer si deux instances du type de données représentent le même nœud. Si la réponse est...
La revendication suivante est-elle connue? Affirmation : Pour tout graphe à n sommets, il existe une coloration de G telle que chaque ensemble indépendant soit coloré par au plus O ( √gGGnnngGGcouleurs.O (
J'ai une question concernant les fonctions pures. Selon la page Wikipedia, l'une des conditions requises pour une fonction pure est: L'évaluation du résultat ne provoque aucun effet secondaire ou sortie sémantiquement observable, comme une mutation d'objets mutables ou une sortie vers des...
Pour autant que je sache, la borne inférieure de la norme de factorisation donnée par Linial et Shraibman est essentiellement la seule borne inférieure connue pour la complexité de la communication quantique (ou du moins elle subsume toutes les autres). Y a-t-il des preuves que cette limite n'est...
Dans les théorèmes gratuitement! , Wadler dit que la caractérisation de la paramétricité peut être ré-exprimée en termes de transformations naturelles laxistes et cela fera l'objet d'un autre article. De quel document parle-t-il? L'approche catégorique de la paramétricité que je connais utilise des...
Un graphe planaire est un graphe qui peut être intégré dans le plan, sans avoir de bords croisés. Soit un hypergraphe uniforme , c'est-à-dire un hypergraphe tel que tous ses hyper-bords aient la taille k.kG = ( X, E)G=(X,E)G=(X,E)kkk Il y a eu un certain travail sur l'intégration d'hypergraphes...
Après avoir lu une question connexe , sur les preuves d'existence d'algorithmes non constructives, je me demandais s'il existe des méthodes pour montrer l'existence de "petites" machines de calcul (disons, par état) sans les construire. Officiellement: supposons qu'on nous donne un langage et...
La théorie des types de Martin-Löf utilise des types W pour définir des structures inductives comme des nombres entiers, des listes, etc. Ces deux approches sont-elles équivalentes (elles semblent l'être)? Y a-t-il des raisons philosophiques pour lesquelles l'une est meilleure que l'autre (pour...
Notons le degré de sortie minimal dans G , et par δ - ( G ) le degré de sortie minimal .δ+( G )δ+(G)\delta^+(G)gGGδ-( G )δ−(G)\delta^-(G) Dans une question connexe , j'ai mentionné l'extension de Ghouila-Houri du théorème de Dirac sur les cycles hamiltoniens , qui suggère que si alors G est...
Ainsi, le problème de couverture d'ensemble est trivial si aucun des ensembles candidats ne se recoupe. Cependant, que faire si la taille de l'intersection pour une paire d'ensembles candidats était au plus 1? Ce problème est-il difficile à résoudre? J'apprécierais toute idée. Merci,...
Voici un problème avec une saveur similaire à l'apprentissage des juntes: Entrée: Une fonction F: { 0 , 1 }n→ { - 1 , 1 }f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\} , représentée par un oracle d'appartenance, c'est-à-dire un oracle qui a donné XXx , renvoie F( x )F(X)f(x) . Objectif: trouver...
Comme @Marzio l'a mentionné, le jeu suivant est connu sous le nom de Géographie généralisée . Étant donné un graphique et un sommet de départ , le jeu est défini comme suit:G = ( V, E)g=(V,E)G=(V,E)v ∈ Vv∈Vv \in V A chaque tour (alternance de deux joueurs), un joueur choisit u ∈ N( v )u∈N(v)u\in...
La preuve standard que BQPSPACE est dans PSPACE repose sur une analyse de type de jeu Savitch sur les intégrales de chemin. Cependant, il suppose que la durée d'exécution de BQPSPACE est au maximum exponentiellement longue. Cela est vrai pour PSPACE, mais pour les systèmes quantiques fermés avec un...
J'essaie de comprendre ce qui est impliqué dans la recherche théorique en informatique. Que font les informaticiens théoriques? Je sais que l'on consacre beaucoup de temps à l'enseignement, à la supervision des étudiants des cycles supérieurs, à la demande de financement et aux fonctions...
Crossposted de MO . Soit une classe de graphes définie par un nombre fini de sous-graphes induits interdits, tous cycliques (contenant au moins un cycle).CCC Existe-t-il des problèmes de graphes NP-difficiles qui peuvent être résolus en temps polynomial pour autre que Clique et Clique cover?CCC Si...