La propagation de la croyance s'est avérée être une méthode très puissante grâce à la recherche de modèles graphiques probabilistes. Cependant, je ne connais rien de BP comparable aux méthodes MCMC où nous pouvons avoir des schémas d'approximation randomisés entièrement polynomiaux (FPRAS) pour les...
Il est mentionné dans un commentaire dans un autre article de cstheorySE que PSPACE- exhausteness implique APX-hardness. Quelqu'un peut-il expliquer / partager une référence pour cela? Est-ce "serré"? (c.-à-d. y a-t-il des problèmes PSPACE complets dont le problème d'optimisation admet une...
Il me semble que la plupart des théoriciens de la complexité croient généralement à la règle philosophique suivante: Si nous ne pouvons pas trouver un algorithme efficace pour le problème , et nous pouvons réduire problème A à un problème B , alors il n'y a probablement pas un algorithme efficace...
Je veux en savoir plus sur les algorithmes algébriques et la complexité de la théorie. Je m'intéresse en particulier au PIT. Existe-t-il un ensemble de notes de cours, de livres, d'articles et d'enquêtes pour les étudiants qui ont lu un manuel standard sur la théorie comme le livre de Sipser ou le...
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...
Nous considérons les DAG (graphes acycliques dirigés) avec un nœud source sss et un nœud cible ; les arêtes parallèles joignant la même paire de sommets sont autorisées. A - coupe est un ensemble d'arêtes dont le retrait détruit toutes - chemins plus longs que ; des chemins - courts ainsi que de...
Razborov a prouvé que la correspondance de fonction monotone n'est pas en mP . Mais peut-on calculer l'appariement en utilisant un circuit de taille polynomiale avec quelques négations? Existe-t-il un circuit P / poly avec des négations qui calcule la correspondance? Quel est le compromis entre le...
Considérons un vecteur de variables et un ensemble de contraintes linéaires spécifiées par .X⃗ X→\vec{x}A x⃗ ≤ bUNEX→≤bA\vec{x}\leq b En outre, considérons deux polytopes
Le temps constant est la complexité absolue la plus basse. On peut se demander: y a-t-il quelque chose de non trivial qui peut être calculé en temps constant? Si nous nous en tenons au modèle de la machine de Turing, alors peu de choses peuvent être faites, car la réponse ne peut dépendre que d'un...
Pour tout langage arbitraire NP complet, existe-t-il toujours un surensemble de polytimes dont le complément est également infini? Une version triviale qui ne stipule pas que le sur-ensemble a un complément infini a été demandée à /cs//q/50123/42961 Aux fins de cette question, vous pouvez supposer...
Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1}RegReg\mathsf{Reg}TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg}Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0}NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0}Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} Y a-t-il un...
Le kkk -ième polynôme symétrique élémentaire est la somme de tous produits de variables distinctes. Je m'intéresse à la complexité du circuit arithmétique monotone de ce polynôme. Un algorithme de programmation dynamique simple (ainsi que la figure 1 ci-dessous) donne un circuit avec des portes...
Le non-déterminisme peut-il accélérer le calcul déterministe? Si oui, combien? En accélérant le calcul déterministe par le non-déterminisme, j'entends les résultats de la forme: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Par exemple quelque chose comme...
Y at - il eu des travaux visant à trouver le nombre minimum d'opérations arithmétiques élémentaires nécessaires pour calculer le déterminant d'un par matrice pour les petites et fixe ? Par exemple, .n n 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...
Soit la fonction qui mappe un circuit s- porte C sur n bits et une chaîne de n bits x à C ( x ) . Supposons que les circuits sont codés comme une séquence acyclique d'affectations k : = g ( i , j ) où i , j , k sont des étiquettes de fils.C i r c u i t E v a ls ,
Compte tenu des sujets abordés lors d'une conférence comme le STOC, des chercheurs en algorithmes ou en complexité utilisent-ils activement COQ ou Isabelle? Si oui, comment l'utilisent-ils dans leurs recherches? Je suppose que la plupart des gens n'utiliseraient pas de tels outils car les preuves...
Une langue est en s'il existe une machine de Turing de l'espace de log qui décide de la langue avec une quantité polynomiale de conseils.L/polyL/polyL/poly Voir ici pour plus d'informations: https://en.wikipedia.org/wiki/L/poly Question Quelles sont les conséquences de ?P⊆L/polyP⊆L/polyP \subseteq...
Quelle est la complexité de décider si un intervalle des nombres naturels contient un nombre premier? Une variante du tamis d'Ératosthène donne un algorithme O~(L)O~(L)\tilde O(L) , où LLL est la longueur de l'intervalle et ∼∼\sim cache les facteurs poly-logarithmiques au point de départ de...
Il est connu grâce à Immerman et Szelepcsényi que si f = Ω ( log ) (même pour les fonctions constructibles non spatiales).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) Dans le même article, Immerman déclare que la hiérarchie alternative de...