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...
J'ai posé cette question il y a 10 jours sur cs.stackexchange ici mais je n'ai pas eu de réponse. Dans un article très célèbre (dans la communauté des réseaux), Wang et Crowcroft présentent des résultats de complétion du calcul de chemin sous plusieurs contraintes additives / multiplicatives. Le...
J'ai posé cette question sur Stack Overflow il y a un moment: Problème: la vente de Bob . Quelqu'un a également suggéré de poser la question ici. Quelqu'un a déjà posé une question liée à ce problème ici - sous- forêt de poids minimum de cardinalité donnée - mais pour autant que je comprends cela...
Un ensemble de frappe d'une famille est un sous-ensemble de tel que pour . Le problème pour trouver un ensemble de frappe minimum d'une famille donnée est NP-difficile en général, car il généralise le problème de couverture de vertex. Maintenant ma question est:H ⋃ n i = 1 S i H ∩ S i ≠ ∅ 1 ≤ i ≤...
Cette question est étroitement liée à un autre article: Transitions de phase dans les problèmes difficiles NP, mais elle est quelque peu différente. Bien que cette question concerne la dureté d'instances particulières de problèmes difficiles NP, il s'agit de classer la difficulté des mêmes...
Quelle est la complexité de calcul du problème suivant: étant donné deux matrices complexes et vérifiez s'il existe une matrice de permutation telle que: n×nn×nn\times nAAABBBPPPB=PAPT.B=PAPT.B = P A P^T. Si cela aide, on peut supposer que et B sont hermitiens (ou même que A et B sont réels et...
Considérons une collection d'ensembles F = { F 1 , F 2 , … , F n } sur un ensemble de base U = { e 1 , e 2 , … , e n } où | F i | ≪ n et e i ∈ F i , et soit k un entier positif.F= { F1, F2, … , Fn}F=\{F_1,F_2,\dotsc,F_n\}U= { e1, e2, … , En}U=\{e_1,e_2,\dotsc,e_n\}| Fje||F_i| ≪\ll nneje∈ Fjee_i \in...
J'espérais que quelqu'un pourrait m'expliquer pourquoi exactement le problème de produit de sous-ensemble est fortement NP-difficile alors que le problème de somme de sous-ensemble est faiblement NP-difficile. Somme Sous - ensemble: Étant donné X= { x1, . . . , xn}X={X1,...,Xn}X = \{x_1,...,x_n\}...
Quelle est la complexité du problème suivant? Entrée : unchemin hamiltonienen K nHHHKnKnK_n un sous-ensemble de paires de sommetsR⊆[n]2R⊆[n]2R \subseteq [n]^2 un entier positif kkk Requête : existe-t-il un correspondant tel que pour chaque , ? (où G = ( [ n ] , M ∪ H ) )MMM(v,u)∈R(v,u)∈R(v,u) \in...
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...
Comme tout le monde le sait, le SAT est complet pour les réductions de plusieurs P de rapport au temps polynomial. Elle est toujours complète par rapport aux réductions multiples de A C 0 .N PNP\mathsf{NP}A C0UNEC0\mathsf{AC^0} Ma question est quelle est la profondeur minimale requise pour les...
Pendant longtemps, j'ai pensé qu'un problème était NP-complet s'il était à la fois (1) NP-dur et (2) en NP. Cependant, dans le célèbre article "La méthode ellipsoïde et ses conséquences dans l'optimisation combinatoire" , les auteurs affirment que le problème du nombre chromatique fractionnaire...
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....
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...
Je lisais récemment un très bon article de Valiant et Vazirani qui montre que si NP≠RPNP≠RP\mathbf{NP \neq RP} , il ne peut pas y avoir d'algorithme efficace pour résoudre SAT même sous la promesse qu'il est insatisfaisant ou qu'il a une solution unique. Montrant ainsi que SAT n'admet pas...
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...
Etant donné un graphe, , je veux trouver un optimal r -domination pour G . C'est, je veux un sous - ensemble S de V tel que tous les sommets de G sont à une distance d'au plus r de un sommet en S , tout en minimisant la taille S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS D'après ce que j'ai...
Il y a quelque temps, j'ai publié une demande de référence pour les problèmes de graphe où nous voulons trouver une partition à 2 des bords où les deux ensembles remplissent une propriété sans rapport avec leur cardinalité. J'essayais de prouver que le problème suivant est NP-difficile: Étant donné...
Est-il difficile de trouver la solution la plus simple à un système d'équations linéaires? Plus formellement, considérons le problème de décision suivant: Instance: Un système d'équations linéaires avec des coefficients entiers et un nombre ccc . Question: Existe-t-il une solution au système avec...
Le problème de partition est faiblement NP-complet car il a un algorithme de temps polynomial (pseudo-polynomial) si les entiers d'entrée sont délimités par un polynôme. Cependant, la partition 3 est un problème fortement NP-complet même si les entiers d'entrée sont délimités par un polynôme. En...