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...
Je m'intéresse à la première histoire des résultats publiés sur les compromis spatio-temporels à usage général. En particulier, je veux savoir qui a décrit en premier le type d'algorithme suivant pour évaluer un calcul ayant un graphique de flux de données arbitraire avec en degré O (1) en...
Quelle est la complexité de calcul de l'optimisation de diverses fonctions sur le groupe unitaire ?U(n)U(n)\mathcal{U}(n) Une tâche typique, résultant souvent en théorie quantique de l' information, on maximiser le nombre de types (ou des polynômes d'ordre supérieur en U ) sur l' ensemble des...
Réponse: inconnue. Les questions posées sont naturelles, ouvertes et apparemment difficiles; la question est maintenant un wiki communautaire. Aperçu La question vise à diviser les langages appartenant à la classe de complexité PPP - ainsi que les machines de Turing de décision (TM) qui acceptent...
Quelle est la complexité de requête la plus connue de l'algorithme d'apprentissage Goldreich-Levin? Les notes de cours du blog de Luca Trevisan , Lemma 3, l'indiquent comme . Est-ce le plus connu en termes de dépendance à n ? Je serai particulièrement reconnaissant pour une référence à une source...
Je recherche des informations sur la complexité de calcul de la multiplication matricielle des matrices rectangulaires. Wikipedia indique que la complexité de la multiplication de par B ∈ R n × p est O ( m n p ) (multiplication des manuels scolaires).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times...
Je commence mon doctorat cet automne et je prévois de travailler en théorie de la complexité pour ma thèse. Je compile une liste d'articles importants que tout théoricien de la complexité devrait connaître. Quels papiers suggéreriez-vous à une personne comme moi? Et veuillez expliquer brièvement...
Ma première question est de savoir si une caractérisation de système de preuve interactive est connue pour toutes les classes de complexité classiques. J'appellerais P, NP, PSPACE, EXP, NEXP, EXPSPACE, les fonctions récursives et récursivement énumérables (entre autres). Plus précisément, une...
Résultat 1: le théorème de Linial-Mansour-Nisan dit que le poids de Fourier des fonctions calculées par les circuits A C0UNEC0\mathsf{AC}^0 est concentré sur les sous-ensembles de petite taille à forte probabilité. Résultat 2: Le a son poids de Fourier concentré sur le coefficient du degré n .P A R...
GI et Knot Problem sont tous deux des problèmes de décision d'équivalence structurelle d'objets mathématiques. Y a-t-il des résultats établissant des liens entre eux? De jolies connexions du problème des nœuds à la physique statistique ont été explorées via des polynômes de nœuds , y a-t-il des...
Quelle est la classe de complexité associée aux algorithmes de recherche exhaustifs? (Si il y en a un) Est-ce NP ou PSPACE? Existe-t-il des modèles de calcul restreints capturant la classe d'algorithmes de recherche exhaustifs similaires aux modèles de programmation gourmande et...
Etant donné que l' entrée d' un nombre entier et un ensemble S d'ensembles d'éléments de { 1 , . . . , N } , quelle est la complexité de trouver un ensemble T d'éléments de { 1 , . . . , n } tel que T a une cardinalité minimale et T n'est inclus dans aucun des ensembles de S...
D'après les commentaires sur une de mes questions sur mathoverflow je le sentiment que la question concernant GCD étant en par rapport à P est semblable à la question concernant Integer factorisation être dans P par rapport à N P .N CNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}N PNP\mathsf{NP} Y at - il...
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...
Cette question a été posée par Jan Pax sur la liste de diffusion Foundations of Mathematics . Certainement mais je soupçonne d'après les réponses à cette question que l'on ne sait pas si ⊕ P ⊆ P P (sinon, P P serait une réponse possible à cette question). Si ce n'est pas connu, y a-t-il une...
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...
Je lis l'annexe sur les limites inférieures de l'ACC pour NEXP dans le livre Arora et Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf L'un des lemmes clés est une transformation des circuits ACC0ACC0ACC^{0} en polynômes multilinéaires sur les...
J'ai recherché sur Internet, mais je n'ai trouvé aucune «grande liste» de variantes du problème SAT. Mis à part le (commun) SAM, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT Quelles sont les autres variantes? (cela sera également très utile si des classes de complexité sont données (si...
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...
Est-il connu si le problème d'évaluation du circuit est dans N C 1 ? Que diriez-vous de A L o g T i m e (uniforme N C 1 )?NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Nous savons que les circuits de profondeur peuvent être évalués avec des circuits de...