Cette question est motivée par une question MathOverflow de Peng Zhang . Valiant a montré que le comptage des cliques maximales dans un graphique général est # P-complet, mais que se passe-t-il si nous nous limitons aux graphiques d'incomparabilité (c'est-à-dire que nous voulons compter les...
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 )...
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,...
Soit G un graphe connecté. Quelle est la complexité du comptage de tous les sous - graphiques connectés si G est des types suivants? G est général. G est plan. G est bipartite. Je ne me soucie pas des structures ou ..., il suffit de compter tous les sous-graphiques connectés! Je suis également...
Je partie d'une tentative de preuve . La tentative de preuve consiste en une réduction Karp du ⊕ P problème -complete ⊕ 3 RÉGULIER COUVERTURE vertex SAT.⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Étant donné un graphique cubique , la réduction produit une formule...
Étant donné un graphe orienté avec n nœuds tels que chaque sommet a exactement deux bords sortants, et un nombre naturel N codé en binaire, deux sommets s et t, Je veux compter le nombre de chemins (pas nécessairement simples) de s à t dans N étapes. Est-ce un problème # P-difficile? Ou...
Par http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Si est un langage complet-PSPACE, P A = N P A .UNEAAPUNE= NPUNEPA=NPAP^{A}=NP^{A} Si est un oracle à temps polynomial déterministe, P B ≠ N P B (en supposant P ≠ N P ).BBBPB≠ NPBPB≠NPBP^{B}\ne NP^{B}P≠ NPP≠NPP\ne NP est la classe de...
Pour un problème de recherche locale polynomiale , on sait qu'au moins une solution (optimum local) doit exister. Cependant, de nombreuses autres solutions pourraient exister, est-il difficile de compter le nombre de solutions pour un problème PLS complet? Je suis particulièrement intéressé par le...
Dans une formule CNF opposée en lecture deux, chaque variable apparaît deux fois, une fois positive et une fois négative. Je m'intéresse au problème , qui consiste à calculer la parité du nombre d'assignations satisfaisantes d'une formule CNF opposée lue deux
Je suppose qu'il s'appellerait # P-Space mais je n'ai trouvé qu'un seul article le mentionnant vaguement. Que diriez-vous de la version de comptage des problèmes EXP-TIME-Complete, NEXP-Complete ainsi que EXP-SPACE-Complete? Y a-t-il des travaux antérieurs que l'on peut citer en ce qui concerne...
Que sait-on de la transition de phase dans les problèmes # P-Complete? Spécifiquement, existe-t-il une transition de phase différente pour # DNF-k-SAT et # CNF-k-SAT? Mise à jour: Comme nous le savons, il y a une transition de phase dans Random k-SAT où la résolution du problème passe de facile à...
Je suis intéressé par le problème suivant. On nous donne en entrée une "permutation cible" , ainsi qu'une liste ordonnée d'indices . Ensuite, en commençant par la liste (c'est-à-dire la permutation d'identité), à chaque pas de temps nous l' dans avec le élément, avec probabilité indépendante . Soit...
Cette question s'est posée dans mon esprit après avoir lu les contributions d'András Salamon et Colin McQuillan à ma question précédente Compter les solutions des formules Monotone-2CNF . EDIT 30 e mars 2011 question n ° 2. Ajouté EDIT 29 e octobre 2010 Question reformulée après proposition András...
QUESTION COURTE: MAJ-3CNF est-il un problème PP-complet avec plusieurs réductions? VERSION PLUS LONGUE: Il est bien connu que MAJSAT (décider si la majorité des affectations de phrase propositionnelle satisfont la phrase) est PP-complet sous plusieurs réductions et #SAT est # P-complet sous...
Je parcourais le papier séminal de Les Valiant et j'ai eu du mal avec la proposition 4.3 à la page 10 du papier. Je ne vois pas pourquoi est-ce que s'il y a un générateur avec certaines valeurs pour avec une base , alors il existe un générateur avec les mêmes valeurs pour tout base ( ) ou ( ) pour...
Considérons le problème classique # P-complet # 3SAT, c'est-à-dire de compter le nombre d'évaluations pour rendre un 3CNF avec variables satisfaisable. Je m'intéresse à l' approximabilité additive . De toute évidence, il existe un algorithme trivial pour obtenir une erreur de , mais si , est-il...
Un homomorphisme d'un graphe à un graphe est un mappage de à tel que si et sont adjacents dans alors et sont adjacents dans . Un endomorphisme d'un graphe est un homomorphisme de à lui-même; il est sans virgule fixe s'il n'y a pas de tel que et il n'est pas trivial si ce n'est...
Considérez une formule monotone 3CNF ayant les deux restrictions supplémentaires suivantes: Chaque variable apparaît dans exactement clauses.222 Étant donné clauses, elles partagent au plus 1 variable.222111 Je voudrais savoir à quel point il est difficile de compter les affectations satisfaisantes...
Soit un graphe. Soitêtre un entier. Soit le nombre de sous-graphes induits par les arêtes de ayant sommets et un nombre impair d'arêtes. Soit le nombre de sous-graphes induits par les arêtes de ayant sommets et un nombre pair d'arêtes. Soit . Le problème ODD EVEN DELTA consiste à calculer , étant...
Dans une question précédente, Algorithme paramétré pour trouver des bicliques , je me suis demandé s'il y avait des algorithmes paramétrés rapides pour trouver un -biclique dans un graphe de sommets n et j'ai appris qu'il était ouvert s'il était FPT par rapport à k . Est-ce la même chose pour le...