Ce jeu d'information parfait joué sur des graphiques est-il connu / étudié? Étant donné un graphique , deux joueurs alternent en choisissant un bord ou un nœud isolé. Si le joueur choisit une arête les deux nœuds et sont supprimés avec leurs arêtes incidentes. Si le joueur choisit un nœud isolé, le...
Je recherche des problèmes fortement NP-durs pour une réduction. Jusqu'à présent, j'ai trouvé les problèmes suivants: Problème de 3 partitions problème de bin-packing Correspondance numérique tridimensionnelle TSP Tout problème NP-complet sans données numériques, par exemple, SATISFACILITÉ, CYCLE...
Étant donné deux sous-ensembles de l' hypercube à dimensions (c'est-à-dire ), je cherche un algorithme qui récupère les points st le hamming la distance (ou la distance sur l'hypercube) est minimale. L'algorithme naïf qui vérifie juste chaque paire a besoin de time, existe-t-il un meilleur résultat...
Sur cs.stackexchange, j'ai posé des questions sur la bibliothèque d' algebird scala sur github, spéculant sur les raisons pour lesquelles ils pourraient avoir besoin d'un paquet d'algèbre abstrait. La page github contient quelques indices: Implémentations de Monoids pour des algorithmes...
Je recherche une structure de données et un algorithme pour calculer le nombre minimum de changements requis pour transformer un mot en un autre, étant donné les deux mots en entrée, où les seuls changements autorisés sont ajouter une lettre à l'une des extrémités (par exemple, AB -> ABC),...
J'ai quelques questions concernant la tromperie des circuits à profondeur constante. On sait que logO(d)(n)logO(d)(n)\log^{O(d)}(n) sens de l'indépendance est nécessaire pour tromper AC0AC0AC^0 circuits AC ^ 0 de profondeur ddd , où nnn est la taille de l'entrée. Comment peut-on le prouver?...
J'essaie de comprendre le protocole bitcoin dans le contexte de la sécurité cryptographique informatique. La question est une demande de référence aux fondations d'articles de cryptographie sur le bitcoin. Ma première question est quel bitcoin de protocole cryptographique abstrait essaie de mettre...
Je voudrais savoir s'il existe un monde relativisée où . Je suis également intéressé à savoir s'il existe un monde relativisée où P B ≠ N P B = P P B .PUNE= N PUNE≠ P PUNEPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}PB≠ N PB= P PBPB≠NPB=PPB{\bf P^B} \not = {\bf NP^B} = {\bf...
On dit qu'en gros une matrice de rang est rigide, si pour ramener son rang à , il faut changer au moins de ses entrées, pour certains .nnnn2n2\frac{n}{2}n1+ϵn1+ϵn^{1+\epsilon}ϵ>0ϵ>0\epsilon > 0 Si une matrice est rigide, alors le plus petit programme en ligne droite calculant ( est un vecteur...
Comme beaucoup de gens, je suis un grand utilisateur de logiciels mathématiques tels que Mathematica et Maple. Cependant, je suis devenu de plus en plus frustré par les nombreux cas où un tel logiciel vous donne simplement la mauvaise réponse sans avertissement. Cela peut se produire lors de...
Soit représente la distance moyenne d'un graphe connexe G .ad(G)ad(G)\rm{ad}(G)G.G.G. Une façon de calculer est de résumer les éléments de D ( G ) , la matrice de distance de G et de mettre à l'échelle la somme de manière appropriée.ad(G)ad(G)\rm{ad}(G)D(G),D(G),D(G),GGG Si le graphique de sortie...
L'assistant d'enseignement d'un cours a réussi à écrire un programme qui (de manière déterministe) génère des questions d'examen difficiles. Maintenant, elle aimerait écrire un programme qui génère les réponses correspondantes. Le problème de l'examinateur demande si cela est toujours possible; la...
J'essaie de comprendre la relation entre la complexité algorithmique et la complexité du circuit des déterminants et de la multiplication matricielle. On sait que le déterminant d'unmatrice n × n peut êtrecalculéen temps ˜ O ( M ( n ) ) , où M ( n ) est le temps minimum requis pour multiplier...
Il est connu que certaines classes de complexité syntaxique (non relativisées) entre et P S P A C E ont la propriété suivante, P ⊆ C o N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P A C E . Je me demande s'il existe une classe de complexité syntaxique (non relativisée) X telle que P P ⊆ X ⊆ P S P A C EPP{\bf P}P...
Ceci fait suite à ma question précédente: Meilleure complexité temporelle déterministe connue borne inférieure pour un problème naturel dans NP Je trouve déconcertant que nous n'ayons pas été en mesure de prouver de limite inférieure de temps déterministe quadratique pour un problème NP intéressant...
Une partie de la difficulté à en savoir plus sur ce problème est que le problème de correspondance des graphiques est différent de son cousin beaucoup plus célèbre, le problème de correspondance, mais difficile à en distinguer lors de l'utilisation des moteurs de recherche. Étant donné deux...
Alors que la règle générale est que dans les articles du TCS, les auteurs sont classés par ordre alphabétique, il y a quelques contre-exemples notables qui viennent à l'esprit, dans lesquels les auteurs sont classés d'une manière différente, par exemple, Méthodes algébriques pour les systèmes de...
Rappelons le diamètre d'un graphe est la longueur d'un plus court chemin plus long . Étant donné un graphique, un algorithme évident pour calculer résout le problème du chemin le plus court toutes paires (APSP) et renvoie la longueur du chemin le plus long trouvé.G diam ( G )gGGgGGdiam ( G...
Tous les solveurs #SAT que je connais, par exemple RelSat, C2D, ne renvoient que le nombre d'instances satisfaisables. Mais je veux connaître chacun de ces cas? Existe-t-il un tel solveur #SAT ou comment dois-je modifier un solveur #SAT disponible pour ce faire? Je vous
Cela peut être une question très simple. Mais quelle est la différence entre les types et les sortes? Ma compréhension actuelle est que vous avez une théorie des types avec des règles de type qui donnent une notion d'une instruction bien typée mais les tris sont plus basiques, différenciant les...