Existe-t-il un moyen de coder une instance de sous-ensemble de somme ou le problème de partition numérique afin qu'une (petite) solution à une relation entière donne une réponse? Si ce n'est pas définitivement, dans un sens probabiliste? Je sais que LLL (et peut-être PSLQ) ont été utilisés avec un...
Objectif : établir la conjecture qu'il n'y a pas de plan projectif d'ordre 12. En 1989, en utilisant la recherche informatique sur un Cray, Lam a prouvé qu'il n'existait aucun plan projectif d'ordre 10. Maintenant que le nombre de Dieu pour le cube de Rubik a été déterminé après seulement quelques...
De nombreux cryptosystèmes à clé publique ont une sorte de sécurité prouvable. Par exemple, le cryptosystème Rabin est aussi difficile que l'affacturage. Je me demande si ce type de sécurité prouvable existe pour les cryptosystèmes à clé secrète, tels que AES. Sinon, quelle est la preuve qu'il est...
est la classe de problèmes de décision pouvant être résolus par une famille decircuits de profondeur O ( log i n ) avec des portes fanin non bornées OR et fanin borné ET. Les négations ne sont autorisées qu'au niveau d'entrée. On sait que S A C i pour i ≥ 1 est fermé sous complément et S A C 0 ne...
Quels types de conjectures et de grands problèmes ouverts sont les plus importants dans la théorie des jeux algorithmiques (ou la théorie des jeux en général en ce qui concerne CS)? Par exemple, la résolution de NASH comme PPAD-complete aurait, je pense, été la plus importante jusqu'à ce qu'elle...
Considérez la liste faiblement liée dans un cadre purement fonctionnel. Ses louanges ont été chantées du haut des montagnes et continueront d'être chantées. Ici, je vais aborder l'une de ses nombreuses forces et la question de savoir comment l'étendre à la classe plus large de séquences purement...
Comment puis-je convaincre Coq que la fonction récursive donnée ci-dessous se termine? La fonction prend deux arguments inductifs. Intuitivement, la récursivité se termine car l'un ou l'autre argument est décomposé. Plus précisément, la fonction prend deux arbres en entrée. Inductive Tree := | Tip:...
Je révise un modèle cryptographique. Pour montrer son insuffisance, j'ai conçu un protocole artificiel basé sur l'isomorphisme des graphes. Il est "banal" (et pourtant controversé!) De supposer l'existence d'algorithmes BPP capables de générer "des instances dures du problème d'isomorphisme des...
J'ai écrit une implémentation de l'algorithme de Kuhn-Munkres pour le problème de correspondance parfaite bipartite de poids minimum basé sur des notes de cours que j'ai trouvées ici et là sur le web. Cela fonctionne vraiment bien, même sur des milliers de sommets. Et je suis d'accord que la...
Étant donné deux CNF, s'ils ont le même nombre d'affectations pour les rendre vraies, répondez "Oui", sinon répondez "Non". Il est facile de voir que c'est dans , car si nous connaissons le nombre exact de solutions à ces deux CNF, nous les campons simplement et répondons "Oui" ou...
Nous savons que l'algorithme de raccourci de Karger peut être utilisé pour prouver (de manière non constructive) que le nombre maximal de raccourcis possibles qu'un graphique peut avoir est .(n2)(n2)n \choose 2 Je me demandais si nous pouvions en quelque sorte prouver cette identité en donnant une...
1) Est-il possible d'avoir une réduction parcimonieuse d'un problème # P-complet #A à un problème de comptage #B quand (la version de décision) A est NP-complet et le B est en P? Par exemple, peut-il y avoir une réduction parcimonieuse de #SAT à #B, lorsque B est dans P? 2) Si B est dans P, quelles...
Quelqu'un m'oriente-t-il vers un article détaillant un théorème d'élimination des coupures pour la logique intuitionniste propositionnelle, y compris un type de données inductif tel que les nombres naturels (les listes ou les arbres conviendraient aussi)? Un exemple du genre de système que je suis...
L'algorithme hongrois est un algorithme d'optimisation combinatoire qui résout le problème d'appariement bipartite de poids maximum en temps polynomial et a anticipé le développement ultérieur de l'importante méthode primal-dual . L'algorithme a été développé et publié par Harold Kuhn en 1955, qui...
Disons que j'ai un gros bloc de code que j'ai déjà lexé et analysé. Supposons qu'un seul caractère change; Je voudrais mettre à jour mon analyse, mais comme la modification est très petite par rapport à l'ensemble, je voudrais savoir s'il est possible de ne pas analyser à nouveau l'ensemble, mais...
C'est un nom que j'ai inventé pour ce problème. Je ne l'ai jamais vu décrit auparavant. Je n'ai pas encore trouvé de preuve de complétude NP ni d'algorithme de temps polynomial pour ce problème. Ce n'est pas un problème de devoirs - il est lié à un problème que j'ai rencontré dans mon travail....
La complexité de calcul implique de grandes quantités de combinatoire et de théorie des nombres, quelques ingrédients de la stochastique et une quantité émergente d'algèbre. Cependant, en tant qu'analyseur, je me demande s'il existe des applications de l'analyse dans ce domaine, ou peut-être des...
J'explore l'idée d'écrire un SGBD de manière purement fonctionnelle. La structure de données traditionnelle utilisée pour l'indexation est B-Tree. J'aimerais connaître un équivalent purement fonctionnel de B-Tree qui serait optimisé pour minimiser l'accès au disque.
Considérons un langage tel que:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) et pour que L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) En d'autres termes, la machine la...
Dans quelle mesure le problème suivant a-t-il été étudié dans TCS? (Je m'excuse si l'énoncé du problème vous semble vague!) Étant donné un modèle de calcul MC (Turing Machine, Cellular Automata, Kolmogorov-Uspenskii Machine ... etc.) et un modèle de bruit qui pourraient affecter le calcul de MC,...