Il n'y a que très peu d'informations que je peux trouver sur le problème NP-complet de la résolution de l'équation diophantienne linéaire en nombres entiers non négatifs. C'est - à - dire, est - il une solution non négatif à l'équation a 1 x 1 + a 2 x 2 + . . . + a n x n = b , où toutes les...
Un couvercle de bord est un sous-ensemble de bords d'un graphique de sorte que chaque sommet du graphique est adjacent à au moins un bord du couvercle. Les deux articles suivants indiquent que le comptage des couvertures de bord est # P-complet: Un FPTAS simple pour compter les couvertures de bord...
Soit un digraphe (pas nécessairement un DAG) et soit s , t ∈ V ( G ) . Quelle est la complexité de compter le nombre de simples s - t chemins dans G . ggGs , t ∈ V( G )s,t∈V(g)s,t \in V(G) s - ts-ts-tggG Je m'attendrais à ce que le problème soit # -complet, mais je n'ai pas pu trouver une référence...
∑X∏i j ∈ EF( xje, xj)∑X∏jej∈EF(Xje,Xj)\sum_x \prod_{ij \in E} f(x_i,x_j)maxX∏i j ∈ EF( xje, xj)maxX∏jej∈EF(Xje,Xj)\max_x \prod_{ij \in E} f(x_i,x_j) Lorsque max ou sum est pris sur tous les étiquetages de , le produit est pris sur tous les bords pour un graphique et est une fonction arbitraire....
J'ai un polytope PPP défini par {x:Ax≤b,x≥0}{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} . Question: Étant donné un sommet vvv de PPP , existe-t-il un algorithme polynomial de temps pour échantillonner uniformément à partir des voisins de vvv dans le graphique de PPP ? (Polynôme dans la dimension, le...
Il est difficile de trouver une approximation à facteur constant du cycle le plus long dans les graphiques hamiltoniens cubiques. Les graphiques hamiltoniens cubiques ont au moins deux cycles hamiltoniens.NPNPNP Quelles sont les limites supérieure et inférieure les plus connues sur le nombre de...
Je lisais l'article de wikipedia sur le problème des huit reines. Il est indiqué qu'il n'existe pas de formule connue pour le nombre exact de solutions. Après quelques recherches, j'ai trouvé un article intitulé "Sur la dureté des problèmes de comptage des mappings complets". Dans cet article, il y...
Il existe un certain nombre de problèmes dans la théorie de la représentation combinatoire et la géométrie algébrique pour lesquels aucune formule positive n'est connue. Il y a plusieurs exemples auxquels je pense, mais permettez-moi de prendre le calcul des coefficients Kronecker comme exemple....
Question. Dans leur article Improved simulation of stabilizer circuits , Aaronson et Gottesman affirment que la simulation d'un circuit CNOT est ⊕L - complete (sous les réductions de l'espace de log). Il est clair qu'il est contenu dans ⊕L ; comment le résultat de dureté tient-il? De manière...
Dans l'article de Ben-Dor / Halevi [1], il est donné une autre preuve que le permanent est #P#P\#P complet. Dans la dernière partie de l'article, ils montrent la chaîne de réduction IntPerm∝NoNegPerm∝2PowersPerm∝0/1-PermIntPerm∝NoNegPerm∝2PowersPerm∝0/1-Perm\begin{equation} \text{IntPerm} \propto...
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...
Problème: étant donné représenté par un circuit booléen, générer un uniformément aléatoire tel que (ou sortie si un tel n'existe pas). ϕ : { 0 , 1 }n→ { 0 , 1 }ϕ:{0,1}n→{0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }nX∈{0,1}nx \in \{0,1\}^nϕ ( x ) = 1ϕ(X)=1\phi(x)=1⊥⊥\perpXXx Clairement, ce...
É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...
Considérons le problème # P-complet de compter le nombre de couvertures de sommets d'un graphe donné G=(V,E)G=(V,E)G = (V, E) . Je voudrais savoir s'il y a un résultat montrant comment la dureté d'un tel problème varie avec un paramètre de GGG (par exemple, d=|E||V|d=|E||V|d = \frac{|E|}{|V|}). Ma...
Le problème #SAT est le problème canonique # P-complete. C'est un problème de fonction plutôt qu'un problème de décision. Il demande, étant donné une formule booléenne dans la logique propositionnelle, combien d'affectations satisfaisantes F a. Quelles sont les meilleures limites inférieures sur...
Lemme: En supposant une équivalence éta, nous avons cela (\x -> ⊥) = ⊥ :: A -> B. Preuve: ⊥ = (\x -> ⊥ x)par eta-équivalence, et (\x -> ⊥ x) = (\x -> ⊥)par réduction sous lambda. Le rapport Haskell 2010, section 6.2 spécifie la seqfonction par deux équations: seq :: a -> b -> b...
Soit une formule CNF avec n variables et m clauses. Soit t ∈ { 0 , 1 } n une affectation de variable et f φ ( t ) ∈ { 0 , … , m } compte le nombre de clauses satisfaites par une affectation de variable à φ . Définissez ensuite Median-SAT comme le problème du calcul de la valeur médiane de f φ ( t )...
La parité-L, également connue sous le nom de L, est l'ensemble des langages reconnus par une machine de Turing non déterministe qui ne peut distinguer qu'un nombre pair ou un nombre impair de chemins "d'acceptation". Une question connexe récente⊕⊕\oplus été posée par Niel de Beaudrap. Ma question...
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...
Une formule Monotone-2CNF est une formule CNF où chaque clause est composée d'exactement 2 littéraux positifs. Maintenant, j'ai une formule Monotone-2CNF FFF. Soit SSS l'ensemble des affectations satisfaisantes de FFFJ'ai également un oracle qui est capable de donner les informations suivantes:OOO...