L'article de Fischer ce mois-ci m'a rappelé à quel point je connaissais mal l'art des structures de données succinctes et les algorithmes pour les utiliser. Pour ceux qui ne connaissent pas les structures de données succinctes: Étant donné une structure combinatoire, avec une (n) configurations...
Comme cela est bien connu, la PARITÉ ne peut pas être effectuée dans des circuits de profondeur constante de taille poly, et en fait, les circuits const-dept nécessitent un nombre de portes EXP. Qu'en est-il des circuits QUANTUM? a) La PARITE peut-elle être effectuée avec un circuit quantique qui a...
Je comprends que l'exhaustivité de Turing nécessite une mémoire illimitée et un temps illimité. Cependant, il existe une quantité finie d'atomes dans ce service, ce qui rend la mémoire limitée. Par exemple, même si est irrationnel, il n'y a aucun moyen de stocker plus d'un certain nombre de...
Étant donné un graphe acyclique dirigé, , est-il possible de supporter efficacement les opérations suivantes?G(V,E)g(V,E)G(V,E) : détermine s'il existe un chemin dans G du noeud a au noeud bisCo n n ected(G,a,b)jesConnecteré(g,une,b)isConnected(G,a,b)GgGauneabbb : Ajoute une arête de a à b dans le...
Que faire si l'on sait quelque chose sur la complexité paramétrée du calcul du nombre d'intersection d'un graphe (le plus petit nombre de cliques nécessaires pour couvrir tous ses bords)? Il est connu depuis longtemps pour être NP-complet, et c'est évidemment FPT car il a un noyau: si vous pouvez...
Mon idée d'une carrière de rêve est une carrière dans la recherche industrielle, où l'on arrive à s'attaquer à des problèmes difficiles, mais aussi à un usage pratique. À cette fin, la poursuite d'un doctorat en TCS (je suis intéressé par des sujets tels que les algorithmes distribués / parallèles,...
comment montrer la relation entre "Conjecture de jeux uniques" et "Théorème PCP"? comment expliquer que "la conjecture des jeux uniques" est une forme plus forte de "théorème
En théorie des automates (automates finis, automates pushdown, ...) et en complexité, il existe une notion d '"ambiguïté". Un automate est ambigu s'il existe un mot avec au moins deux cycles d'acceptation distincts. Une machine est k- ambiguë si pour chaque mot w accepté par la machine il y a au...
Je cherche un exemple simple de deux systèmes de transition qui sont équivalents LTL, mais pas équivalents trace. J'ai lu la preuve que l'équivalence de trace est plus fine que l'équivalence LTL dans le livre "Principles of Model Checking" (Baier / Katoen) mais je ne suis pas sûr de bien la...
L'hypercomputation fait référence à des modèles de calcul qu'il n'est pas possible de simuler à l'aide de machines de Turing. (Les hypercalculateurs ne sont pas nécessairement physiquement réalisables!) Certains hypercalculateurs ont accès à une ressource qui permet de résoudre le problème d'arrêt...
Il est bien connu que si vous lancez n balles dans n cases, le bin le plus chargé est très susceptible d'avoir balles dedans. En général, on peut poser des questions sur balles dans cases. Un article de RANDOM 1998 de Raab et Steger explore cela en détail, montrant qu'à mesure que augmente, la...
On m'a dit qu'il existe de bons algorithmes de temps polynomiaux pour approximer le nombre de chemins simples dans un graphe orienté d'un sommet de départ donné à un sommet de fin donné t . Quelqu'un connaît-il une bonne référence à ce sujet?sssttt Contexte: compter le nombre exact de chemins dans...
J'ai deux partitions de et je recherche la distance d'édition entre elles.[1…n][1…n][1 \ldots n] Par cela, je veux trouver le nombre minimal de transitions uniques d'un nœud dans un groupe différent qui sont nécessaires pour passer de la partition A à la partition B. Par exemple, la distance de {0...
La méthode de l'adversaire négatif ( ) est un SDP qui caractérise la complexité des requêtes quantiques. Il s'agit d'une généralisation de la méthode de l'adversaire largement utilisée ( ), et surmonte les deux obstacles qui ont entravé la méthode de l'adversaire:A D V±UNEréV±ADV^\pmA D VUNEréVADV...
J'ai récemment lu une preuve qui avait pour but de montrer qu'un problème était fortement NP-difficile, simplement en le réduisant (en temps polynomial) à partir d'un problème fortement NP-difficile. Cela n'avait aucun sens pour moi. J'aurais pensé que vous deviez montrer que tous les nombres...
Récemment, j'étais dans une conférence soutenue par ACM. Pendant le banquet, les organisateurs de la conférence nous ont parlé de l'avenir et du passé de la conférence. Ils nous ont dit que lors de l'édition 2010 de la conférence il y avait eu une perte de 5000 $. Ils nous ont montré le budget de...
Quelles sont les méthodes les plus connues pour la convolution cyclique de longueur nnn sur un petit champ, c'est-à-dire quand |F|≪n|F|≪n|\mathbb{F}| \ll n ? Je suis particulièrement intéressé par les champs de taille constante, ou même . Les déclarations et références générales sur l'efficacité...
Taquin Étant donné que le problème est assez long, voici un cas spécial qui capture son essence. Problème: Soit A un algorithme detrministique pour 3-SAT. Est le problème de la simulation complète de l'algorithme A (sur chaque instance du problème). P-Space dur? (Plus précisément, y a-t-il des...
est un ensemble de points sur un plan. Un point aléatoire x ∉ S est donné sur le même plan. La tâche consiste à trier tous les y ∈ S par distance euclidienne entre x et y .SSSx∉Sx∉Sx \notin Sy∈Sy∈Sy \in Sxxxyyy Une approche sans cerveau consiste à calculer les distances entre et y pour tous les y...
Il est bien connu que K5K5K_5 et K3,3K3,3K_{3,3} sont des mineurs interdits pour les graphes planaires. Il existe des centaines de mineurs interdits pour les graphiques intégrables sur un tore. Le nombre de mineurs interdits pour les graphes intégrables à la surface du genre g est une fonction...