Étant donné un graphe orienté, nous voulons décider s'il contient un cycle orienté de longueur paire. Ce document de 1997 de YUSTER et ZWICK déclare que le problème n'est pas connu pour être en ni pour complet.PPPNPNPNP Y a-t-il un résultat récent qui résout la complexité du problème de cycle pair...
Nous pouvons faire la convolution en pour les polynômes plus / multiplier avec FFT. Cependant, l'approche ne semble pas très généralisable aux anneaux en général. Y a-t-il eu des progrès par rapport à la convolution naïve pour l'anneau max / plus?O(nlogn)O(nlogn)O(n\log n)O(n2)O(n2)O(n^2) Je dois...
Un problème CNF SAT NP est-il difficile lorsque le nombre total (mais pas la largeur) des clauses de 3 termes ou plus est limité au-dessus par une constante? Qu'en est-il spécifiquement quand il n'y a qu'une seule clause de ce
Un automate déterministe est appelé -local pour si pour chaque l'ensemble contient au plus un élément. Intuitivement, cela signifie que si un mot de longueur mène à un état, alors cet état est unique, ou dit différemment d'un mot arbitraire de longueur les derniers symboles déterminent l'état vers...
Il est connu que pour l' erreur , la pire définition de cas de complexité de communication aléatoire et la définition de cas moyenne sont équivalentes. Mais lorsque l'erreur est , la pire complexité de communication aléatoire est la même que la complexité de communication...
Les algorithmes distribués qui résistent aux défaillances peuvent être déterministes ou probabilistes. Prenons par exemple le problème du consensus. Paxos est déterministe dans le sens où, étant donné l'hypothèse qu'il fait, il fonctionne toujours . En revanche, le consensus randomisé fonctionne...
Dans le chapitre 13 «Objets atomiques» du livre «Algorithmes distribués» de Nancy Lynch, la linéarisation (également connue sous le nom d'atomicité) s'est avérée être une propriété de sécurité. C'est-à-dire que sa propriété de trace correspondante est non vide, fermée par préfixe et fermée par...
Les algorithmes en temps polynomial sont connus pour trouver des groupes générateurs de groupes de permutation, ce qui est intéressant car nous pouvons alors représenter ces groupes de manière succincte sans renoncer aux algorithmes en temps polynomial pour répondre à de nombreuses questions...
La minimisation des circuits est le problème pour minimiser la taille d'un circuit donné. Existe-t-il quelque chose de similaire pour les programmes généraux? En particulier, ma question est - Existe-t-il des algorithmes pour minimiser le nombre d'instructions pour un programme donné. Je sais que...
Nous savons que l'égalité bêta de termes lambda simplement typés est décidable. Étant donné M, N: σ → τ, est-il décidable que ce soit pour tout X: σ, MX ≃β≃β≃_β
Cette question est de savoir s'il existe des tarpits de Turing réversibles connus, où "réversible" signifie au sens d' Axelsen et de Glück , et "tarpit" est un concept beaucoup plus informel (et pourrait ne pas être un très bon choix de mot), mais je ferai de mon mieux pour expliquer ce que je veux...
Existe-t-il des classes de graphes agréables pour lesquelles la largeur d'arbre est limitée par une fonction du nombre de cliques ω ( G ) , c'est-à-dire t w ( G ) ≤ f ( ω ( G ) ) ?t w ( G )tw(G)tw(G)ω ( G )ω(G)\omega(G)t w ( G ) ≤ f( ω ( G ) )tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Par exemple, c'est...
Je m'intéresse aux algorithmes pour les groupes finis mis en œuvre dans le package GAP. Il semble que tous les algorithmes connus dans ce domaine traitent des groupes de permutation / groupes matriciels; Schreier-Sims [1970] et Butler [1979] en sont deux fondamentaux, voir par exemple «Algorithms...
L'inégalité de Fano peut être exprimée sous de nombreuses formes, et une particulièrement utile est due (avec une modification mineure) à Oded Regev : Soit une variable aléatoire, et soit où est un processus aléatoire. Supposons l'existence d'une procédure qui, avec puisse reconstruire avec une...
Le relâchement complémentaire (CS) est couramment enseigné lorsque l'on parle de dualité. Il établit une belle relation entre la primale et la double contrainte / variables d'un point de vue mathématique. Les deux principales raisons d'appliquer CS (comme enseigné dans les cours d'études...
Depuis un certain temps, je m'intéresse beaucoup à la théorie des langages de programmation et aux calculs de processus et j'ai commencé à les étudier. Pour être honnête, c'est quelque chose qui ne me dérangerait pas de me lancer dans une carrière. Je trouve la théorie incroyablement fascinante....
Je suis tombé sur un problème ouvert posé par David Eppstein et je m'intéresse à son état de complexité. Il a supposé qu'il était NP-complet. Entrée: matrice par de 0 et 1, séquence de 0 et 1nnnnnnn2n2n^2 Question: Existe-t-il un chemin à travers les entrées de matrice adjacentes, couvrant chaque...
Étant donné deux polyèdres et Q , P et Q sont équidécomposables s'il existe des ensembles finis de polyèdres P 1 , … , P n et Q 1 , … , Q n tels que P i et Q i sont congruents pour tout i , P = ∪ n i = 1 P i et Q = ∪ n i = 1 QPPPQQQPPPQQQP1,…,PnP1,…,PnP_1, \ldots, P_nQ1,…,QnQ1,…,QnQ_1, \ldots,...
Appelons une langue NP peu certifiée si et seulement si:L∈L∈L \in Il existe un polynôme tel que pour chaque entrée x ∈ Σ ∗ de taille n , si x ∈ L alors l'ensemble U x des certificats u qui vérifient que x ∈ L est de taille polynomiale, ie | U x | ≤ p ( n ) .p:N→Np:N→Np : \mathbb{N} \rightarrow...
Quelle est la définition standard de Planar 3-SAT? J'ai vu un certain nombre de définitions différentes. Quel est le document original qui l'a défini et a prouvé qu'il était