Ce que je me demande précisément, c'est s'il existe une condition intéressante sur le pourcentage d'affectations qui satisfont à une formule 3SAT pour garantir que ces problèmes sont traitables. Supposons par exemple la classe de problèmes 3SAT que des 2 n affectations possibles satisfont la...
Le groupe Clifford d'opérateurs quantiques est généré par les opérations quantiques: Contrôlé-Z , Hadamard et Phase ( ).=|0⟩⟨0|+i|1⟩⟨1|=|0⟩⟨0|+i|1⟩⟨1|= |0\rangle\langle0| + i |1\rangle\langle1| Un circuit composé uniquement de ces portes peut être simulé efficacement sur un ordinateur classique....
Tout en travaillant sur un projet quelque peu indépendant pour Suresh, j'ai récemment rencontré des travaux effectués par Page et Opper sur les systèmes composables par l'utilisateur et une partie de leur travail a brièvement discuté de problèmes qui ne peuvent pas être vérifiés en temps...
En comptant les arguments, on peut montrer qu'il existe des polynômes de degré n dans 1 variable (c'est-à-dire quelque chose de la forme qui ont complexité du circuit n. De plus, on peut montrer qu'un polynôme comme nécessite au moins multiplications (vous en avez besoin juste pour obtenir un degré...
Étant donné un terme t : ∀x.∃y.(¬(x = 0) ⇒ x = S(y))dans la théorie des types de Martin-Lof, quelle est la valeur de w(t(0)), où west l'opérateur qui extrait le témoin d'un terme de type
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...
Quels sont les problèmes avec le meilleur rapport d'approximation connu obtenu par un algorithme renvoyant une solution uniformément aléatoire? Je connais un tel exemple pour le problème de magasin de flux de permutation : dans le document " Limites serrées pour la planification des ateliers de...
La décomposition des arbres est difficile dans le pire des cas, mais la méthode gourmande semble être presque optimale sur les petits réseaux réels. Sait-on quelque chose sur la dureté de la décomposition des arbres d'une instance "typique" d'une classe de graphes? Existe-t-il un exemple de famille...
Je recherche un nom ou des références à ce problème. Étant donné un graphe pondéré G = ( V, E, w )G=(V,E,w)G = (V, E, w) trouver une partition des sommets jusqu'à n = | V|n=|V|n = |V|fixe S1, … , SnS1,…,SnS_1,\ldots,S_n façon à maximiser la valeur des arêtes coupées: c ( S1, … , Sn) = ∑i ≠ j⎛⎝∑( u...
On m'a récemment rappelé le problème vs comme expliqué par Stephen A. Cook sur Clay Mathematics Institute.N PPP\mathsf{P}N PNP\mathsf{NP} Cela a piqué mon intérêt et j'aimerais en savoir plus. La première étape serait d'acquérir une compréhension plus approfondie du problème et une compréhension du...
Je lis dans SP Jordan, D. Gosset, "PJ amour des problèmes COMPLETES pour Hamiltonians stoquastic et matrices de MarkovQ MUNEQMAQMA " qu'il est peu probable que .Q MA ⊆ A MQMA⊆AMQMA \subseteq AM J'ai été surpris de cette affirmation. Quelle est donc la bonne relation entre et A M ?Q MUNEQMAQMAA...
Soit et notons G k l'ensemble de tous les graphes qui peuvent être incrustés sur une surface du genre k de telle sorte que tous les sommets soient situés sur la face externe . Par exemple, G 0 est l'ensemble des graphes planaires externes. La largeur d'arbre des graphes dans G k peut-elle être...
Quels sont les articles de recherche les plus importants sur les fondements des génériques en C # et
La programmation linéaire est, bien sûr, de nos jours très bien comprise. Nous avons beaucoup de travail qui caractérise la structure des solutions réalisables et la structure des solutions optimales. Nous avons la forte dualité, les algorithmes poly-temps, etc. Mais que sait- on des solutions...
J'ai posé cette question il y a quelques semaines à mathoverflow , mais je n'ai reçu aucune réponse. Ici, par grille 3D de longueur latérale je veux dire le graphique avec et , c'est-à-dire que les nœuds sont placés à des coordonnées entières en 3 dimensions entre 1 et , et un nœud est connecté à...
Razborov a prouvé que chaque circuit monotone qui calcule la fonction de correspondance parfaite pour les graphes bipartis doit avoir au moins portes (il l'a appelé "permanent logique"). Une meilleure borne inférieure pour le même problème a-t-elle été prouvée depuis lors? (disons ?) Pour autant...
C'est probablement assez simple, mais considérez le problème standard de correspondance par correspondance: Étant donné et , trouvez une séquence d'indices tels que . C'est, bien sûr, indécidable.β 1 , … , β N i 1 , … , i K α i 1 ⋯ α i K = β i 1 ⋯ β i Kα1,…,αNα1,…,αN\alpha_1, \ldots,...
Cette question est inspirée d'une question existante sur la possibilité de simuler une pile à l'aide de deux files d'attente en temps amorti par opération de pile. La réponse semble inconnue. Voici une question plus spécifique, correspondant au cas particulier dans lequel toutes les opérations PUSH...
\newcommand{\symp}{\Bumpeq} Une relation de cohérence sur un ensemble X est une relation réflexive et symétrique. Un espace de cohérence est une paire (X, \ symp_X) , et un morphisme f: X \ à Y entre les espaces de cohérence est une relation f \ subseteq X \ fois Y telle que pour tout (x, y) \ en f...
CMSOL est la logique de deuxième ordre monadique, c'est-à-dire une logique de graphiques où le domaine est l'ensemble des sommets et des arêtes, il y a des prédicats pour la contiguïté des sommets et les incidences des arêtes et des sommets, il y a une quantification sur les arêtes, les sommets,...