Voici le problème: Nous avons un carré avec des nombres de 1..N dans certaines cellules. Il est nécessaire de déterminer s'il peut être complété par un carré magique. Exemples: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Ce problème est-il NP-complet?...
Soit une classe de graphiques avec une largeur de clique bornée. Dans chaque graphique en G, certaines arêtes sont contractées (par exemple au hasard). La largeur de la clique est-elle toujours limitée?ggGggG Dans le cas où il n'est (en général) plus délimité, je serais très intéressé par un...
Récemment, je passais en revue une introduction aux algorithmes holographiques. Je suis tombé sur des objets combinatoires appelés Pfaffians. Je ne connais pas vraiment grand-chose à ce sujet en ce moment et je suis tombé sur des utilisations surprenantes qui peuvent être utilisées. Par exemple,...
Tout en essayant de résoudre un problème, j'ai fini par en exprimer une partie comme le programme linéaire entier suivant. Ici sont tous des entiers positifs donnés dans le cadre de l'entrée. Un sous-ensemble spécifié des variables x i j est mis à zéro, et le reste peut prendre des valeurs...
Une observation associée à la cryptographie asymétrique est que certaines fonctions sont (supposées être) faciles à exécuter dans une direction mais difficiles à inverser. De plus, s'il existe des informations de «trappe» qui permettent de calculer rapidement l'opération inverse, le problème...
La théorie du compilateur semble être un sujet assez vérifié. Quels sont les problèmes ouverts ou les recherches en cours dans le
Vertex Cover peut être facilement réduit en jeu indépendant et vice versa. Cependant, dans un contexte de complexité paramétrée, l'ensemble indépendant est plus difficile que Vertex Cover. Un noyau avec sommets existe pour Vertex Cover, mais Independent Set est W 1 hard.2k2k2k Comment la nature de...
J'ai trouvé que les systèmes de transition étiquetés sont un bon modèle pour mon application, à savoir qu'il existe un article sur la modélisation des cas d'utilisation à l'aide de LTS. La question est, que peut-on facilement prouver sur les LTS? Je voudrais réutiliser les solutions existantes pour...
Ceci est lié à la question générale de " Comment arbitrer un article? ". J'examine un document pour une conférence, et ce document devrait être rejeté, car il n'est pas suffisamment important pour être publié et présente des défauts dans certains de ses détails techniques. Le document n'est pas...
Il est bien connu qu'il existe un algorithme optimal dans le pire des cas pour calculer le code Huffman dans le temps θ ( n lgn )θ(nlgn)\theta(n\lg n) . Ceci est amélioré de deux manières orthogonales: Des codes libres de préfixe optimaux peuvent être calculés plus rapidement si l'ensemble de...
Les algorithmes génétiques évoluent en moins de générations avec une population plus importante, mais prennent également plus de temps pour calculer une génération. Existe-t-il des lignes directrices pour équilibrer ces deux facteurs, afin d'arriver à une solution viable le plus rapidement...
J'ai essayé la relaxation LP suivante de l'ensemble indépendant maximum max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 J'obtiens 1/21/21/2 pour chaque variable pour chaque graphique non bipartite cubique que...
En supposant que NP! = CoNP, il n'y a pas de certificat de taille polynomiale pour un problème coNP-complet. Mais qu'en est-il du certificat de taille sous-exponentielle? En particulier pour coSAT, existe-t-il une preuve de taille sous-exponentielle pour prouver qu'une formule n'est pas...
Les paramètres fixes et l'approximation sont des approches totalement différentes pour résoudre des problèmes difficiles. Ils ont une motivation différente. L'approximation recherche un résultat plus rapide avec une solution approximative. Le paramètre fixe recherche une solution exacte avec une...
Ce que j'appelle compter, c'est le problème qui consiste à trouver le nombre de solutions à une fonction. Plus précisément, étant donné une fonction (pas nécessairement une boîte noire), approximative .f:N→{0,1}f:N→{0,1}f:N\to \{0,1\}# { x ∈ N∣ f( x ) = 1 } = | F- 1( 1 )...
Étant donné dénominations, avec c 1 = 1 et c 2 < c 3 < . . < c n étant des nombres aléatoires uniformément répartis dans l'intervalle [ 2 , N ] . De manière asymptotique, pour quelle fraction de pièces l'algorithme gourmand génère-t-il un changement optimal en utilisant cet ensemble de...
Je commence à étudier la possibilité de compter sur un solveur SAT pour résoudre un problème d'optimisation qui m'intéresse, et je suis actuellement à la recherche d'une enquête qui présenterait des exemples de transformations "intelligentes" vers des variantes de SAT (c'est-à-dire des...
Chaque fois que j'enseigne la NP-Complétude, les étudiants demandent "y a-t-il des problèmes connus pour ne pas appartenir à NP?" Comment répondriez-vous? Je leur donne généralement un problème indécidable à titre d'exemple, mais cela ne tourne souvent pas bien: (a) si je leur donne le problème de...
Considérez le problème suivant - Étant donné les graphes planaires maximaux et G 2 , trouvez le graphique G avec un nombre maximal d'arêtes tel qu'il y ait un sous-graphe (pas nécessairement induit) dans G 1 et G 2 qui est isomorphe à GG1G1G_1G2G2G_2GGGG1G1G_1G2G2G_2GGG . Peut-on le faire en temps...
Contexte Cette question est motivée par un jeu de société appelé «Dracula». Dans ce jeu, il y a un vampire et quatre chasseurs, le but des chasseurs est d'attraper le vampire. Le jeu se déroule en Europe. Le jeu se présente comme suit: 1. Le joueur chasseur place tous les chasseurs dans les villes....